Mercurial > dropbear
comparison bn_mp_prime_miller_rabin.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 | d29b64170cf0 |
children |
comparison
equal
deleted
inserted
replaced
142:d29b64170cf0 | 190:d8254fc979e9 |
---|---|
38 /* get n1 = a - 1 */ | 38 /* get n1 = a - 1 */ |
39 if ((err = mp_init_copy (&n1, a)) != MP_OKAY) { | 39 if ((err = mp_init_copy (&n1, a)) != MP_OKAY) { |
40 return err; | 40 return err; |
41 } | 41 } |
42 if ((err = mp_sub_d (&n1, 1, &n1)) != MP_OKAY) { | 42 if ((err = mp_sub_d (&n1, 1, &n1)) != MP_OKAY) { |
43 goto __N1; | 43 goto LBL_N1; |
44 } | 44 } |
45 | 45 |
46 /* set 2**s * r = n1 */ | 46 /* set 2**s * r = n1 */ |
47 if ((err = mp_init_copy (&r, &n1)) != MP_OKAY) { | 47 if ((err = mp_init_copy (&r, &n1)) != MP_OKAY) { |
48 goto __N1; | 48 goto LBL_N1; |
49 } | 49 } |
50 | 50 |
51 /* count the number of least significant bits | 51 /* count the number of least significant bits |
52 * which are zero | 52 * which are zero |
53 */ | 53 */ |
54 s = mp_cnt_lsb(&r); | 54 s = mp_cnt_lsb(&r); |
55 | 55 |
56 /* now divide n - 1 by 2**s */ | 56 /* now divide n - 1 by 2**s */ |
57 if ((err = mp_div_2d (&r, s, &r, NULL)) != MP_OKAY) { | 57 if ((err = mp_div_2d (&r, s, &r, NULL)) != MP_OKAY) { |
58 goto __R; | 58 goto LBL_R; |
59 } | 59 } |
60 | 60 |
61 /* compute y = b**r mod a */ | 61 /* compute y = b**r mod a */ |
62 if ((err = mp_init (&y)) != MP_OKAY) { | 62 if ((err = mp_init (&y)) != MP_OKAY) { |
63 goto __R; | 63 goto LBL_R; |
64 } | 64 } |
65 if ((err = mp_exptmod (b, &r, a, &y)) != MP_OKAY) { | 65 if ((err = mp_exptmod (b, &r, a, &y)) != MP_OKAY) { |
66 goto __Y; | 66 goto LBL_Y; |
67 } | 67 } |
68 | 68 |
69 /* if y != 1 and y != n1 do */ | 69 /* if y != 1 and y != n1 do */ |
70 if (mp_cmp_d (&y, 1) != MP_EQ && mp_cmp (&y, &n1) != MP_EQ) { | 70 if (mp_cmp_d (&y, 1) != MP_EQ && mp_cmp (&y, &n1) != MP_EQ) { |
71 j = 1; | 71 j = 1; |
72 /* while j <= s-1 and y != n1 */ | 72 /* while j <= s-1 and y != n1 */ |
73 while ((j <= (s - 1)) && mp_cmp (&y, &n1) != MP_EQ) { | 73 while ((j <= (s - 1)) && mp_cmp (&y, &n1) != MP_EQ) { |
74 if ((err = mp_sqrmod (&y, a, &y)) != MP_OKAY) { | 74 if ((err = mp_sqrmod (&y, a, &y)) != MP_OKAY) { |
75 goto __Y; | 75 goto LBL_Y; |
76 } | 76 } |
77 | 77 |
78 /* if y == 1 then composite */ | 78 /* if y == 1 then composite */ |
79 if (mp_cmp_d (&y, 1) == MP_EQ) { | 79 if (mp_cmp_d (&y, 1) == MP_EQ) { |
80 goto __Y; | 80 goto LBL_Y; |
81 } | 81 } |
82 | 82 |
83 ++j; | 83 ++j; |
84 } | 84 } |
85 | 85 |
86 /* if y != n1 then composite */ | 86 /* if y != n1 then composite */ |
87 if (mp_cmp (&y, &n1) != MP_EQ) { | 87 if (mp_cmp (&y, &n1) != MP_EQ) { |
88 goto __Y; | 88 goto LBL_Y; |
89 } | 89 } |
90 } | 90 } |
91 | 91 |
92 /* probably prime now */ | 92 /* probably prime now */ |
93 *result = MP_YES; | 93 *result = MP_YES; |
94 __Y:mp_clear (&y); | 94 LBL_Y:mp_clear (&y); |
95 __R:mp_clear (&r); | 95 LBL_R:mp_clear (&r); |
96 __N1:mp_clear (&n1); | 96 LBL_N1:mp_clear (&n1); |
97 return err; | 97 return err; |
98 } | 98 } |
99 #endif | 99 #endif |