libcrypto/bn/bn_mod_sqrt.c

88     const BIGNUM *p, BN_CTX *ctx)
114     BN_CTX *ctx)
119 	BN_CTX_start(ctx);
121 	if ((n = BN_CTX_get(ctx)) == NULL)
131 	if (!BN_mod_exp_ct(out_sqrt, a, n, p, ctx))
137 	BN_CTX_end(ctx);
148     BN_CTX *ctx)
153 	BN_CTX_start(ctx);
155 	if ((b = BN_CTX_get(ctx)) == NULL)
157 	if ((i = BN_CTX_get(ctx)) == NULL)
159 	if ((n = BN_CTX_get(ctx)) == NULL)
161 	if ((tmp = BN_CTX_get(ctx)) == NULL)
170 	if (!BN_mod_lshift1(tmp, a, p, ctx))
174 	if (!BN_mod_exp_ct(b, tmp, n, p, ctx))
178 	if (!BN_mod_sqr(i, b, p, ctx))
180 	if (!BN_mod_mul(i, tmp, i, p, ctx))
186 	if (!BN_mod_mul(out_sqrt, a, b, p, ctx))
188 	if (!BN_mod_mul(out_sqrt, out_sqrt, i, p, ctx))
194 	BN_CTX_end(ctx);
210     const BIGNUM *p, BN_CTX *ctx)
212 	switch (BN_kronecker(n, p, ctx)) {
238     const BIGNUM *q, BN_CTX *ctx)
244 	BN_CTX_start(ctx);
246 	if ((n = BN_CTX_get(ctx)) == NULL)
248 	if ((p_abs = BN_CTX_get(ctx)) == NULL)
254 		if (!bn_mod_sqrt_n_is_non_residue(&is_non_residue, n, p, ctx))
267 		if (!bn_mod_sqrt_n_is_non_residue(&is_non_residue, n, p, ctx))
286 	if (!BN_mod_exp_ct(out_generator, n, q, p, ctx))
298 	BN_CTX_end(ctx);
313     const BIGNUM *p, const BIGNUM *q, BN_CTX *ctx)
318 	BN_CTX_start(ctx);
320 	if ((k = BN_CTX_get(ctx)) == NULL)
328 	if (!BN_mod_exp_ct(x, a, k, p, ctx))
332 	if (!BN_mod_sqr(b, x, p, ctx))
334 	if (!BN_mod_mul(b, a, b, p, ctx))
338 	if (!BN_mod_mul(x, a, x, p, ctx))
344 	BN_CTX_end(ctx);
356     const BIGNUM *p, int r, BN_CTX *ctx)
362 	BN_CTX_start(ctx);
364 	if ((x = BN_CTX_get(ctx)) == NULL)
390 		if (!BN_mod_sqr(x, x, p, ctx))
407 	BN_CTX_end(ctx);
421     const BIGNUM *p, int m, int r, BN_CTX *ctx)
426 	BN_CTX_start(ctx);
428 	if ((t = BN_CTX_get(ctx)) == NULL)
434 	if (!BN_mod_exp_ct(t, y, t, p, ctx))
438 	if (!BN_mod_mul(x, x, t, p, ctx))
442 	if (!BN_mod_sqr(y, t, p, ctx))
446 	if (!BN_mod_mul(b, b, y, p, ctx))
452 	BN_CTX_end(ctx);
459     BN_CTX *ctx)
465 	BN_CTX_start(ctx);
467 	if ((b = BN_CTX_get(ctx)) == NULL)
469 	if ((q = BN_CTX_get(ctx)) == NULL)
471 	if ((x = BN_CTX_get(ctx)) == NULL)
473 	if ((y = BN_CTX_get(ctx)) == NULL)
486 	if (!bn_mod_sqrt_find_sylow_generator(y, p, q, ctx))
492 	if (!bn_mod_sqrt_tonelli_shanks_initialize(b, x, a, p, q, ctx))
528 		if (!bn_mod_sqrt_tonelli_shanks_find_exponent(&m, b, p, r, ctx))
534 		if (!bn_mod_sqrt_tonelli_shanks_update(b, x, y, p, m, r, ctx))
559 	BN_CTX_end(ctx);
569 bn_mod_sqrt_normalize(BIGNUM *sqrt, const BIGNUM *p, BN_CTX *ctx)
574 	BN_CTX_start(ctx);
576 	if ((x = BN_CTX_get(ctx)) == NULL)
590 	BN_CTX_end(ctx);
601     BN_CTX *ctx)
606 	BN_CTX_start(ctx);
608 	if ((x = BN_CTX_get(ctx)) == NULL)
611 	if (!BN_mod_sqr(x, sqrt_a, p, ctx))
622 	BN_CTX_end(ctx);
629     BN_CTX *ctx)
637 	BN_CTX_start(ctx);
639 	if ((a_mod_p = BN_CTX_get(ctx)) == NULL)
641 	if ((sqrt = BN_CTX_get(ctx)) == NULL)
644 	if (!BN_nnmod(a_mod_p, a, p, ctx))
647 	if (!bn_mod_sqrt_trivial_cases(&done, sqrt, a_mod_p, p, ctx))
659 	if ((kronecker = BN_kronecker(a_mod_p, p, ctx)) == -2)
670 		if (!bn_mod_sqrt_p_is_3_mod_4(sqrt, a_mod_p, p, ctx))
673 		if (!bn_mod_sqrt_p_is_5_mod_8(sqrt, a_mod_p, p, ctx))
676 		if (!bn_mod_sqrt_p_is_1_mod_8(sqrt, a_mod_p, p, ctx))
684 	if (!bn_mod_sqrt_normalize(sqrt, p, ctx))
688 	if (!bn_mod_sqrt_verify(a_mod_p, sqrt, p, ctx))
697 	BN_CTX_end(ctx);
703 BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
712 	if (!bn_mod_sqrt_internal(out_sqrt, a, p, ctx))