Mercurial > dropbear
comparison etc/mersenne.c @ 190:d8254fc979e9 libtommath-orig LTM_0.35
Initial import of libtommath 0.35
author | Matt Johnston <matt@ucc.asn.au> |
---|---|
date | Fri, 06 May 2005 08:59:30 +0000 |
parents | 86e0b50a9b58 |
children |
comparison
equal
deleted
inserted
replaced
142:d29b64170cf0 | 190:d8254fc979e9 |
---|---|
16 if ((res = mp_init (&n)) != MP_OKAY) { | 16 if ((res = mp_init (&n)) != MP_OKAY) { |
17 return res; | 17 return res; |
18 } | 18 } |
19 | 19 |
20 if ((res = mp_init (&u)) != MP_OKAY) { | 20 if ((res = mp_init (&u)) != MP_OKAY) { |
21 goto __N; | 21 goto LBL_N; |
22 } | 22 } |
23 | 23 |
24 /* n = 2^s - 1 */ | 24 /* n = 2^s - 1 */ |
25 if ((res = mp_2expt(&n, s)) != MP_OKAY) { | 25 if ((res = mp_2expt(&n, s)) != MP_OKAY) { |
26 goto __MU; | 26 goto LBL_MU; |
27 } | 27 } |
28 if ((res = mp_sub_d (&n, 1, &n)) != MP_OKAY) { | 28 if ((res = mp_sub_d (&n, 1, &n)) != MP_OKAY) { |
29 goto __MU; | 29 goto LBL_MU; |
30 } | 30 } |
31 | 31 |
32 /* set u=4 */ | 32 /* set u=4 */ |
33 mp_set (&u, 4); | 33 mp_set (&u, 4); |
34 | 34 |
35 /* for k=1 to s-2 do */ | 35 /* for k=1 to s-2 do */ |
36 for (k = 1; k <= s - 2; k++) { | 36 for (k = 1; k <= s - 2; k++) { |
37 /* u = u^2 - 2 mod n */ | 37 /* u = u^2 - 2 mod n */ |
38 if ((res = mp_sqr (&u, &u)) != MP_OKAY) { | 38 if ((res = mp_sqr (&u, &u)) != MP_OKAY) { |
39 goto __MU; | 39 goto LBL_MU; |
40 } | 40 } |
41 if ((res = mp_sub_d (&u, 2, &u)) != MP_OKAY) { | 41 if ((res = mp_sub_d (&u, 2, &u)) != MP_OKAY) { |
42 goto __MU; | 42 goto LBL_MU; |
43 } | 43 } |
44 | 44 |
45 /* make sure u is positive */ | 45 /* make sure u is positive */ |
46 while (u.sign == MP_NEG) { | 46 while (u.sign == MP_NEG) { |
47 if ((res = mp_add (&u, &n, &u)) != MP_OKAY) { | 47 if ((res = mp_add (&u, &n, &u)) != MP_OKAY) { |
48 goto __MU; | 48 goto LBL_MU; |
49 } | 49 } |
50 } | 50 } |
51 | 51 |
52 /* reduce */ | 52 /* reduce */ |
53 if ((res = mp_reduce_2k (&u, &n, 1)) != MP_OKAY) { | 53 if ((res = mp_reduce_2k (&u, &n, 1)) != MP_OKAY) { |
54 goto __MU; | 54 goto LBL_MU; |
55 } | 55 } |
56 } | 56 } |
57 | 57 |
58 /* if u == 0 then its prime */ | 58 /* if u == 0 then its prime */ |
59 if (mp_iszero (&u) == 1) { | 59 if (mp_iszero (&u) == 1) { |
60 mp_prime_is_prime(&n, 8, pp); | 60 mp_prime_is_prime(&n, 8, pp); |
61 if (*pp != 1) printf("FAILURE\n"); | 61 if (*pp != 1) printf("FAILURE\n"); |
62 } | 62 } |
63 | 63 |
64 res = MP_OKAY; | 64 res = MP_OKAY; |
65 __MU:mp_clear (&u); | 65 LBL_MU:mp_clear (&u); |
66 __N:mp_clear (&n); | 66 LBL_N:mp_clear (&n); |
67 return res; | 67 return res; |
68 } | 68 } |
69 | 69 |
70 /* square root of a long < 65536 */ | 70 /* square root of a long < 65536 */ |
71 long | 71 long |