Mercurial > dropbear
annotate bn_mp_invmod_slow.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 |
| rev | line source |
|---|---|
| 142 | 1 #include <tommath.h> |
| 2 #ifdef BN_MP_INVMOD_SLOW_C | |
| 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis | |
| 4 * | |
| 5 * LibTomMath is a library that provides multiple-precision | |
| 6 * integer arithmetic as well as number theoretic functionality. | |
| 7 * | |
| 8 * The library was designed directly after the MPI library by | |
| 9 * Michael Fromberger but has been written from scratch with | |
| 10 * additional optimizations in place. | |
| 11 * | |
| 12 * The library is free for all purposes without any express | |
| 13 * guarantee it works. | |
| 14 * | |
| 15 * Tom St Denis, [email protected], http://math.libtomcrypt.org | |
| 16 */ | |
| 17 | |
| 18 /* hac 14.61, pp608 */ | |
| 19 int mp_invmod_slow (mp_int * a, mp_int * b, mp_int * c) | |
| 20 { | |
| 21 mp_int x, y, u, v, A, B, C, D; | |
| 22 int res; | |
| 23 | |
| 24 /* b cannot be negative */ | |
| 25 if (b->sign == MP_NEG || mp_iszero(b) == 1) { | |
| 26 return MP_VAL; | |
| 27 } | |
| 28 | |
| 29 /* init temps */ | |
| 30 if ((res = mp_init_multi(&x, &y, &u, &v, | |
| 31 &A, &B, &C, &D, NULL)) != MP_OKAY) { | |
| 32 return res; | |
| 33 } | |
| 34 | |
| 35 /* x = a, y = b */ | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
36 if ((res = mp_mod(a, b, &x)) != MP_OKAY) { |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
37 goto LBL_ERR; |
| 142 | 38 } |
| 39 if ((res = mp_copy (b, &y)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
40 goto LBL_ERR; |
| 142 | 41 } |
| 42 | |
| 43 /* 2. [modified] if x,y are both even then return an error! */ | |
| 44 if (mp_iseven (&x) == 1 && mp_iseven (&y) == 1) { | |
| 45 res = MP_VAL; | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
46 goto LBL_ERR; |
| 142 | 47 } |
| 48 | |
| 49 /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */ | |
| 50 if ((res = mp_copy (&x, &u)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
51 goto LBL_ERR; |
| 142 | 52 } |
| 53 if ((res = mp_copy (&y, &v)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
54 goto LBL_ERR; |
| 142 | 55 } |
| 56 mp_set (&A, 1); | |
| 57 mp_set (&D, 1); | |
| 58 | |
| 59 top: | |
| 60 /* 4. while u is even do */ | |
| 61 while (mp_iseven (&u) == 1) { | |
| 62 /* 4.1 u = u/2 */ | |
| 63 if ((res = mp_div_2 (&u, &u)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
64 goto LBL_ERR; |
| 142 | 65 } |
| 66 /* 4.2 if A or B is odd then */ | |
| 67 if (mp_isodd (&A) == 1 || mp_isodd (&B) == 1) { | |
| 68 /* A = (A+y)/2, B = (B-x)/2 */ | |
| 69 if ((res = mp_add (&A, &y, &A)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
70 goto LBL_ERR; |
| 142 | 71 } |
| 72 if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
73 goto LBL_ERR; |
| 142 | 74 } |
| 75 } | |
| 76 /* A = A/2, B = B/2 */ | |
| 77 if ((res = mp_div_2 (&A, &A)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
78 goto LBL_ERR; |
| 142 | 79 } |
| 80 if ((res = mp_div_2 (&B, &B)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
81 goto LBL_ERR; |
| 142 | 82 } |
| 83 } | |
| 84 | |
| 85 /* 5. while v is even do */ | |
| 86 while (mp_iseven (&v) == 1) { | |
| 87 /* 5.1 v = v/2 */ | |
| 88 if ((res = mp_div_2 (&v, &v)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
89 goto LBL_ERR; |
| 142 | 90 } |
| 91 /* 5.2 if C or D is odd then */ | |
| 92 if (mp_isodd (&C) == 1 || mp_isodd (&D) == 1) { | |
| 93 /* C = (C+y)/2, D = (D-x)/2 */ | |
| 94 if ((res = mp_add (&C, &y, &C)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
95 goto LBL_ERR; |
| 142 | 96 } |
| 97 if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
98 goto LBL_ERR; |
| 142 | 99 } |
| 100 } | |
| 101 /* C = C/2, D = D/2 */ | |
| 102 if ((res = mp_div_2 (&C, &C)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
103 goto LBL_ERR; |
| 142 | 104 } |
| 105 if ((res = mp_div_2 (&D, &D)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
106 goto LBL_ERR; |
| 142 | 107 } |
| 108 } | |
| 109 | |
| 110 /* 6. if u >= v then */ | |
| 111 if (mp_cmp (&u, &v) != MP_LT) { | |
| 112 /* u = u - v, A = A - C, B = B - D */ | |
| 113 if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
114 goto LBL_ERR; |
| 142 | 115 } |
| 116 | |
| 117 if ((res = mp_sub (&A, &C, &A)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
118 goto LBL_ERR; |
| 142 | 119 } |
| 120 | |
| 121 if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
122 goto LBL_ERR; |
| 142 | 123 } |
| 124 } else { | |
| 125 /* v - v - u, C = C - A, D = D - B */ | |
| 126 if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
127 goto LBL_ERR; |
| 142 | 128 } |
| 129 | |
| 130 if ((res = mp_sub (&C, &A, &C)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
131 goto LBL_ERR; |
| 142 | 132 } |
| 133 | |
| 134 if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
135 goto LBL_ERR; |
| 142 | 136 } |
| 137 } | |
| 138 | |
| 139 /* if not zero goto step 4 */ | |
| 140 if (mp_iszero (&u) == 0) | |
| 141 goto top; | |
| 142 | |
| 143 /* now a = C, b = D, gcd == g*v */ | |
| 144 | |
| 145 /* if v != 1 then there is no inverse */ | |
| 146 if (mp_cmp_d (&v, 1) != MP_EQ) { | |
| 147 res = MP_VAL; | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
148 goto LBL_ERR; |
| 142 | 149 } |
| 150 | |
| 151 /* if its too low */ | |
| 152 while (mp_cmp_d(&C, 0) == MP_LT) { | |
| 153 if ((res = mp_add(&C, b, &C)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
154 goto LBL_ERR; |
| 142 | 155 } |
| 156 } | |
| 157 | |
| 158 /* too big */ | |
| 159 while (mp_cmp_mag(&C, b) != MP_LT) { | |
| 160 if ((res = mp_sub(&C, b, &C)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
161 goto LBL_ERR; |
| 142 | 162 } |
| 163 } | |
| 164 | |
| 165 /* C is now the inverse */ | |
| 166 mp_exch (&C, c); | |
| 167 res = MP_OKAY; | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
168 LBL_ERR:mp_clear_multi (&x, &y, &u, &v, &A, &B, &C, &D, NULL); |
| 142 | 169 return res; |
| 170 } | |
| 171 #endif |