1 #include "tommath_private.h"
2 #ifdef BN_MP_SQRTMOD_PRIME_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
4 /* SPDX-License-Identifier: Unlicense */
6 /* Tonelli-Shanks algorithm
7 * https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm
8 * https://gmplib.org/list-archives/gmp-discuss/2013-April/005300.html
12 mp_err mp_sqrtmod_prime(const mp_int *n, const mp_int *prime, mp_int *ret)
16 mp_int t1, C, Q, S, Z, M, T, R, two;
19 /* first handle the simple cases */
20 if (mp_cmp_d(n, 0uL) == MP_EQ) {
24 if (mp_cmp_d(prime, 2uL) == MP_EQ) return MP_VAL; /* prime must be odd */
25 if ((err = mp_kronecker(n, prime, &legendre)) != MP_OKAY) return err;
26 if (legendre == -1) return MP_VAL; /* quadratic non-residue mod prime */
28 if ((err = mp_init_multi(&t1, &C, &Q, &S, &Z, &M, &T, &R, &two, NULL)) != MP_OKAY) {
32 /* SPECIAL CASE: if prime mod 4 == 3
33 * compute directly: err = n^(prime+1)/4 mod prime
34 * Handbook of Applied Cryptography algorithm 3.36
36 if ((err = mp_mod_d(prime, 4uL, &i)) != MP_OKAY) goto cleanup;
38 if ((err = mp_add_d(prime, 1uL, &t1)) != MP_OKAY) goto cleanup;
39 if ((err = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup;
40 if ((err = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup;
41 if ((err = mp_exptmod(n, &t1, prime, ret)) != MP_OKAY) goto cleanup;
46 /* NOW: Tonelli-Shanks algorithm */
48 /* factor out powers of 2 from prime-1, defining Q and S as: prime-1 = Q*2^S */
49 if ((err = mp_copy(prime, &Q)) != MP_OKAY) goto cleanup;
50 if ((err = mp_sub_d(&Q, 1uL, &Q)) != MP_OKAY) goto cleanup;
54 while (MP_IS_EVEN(&Q)) {
55 if ((err = mp_div_2(&Q, &Q)) != MP_OKAY) goto cleanup;
57 if ((err = mp_add_d(&S, 1uL, &S)) != MP_OKAY) goto cleanup;
61 /* find a Z such that the Legendre symbol (Z|prime) == -1 */
65 if ((err = mp_kronecker(&Z, prime, &legendre)) != MP_OKAY) goto cleanup;
66 if (legendre == -1) break;
67 if ((err = mp_add_d(&Z, 1uL, &Z)) != MP_OKAY) goto cleanup;
71 if ((err = mp_exptmod(&Z, &Q, prime, &C)) != MP_OKAY) goto cleanup;
72 /* C = Z ^ Q mod prime */
73 if ((err = mp_add_d(&Q, 1uL, &t1)) != MP_OKAY) goto cleanup;
74 if ((err = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup;
75 /* t1 = (Q + 1) / 2 */
76 if ((err = mp_exptmod(n, &t1, prime, &R)) != MP_OKAY) goto cleanup;
77 /* R = n ^ ((Q + 1) / 2) mod prime */
78 if ((err = mp_exptmod(n, &Q, prime, &T)) != MP_OKAY) goto cleanup;
79 /* T = n ^ Q mod prime */
80 if ((err = mp_copy(&S, &M)) != MP_OKAY) goto cleanup;
85 if ((err = mp_copy(&T, &t1)) != MP_OKAY) goto cleanup;
88 if (mp_cmp_d(&t1, 1uL) == MP_EQ) break;
89 if ((err = mp_exptmod(&t1, &two, prime, &t1)) != MP_OKAY) goto cleanup;
93 if ((err = mp_copy(&R, ret)) != MP_OKAY) goto cleanup;
97 if ((err = mp_sub_d(&M, i, &t1)) != MP_OKAY) goto cleanup;
98 if ((err = mp_sub_d(&t1, 1uL, &t1)) != MP_OKAY) goto cleanup;
99 if ((err = mp_exptmod(&two, &t1, prime, &t1)) != MP_OKAY) goto cleanup;
100 /* t1 = 2 ^ (M - i - 1) */
101 if ((err = mp_exptmod(&C, &t1, prime, &t1)) != MP_OKAY) goto cleanup;
102 /* t1 = C ^ (2 ^ (M - i - 1)) mod prime */
103 if ((err = mp_sqrmod(&t1, prime, &C)) != MP_OKAY) goto cleanup;
104 /* C = (t1 * t1) mod prime */
105 if ((err = mp_mulmod(&R, &t1, prime, &R)) != MP_OKAY) goto cleanup;
106 /* R = (R * t1) mod prime */
107 if ((err = mp_mulmod(&T, &C, prime, &T)) != MP_OKAY) goto cleanup;
108 /* T = (T * C) mod prime */
114 mp_clear_multi(&t1, &C, &Q, &S, &Z, &M, &T, &R, &two, NULL);