ARM Shanghai IoT Team (Internal) / newMiniTLS-GPL

change some parameters in the library to meet the needs of the website httpbin.org

Fork of MiniTLS-GPL by Donatien Garnier

math/numtheory/fp_invmod.c@5:95f70ebfe61f, 2015-02-06 (annotated)

Committer:
shiyilei
Date:
Fri Feb 06 06:17:33 2015 +0000
Revision:
5:95f70ebfe61f
Parent:
0:35aa5be3b78d 
change some parameters in the library to meet the needs of httpbin.org

Who changed what in which revision?

UserRevisionLine numberNew contents of line
MiniTLS 0:35aa5be3b78d 1 /* TomsFastMath, a fast ISO C bignum library.
MiniTLS 0:35aa5be3b78d 2 *
MiniTLS 0:35aa5be3b78d 3 * This project is meant to fill in where LibTomMath
MiniTLS 0:35aa5be3b78d 4 * falls short. That is speed ;-)
MiniTLS 0:35aa5be3b78d 5 *
MiniTLS 0:35aa5be3b78d 6 * This project is public domain and free for all purposes.
MiniTLS 0:35aa5be3b78d 7 *
MiniTLS 0:35aa5be3b78d 8 * Tom St Denis, tomstdenis@gmail.com
MiniTLS 0:35aa5be3b78d 9 */
MiniTLS 0:35aa5be3b78d 10 #include <tfm.h>
MiniTLS 0:35aa5be3b78d 11
MiniTLS 0:35aa5be3b78d 12 static int fp_invmod_slow (fp_int * a, fp_int * b, fp_int * c)
MiniTLS 0:35aa5be3b78d 13 {
MiniTLS 0:35aa5be3b78d 14 fp_int x, y, u, v, A, B, C, D;
MiniTLS 0:35aa5be3b78d 15 int res;
MiniTLS 0:35aa5be3b78d 16
MiniTLS 0:35aa5be3b78d 17 /* b cannot be negative */
MiniTLS 0:35aa5be3b78d 18 if (b->sign == FP_NEG || fp_iszero(b) == 1) {
MiniTLS 0:35aa5be3b78d 19 return FP_VAL;
MiniTLS 0:35aa5be3b78d 20 }
MiniTLS 0:35aa5be3b78d 21
MiniTLS 0:35aa5be3b78d 22 /* init temps */
MiniTLS 0:35aa5be3b78d 23 fp_init(&x); fp_init(&y);
MiniTLS 0:35aa5be3b78d 24 fp_init(&u); fp_init(&v);
MiniTLS 0:35aa5be3b78d 25 fp_init(&A); fp_init(&B);
MiniTLS 0:35aa5be3b78d 26 fp_init(&C); fp_init(&D);
MiniTLS 0:35aa5be3b78d 27
MiniTLS 0:35aa5be3b78d 28 /* x = a, y = b */
MiniTLS 0:35aa5be3b78d 29 if ((res = fp_mod(a, b, &x)) != FP_OKAY) {
MiniTLS 0:35aa5be3b78d 30 return res;
MiniTLS 0:35aa5be3b78d 31 }
MiniTLS 0:35aa5be3b78d 32 fp_copy(b, &y);
MiniTLS 0:35aa5be3b78d 33
MiniTLS 0:35aa5be3b78d 34 /* 2. [modified] if x,y are both even then return an error! */
MiniTLS 0:35aa5be3b78d 35 if (fp_iseven (&x) == 1 && fp_iseven (&y) == 1) {
MiniTLS 0:35aa5be3b78d 36 return FP_VAL;
MiniTLS 0:35aa5be3b78d 37 }
MiniTLS 0:35aa5be3b78d 38
MiniTLS 0:35aa5be3b78d 39 /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
MiniTLS 0:35aa5be3b78d 40 fp_copy (&x, &u);
MiniTLS 0:35aa5be3b78d 41 fp_copy (&y, &v);
MiniTLS 0:35aa5be3b78d 42 fp_set (&A, 1);
MiniTLS 0:35aa5be3b78d 43 fp_set (&D, 1);
MiniTLS 0:35aa5be3b78d 44
MiniTLS 0:35aa5be3b78d 45 top:
MiniTLS 0:35aa5be3b78d 46 /* 4. while u is even do */
MiniTLS 0:35aa5be3b78d 47 while (fp_iseven (&u) == 1) {
MiniTLS 0:35aa5be3b78d 48 /* 4.1 u = u/2 */
MiniTLS 0:35aa5be3b78d 49 fp_div_2 (&u, &u);
MiniTLS 0:35aa5be3b78d 50
MiniTLS 0:35aa5be3b78d 51 /* 4.2 if A or B is odd then */
MiniTLS 0:35aa5be3b78d 52 if (fp_isodd (&A) == 1 || fp_isodd (&B) == 1) {
MiniTLS 0:35aa5be3b78d 53 /* A = (A+y)/2, B = (B-x)/2 */
MiniTLS 0:35aa5be3b78d 54 fp_add (&A, &y, &A);
MiniTLS 0:35aa5be3b78d 55 fp_sub (&B, &x, &B);
MiniTLS 0:35aa5be3b78d 56 }
MiniTLS 0:35aa5be3b78d 57 /* A = A/2, B = B/2 */
MiniTLS 0:35aa5be3b78d 58 fp_div_2 (&A, &A);
MiniTLS 0:35aa5be3b78d 59 fp_div_2 (&B, &B);
MiniTLS 0:35aa5be3b78d 60 }
MiniTLS 0:35aa5be3b78d 61
MiniTLS 0:35aa5be3b78d 62 /* 5. while v is even do */
MiniTLS 0:35aa5be3b78d 63 while (fp_iseven (&v) == 1) {
MiniTLS 0:35aa5be3b78d 64 /* 5.1 v = v/2 */
MiniTLS 0:35aa5be3b78d 65 fp_div_2 (&v, &v);
MiniTLS 0:35aa5be3b78d 66
MiniTLS 0:35aa5be3b78d 67 /* 5.2 if C or D is odd then */
MiniTLS 0:35aa5be3b78d 68 if (fp_isodd (&C) == 1 || fp_isodd (&D) == 1) {
MiniTLS 0:35aa5be3b78d 69 /* C = (C+y)/2, D = (D-x)/2 */
MiniTLS 0:35aa5be3b78d 70 fp_add (&C, &y, &C);
MiniTLS 0:35aa5be3b78d 71 fp_sub (&D, &x, &D);
MiniTLS 0:35aa5be3b78d 72 }
MiniTLS 0:35aa5be3b78d 73 /* C = C/2, D = D/2 */
MiniTLS 0:35aa5be3b78d 74 fp_div_2 (&C, &C);
MiniTLS 0:35aa5be3b78d 75 fp_div_2 (&D, &D);
MiniTLS 0:35aa5be3b78d 76 }
MiniTLS 0:35aa5be3b78d 77
MiniTLS 0:35aa5be3b78d 78 /* 6. if u >= v then */
MiniTLS 0:35aa5be3b78d 79 if (fp_cmp (&u, &v) != FP_LT) {
MiniTLS 0:35aa5be3b78d 80 /* u = u - v, A = A - C, B = B - D */
MiniTLS 0:35aa5be3b78d 81 fp_sub (&u, &v, &u);
MiniTLS 0:35aa5be3b78d 82 fp_sub (&A, &C, &A);
MiniTLS 0:35aa5be3b78d 83 fp_sub (&B, &D, &B);
MiniTLS 0:35aa5be3b78d 84 } else {
MiniTLS 0:35aa5be3b78d 85 /* v - v - u, C = C - A, D = D - B */
MiniTLS 0:35aa5be3b78d 86 fp_sub (&v, &u, &v);
MiniTLS 0:35aa5be3b78d 87 fp_sub (&C, &A, &C);
MiniTLS 0:35aa5be3b78d 88 fp_sub (&D, &B, &D);
MiniTLS 0:35aa5be3b78d 89 }
MiniTLS 0:35aa5be3b78d 90
MiniTLS 0:35aa5be3b78d 91 /* if not zero goto step 4 */
MiniTLS 0:35aa5be3b78d 92 if (fp_iszero (&u) == 0)
MiniTLS 0:35aa5be3b78d 93 goto top;
MiniTLS 0:35aa5be3b78d 94
MiniTLS 0:35aa5be3b78d 95 /* now a = C, b = D, gcd == g*v */
MiniTLS 0:35aa5be3b78d 96
MiniTLS 0:35aa5be3b78d 97 /* if v != 1 then there is no inverse */
MiniTLS 0:35aa5be3b78d 98 if (fp_cmp_d (&v, 1) != FP_EQ) {
MiniTLS 0:35aa5be3b78d 99 return FP_VAL;
MiniTLS 0:35aa5be3b78d 100 }
MiniTLS 0:35aa5be3b78d 101
MiniTLS 0:35aa5be3b78d 102 /* if its too low */
MiniTLS 0:35aa5be3b78d 103 while (fp_cmp_d(&C, 0) == FP_LT) {
MiniTLS 0:35aa5be3b78d 104 fp_add(&C, b, &C);
MiniTLS 0:35aa5be3b78d 105 }
MiniTLS 0:35aa5be3b78d 106
MiniTLS 0:35aa5be3b78d 107 /* too big */
MiniTLS 0:35aa5be3b78d 108 while (fp_cmp_mag(&C, b) != FP_LT) {
MiniTLS 0:35aa5be3b78d 109 fp_sub(&C, b, &C);
MiniTLS 0:35aa5be3b78d 110 }
MiniTLS 0:35aa5be3b78d 111
MiniTLS 0:35aa5be3b78d 112 /* C is now the inverse */
MiniTLS 0:35aa5be3b78d 113 fp_copy(&C, c);
MiniTLS 0:35aa5be3b78d 114 return FP_OKAY;
MiniTLS 0:35aa5be3b78d 115 }
MiniTLS 0:35aa5be3b78d 116
MiniTLS 0:35aa5be3b78d 117 /* c = 1/a (mod b) for odd b only */
MiniTLS 0:35aa5be3b78d 118 int fp_invmod(fp_int *a, fp_int *b, fp_int *c)
MiniTLS 0:35aa5be3b78d 119 {
MiniTLS 0:35aa5be3b78d 120 fp_int x, y, u, v, B, D;
MiniTLS 0:35aa5be3b78d 121 int neg;
MiniTLS 0:35aa5be3b78d 122
MiniTLS 0:35aa5be3b78d 123 /* 2. [modified] b must be odd */
MiniTLS 0:35aa5be3b78d 124 if (fp_iseven (b) == FP_YES) {
MiniTLS 0:35aa5be3b78d 125 return fp_invmod_slow(a,b,c);
MiniTLS 0:35aa5be3b78d 126 }
MiniTLS 0:35aa5be3b78d 127
MiniTLS 0:35aa5be3b78d 128 /* init all our temps */
MiniTLS 0:35aa5be3b78d 129 fp_init(&x); fp_init(&y);
MiniTLS 0:35aa5be3b78d 130 fp_init(&u); fp_init(&v);
MiniTLS 0:35aa5be3b78d 131 fp_init(&B); fp_init(&D);
MiniTLS 0:35aa5be3b78d 132
MiniTLS 0:35aa5be3b78d 133 /* x == modulus, y == value to invert */
MiniTLS 0:35aa5be3b78d 134 fp_copy(b, &x);
MiniTLS 0:35aa5be3b78d 135
MiniTLS 0:35aa5be3b78d 136 /* we need y = |a| */
MiniTLS 0:35aa5be3b78d 137 fp_abs(a, &y);
MiniTLS 0:35aa5be3b78d 138
MiniTLS 0:35aa5be3b78d 139 /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
MiniTLS 0:35aa5be3b78d 140 fp_copy(&x, &u);
MiniTLS 0:35aa5be3b78d 141 fp_copy(&y, &v);
MiniTLS 0:35aa5be3b78d 142 fp_set (&D, 1);
MiniTLS 0:35aa5be3b78d 143
MiniTLS 0:35aa5be3b78d 144 top:
MiniTLS 0:35aa5be3b78d 145 /* 4. while u is even do */
MiniTLS 0:35aa5be3b78d 146 while (fp_iseven (&u) == FP_YES) {
MiniTLS 0:35aa5be3b78d 147 /* 4.1 u = u/2 */
MiniTLS 0:35aa5be3b78d 148 fp_div_2 (&u, &u);
MiniTLS 0:35aa5be3b78d 149
MiniTLS 0:35aa5be3b78d 150 /* 4.2 if B is odd then */
MiniTLS 0:35aa5be3b78d 151 if (fp_isodd (&B) == FP_YES) {
MiniTLS 0:35aa5be3b78d 152 fp_sub (&B, &x, &B);
MiniTLS 0:35aa5be3b78d 153 }
MiniTLS 0:35aa5be3b78d 154 /* B = B/2 */
MiniTLS 0:35aa5be3b78d 155 fp_div_2 (&B, &B);
MiniTLS 0:35aa5be3b78d 156 }
MiniTLS 0:35aa5be3b78d 157
MiniTLS 0:35aa5be3b78d 158 /* 5. while v is even do */
MiniTLS 0:35aa5be3b78d 159 while (fp_iseven (&v) == FP_YES) {
MiniTLS 0:35aa5be3b78d 160 /* 5.1 v = v/2 */
MiniTLS 0:35aa5be3b78d 161 fp_div_2 (&v, &v);
MiniTLS 0:35aa5be3b78d 162
MiniTLS 0:35aa5be3b78d 163 /* 5.2 if D is odd then */
MiniTLS 0:35aa5be3b78d 164 if (fp_isodd (&D) == FP_YES) {
MiniTLS 0:35aa5be3b78d 165 /* D = (D-x)/2 */
MiniTLS 0:35aa5be3b78d 166 fp_sub (&D, &x, &D);
MiniTLS 0:35aa5be3b78d 167 }
MiniTLS 0:35aa5be3b78d 168 /* D = D/2 */
MiniTLS 0:35aa5be3b78d 169 fp_div_2 (&D, &D);
MiniTLS 0:35aa5be3b78d 170 }
MiniTLS 0:35aa5be3b78d 171
MiniTLS 0:35aa5be3b78d 172 /* 6. if u >= v then */
MiniTLS 0:35aa5be3b78d 173 if (fp_cmp (&u, &v) != FP_LT) {
MiniTLS 0:35aa5be3b78d 174 /* u = u - v, B = B - D */
MiniTLS 0:35aa5be3b78d 175 fp_sub (&u, &v, &u);
MiniTLS 0:35aa5be3b78d 176 fp_sub (&B, &D, &B);
MiniTLS 0:35aa5be3b78d 177 } else {
MiniTLS 0:35aa5be3b78d 178 /* v - v - u, D = D - B */
MiniTLS 0:35aa5be3b78d 179 fp_sub (&v, &u, &v);
MiniTLS 0:35aa5be3b78d 180 fp_sub (&D, &B, &D);
MiniTLS 0:35aa5be3b78d 181 }
MiniTLS 0:35aa5be3b78d 182
MiniTLS 0:35aa5be3b78d 183 /* if not zero goto step 4 */
MiniTLS 0:35aa5be3b78d 184 if (fp_iszero (&u) == FP_NO) {
MiniTLS 0:35aa5be3b78d 185 goto top;
MiniTLS 0:35aa5be3b78d 186 }
MiniTLS 0:35aa5be3b78d 187
MiniTLS 0:35aa5be3b78d 188 /* now a = C, b = D, gcd == g*v */
MiniTLS 0:35aa5be3b78d 189
MiniTLS 0:35aa5be3b78d 190 /* if v != 1 then there is no inverse */
MiniTLS 0:35aa5be3b78d 191 if (fp_cmp_d (&v, 1) != FP_EQ) {
MiniTLS 0:35aa5be3b78d 192 return FP_VAL;
MiniTLS 0:35aa5be3b78d 193 }
MiniTLS 0:35aa5be3b78d 194
MiniTLS 0:35aa5be3b78d 195 /* b is now the inverse */
MiniTLS 0:35aa5be3b78d 196 neg = a->sign;
MiniTLS 0:35aa5be3b78d 197 while (D.sign == FP_NEG) {
MiniTLS 0:35aa5be3b78d 198 fp_add (&D, b, &D);
MiniTLS 0:35aa5be3b78d 199 }
MiniTLS 0:35aa5be3b78d 200 fp_copy (&D, c);
MiniTLS 0:35aa5be3b78d 201 c->sign = neg;
MiniTLS 0:35aa5be3b78d 202 return FP_OKAY;
MiniTLS 0:35aa5be3b78d 203 }
MiniTLS 0:35aa5be3b78d 204
MiniTLS 0:35aa5be3b78d 205 /* $Source: /cvs/libtom/tomsfastmath/src/numtheory/fp_invmod.c,v $ */
MiniTLS 0:35aa5be3b78d 206 /* $Revision: 1.1 $ */
MiniTLS 0:35aa5be3b78d 207 /* $Date: 2007/01/24 21:25:19 $ */