5 * Some Modular Arithmetic Functions.
7 * Copyright (C) Lenka Fibikova 2000
22 int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx)
28 assert(a != NULL && p != NULL && ctx != NULL);
34 if (y2 == NULL) goto err;
36 if (!BN_nnmod(x, a, p, ctx)) goto err;
43 if (BN_copy(y, p) == NULL) goto err;
48 if (!BN_rshift1(y2, y)) goto err;
49 if (BN_cmp(x, y2) > 0)
51 if (!BN_sub(x, y, x)) goto err;
52 if (BN_mod_word(y, 4) == 3)
55 while (BN_mod_word(x, 4) == 0)
57 if (BN_mod_word(x, 2) == 0)
60 m = BN_mod_word(y, 8);
61 if (m == 3 || m == 5) L = -L;
69 if (BN_mod_word(x, 4) == 3 && BN_mod_word(y, 4) == 3) L = -L;
72 if (!BN_nnmod(x, x, y, ctx)) goto err;
83 int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)
87 BIGNUM *n0, *n1, *r, *b, *m;
90 assert(x != NULL && a != NULL && p != NULL && ctx != NULL);
91 assert(BN_cmp(a, p) < 0);
93 ret = BN_legendre(a, p, ctx);
94 if (ret < 0 || ret > 1) return 0;
97 if (!BN_zero(x)) return 0;
102 n0 = BN_CTX_get(ctx);
103 n1 = BN_CTX_get(ctx);
104 if (n1 == NULL) goto err;
106 if ((r = BN_new()) == NULL) goto err;
107 if ((b = BN_new()) == NULL) goto err;
108 if ((m = BN_new()) == NULL) goto err;
111 if (!BN_zero(n0)) goto err;
112 if (!BN_zero(n1)) goto err;
113 if (!BN_zero(r)) goto err;
114 if (!BN_zero(b)) goto err;
115 if (!BN_zero(m)) goto err;
121 if (max++ > MAX_ROUNDS) goto err; /* if p is not prime could never stop*/
122 if (!BN_add_word(m, 1)) goto err;
123 ret = BN_legendre(m, p, ctx);
124 if (ret < -1 || ret > 1) goto err;
128 if (BN_copy(n1, p) == NULL) goto err;
129 if (!BN_sub_word(n1, 1)) goto err;
131 while (!BN_is_odd(n1))
133 if (!BN_add_word(r, 1)) goto err;
134 if (!BN_rshift1(n1, n1)) goto err;
137 if (!BN_mod_exp_simple(n0, m, n1, p, ctx)) goto err;
139 if (!BN_sub_word(n1, 1)) goto err;
140 if (!BN_rshift1(n1, n1)) goto err;
141 if (!BN_mod_exp_simple(x, a, n1, p, ctx)) goto err;
143 if (!BN_mod_sqr(b, x, p, ctx)) goto err;
144 if (!BN_mod_mul(b, b, a, p, ctx)) goto err;
146 if (!BN_mod_mul(x, x, a, p, ctx)) goto err;
148 while (!BN_is_one(b))
150 if (!BN_one(m)) goto err;
151 if (!BN_mod_sqr(n1, b, p, ctx)) goto err;
152 while(!BN_is_one(n1))
154 if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;
155 if (!BN_add_word(m, 1)) goto err;
158 if (!BN_sub(r, r, m)) goto err;
159 if (!BN_sub_word(r, 1)) goto err;
160 if (r->neg) goto err;
162 if (BN_copy(n1, n0) == NULL) goto err;
163 while(!BN_is_zero(r))
165 if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;
166 if (!BN_sub_word(r, 1)) goto err;
169 if (!BN_mod_mul(n0, n1, n1, p, ctx)) goto err;
170 if (BN_copy(r, m) == NULL) goto err;
171 if (!BN_mod_mul(x, x, n1, p, ctx)) goto err;
172 if (!BN_mod_mul(b, b, n0, p, ctx)) goto err;
177 BN_mod_sqr(n0, x, p, ctx);
178 if (BN_cmp(n0, a)) goto err;
181 if (r != NULL) BN_clear_free(r);
182 if (b != NULL) BN_clear_free(b);
183 if (m != NULL) BN_clear_free(m);
187 if (r != NULL) BN_clear_free(r);
188 if (b != NULL) BN_clear_free(b);
189 if (m != NULL) BN_clear_free(m);