2  *  Copyright (C) 2017 - This file is part of libecc project
7  *      Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr>
14  *  See LICENSE file at the root folder of the project.
23  *   Legendre(a) = a^((p-1)/2) (p) = { -1, 0, 1 }
37 	ret = fp_init(&pow, a->ctx); EG(ret, err);  in legendre()
38 	ret = fp_init(&one, a->ctx); EG(ret, err);  in legendre()
44 	ret = fp_init(&pow, a->ctx); EG(ret, err);  in legendre()
45 	ret = fp_init(&one, a->ctx); EG(ret, err);  in legendre()
51 	/* Compute the exponent (p-1)/2  in legendre()
55 	ret = nn_dec(&exp, &(a->ctx->p)); EG(ret, err);  in legendre()
58 	/* Compute a^((p-1)/2) in Fp using our fp_pow  in legendre()
70 		ret = -1;  in legendre()
83  * We implement the Tonelli-Shanks algorithm for finding
84  * square roots (quadratic residues) modulo a prime number,
91  *   All   ≡   are taken to mean   (mod p)   unless stated otherwise.
93  *       Step 0. Check that n is indeed a square  : (n | p) must be ≡ 1
94  *       Step 1. [Factors out powers of 2 from p-1] Define q -odd- and s such as p-1 = q * 2^s
95  *           - if s = 1 , i.e p ≡ 3 (mod 4) , output the two solutions r ≡ +/- n^((p+1)/4) .
96  *       Step 2. Select a non-square z such as (z | p) = -1 , and set c ≡ z^q .
99  *           - if t ≡ 1 output r, p-r .
100  *           - Otherwise find, by repeated squaring, the lowest i , 0 < i < m , such as t^(2^i) ≡ 1
101  *           - Let b ≡ c^(2^(m-i-1)), and set r ≡ r*b, t ≡ t*b^2 , c ≡ b^2 and m = i.
106  * The function returns 0 on success, -1 on error (in which case values of sqrt1 and sqrt2
129 	ret = fp_init(&z, n->ctx); EG(ret, err);  in fp_sqrt()
130 	ret = fp_init(&t, n->ctx); EG(ret, err);  in fp_sqrt()
131 	ret = fp_init(&b, n->ctx); EG(ret, err);  in fp_sqrt()
132 	ret = fp_init(&r, n->ctx); EG(ret, err);  in fp_sqrt()
133 	ret = fp_init(&c, n->ctx); EG(ret, err);  in fp_sqrt()
134 	ret = fp_init(&one_fp, n->ctx); EG(ret, err);  in fp_sqrt()
135 	ret = fp_init(&tmp_fp, n->ctx); EG(ret, err);  in fp_sqrt()
141 	ret = fp_init(sqrt1, _n->ctx); EG(ret, err);  in fp_sqrt()
142 	ret = fp_init(sqrt2, _n->ctx); EG(ret, err);  in fp_sqrt()
149 	/* If our p prime of Fp is 2, then return the input as square roots */  in fp_sqrt()
150 	ret = nn_cmp(&(_n->ctx->p), &two_nn, &cmp); EG(ret, err);  in fp_sqrt()
158 	/* Square root of 0 is 0 */  in fp_sqrt()
166 	/* Step 0. Check that n is indeed a square  : (n | p) must be ≡ 1 */  in fp_sqrt()
168 		/* a is not a square */  in fp_sqrt()
169 		ret = -1;  in fp_sqrt()
172 	/* Step 1. [Factors out powers of 2 from p-1] Define q -odd- and s such as p-1 = q * 2^s */  in fp_sqrt()
175 	/* q = p - 1 */  in fp_sqrt()
176 	ret = nn_copy(&q, &(_n->ctx->p)); EG(ret, err);  in fp_sqrt()
189 	/* - if s = 1 , i.e p ≡ 3 (mod 4) , output the two solutions r ≡ +/- n^((p+1)/4) . */  in fp_sqrt()
192 		ret = nn_inc(&tmp_nn, &(_n->ctx->p)); EG(ret, err);  in fp_sqrt()
199 	/* Step 2. Select a non-square z such as (z | p) = -1 , and set c ≡ z^q . */  in fp_sqrt()
201 	while (legendre(&z) != -1) {  in fp_sqrt()
215 		/* - if t ≡ 1 output r, p-r . */  in fp_sqrt()
223 		/* - Otherwise find, by repeated squaring, the lowest i , 0 < i < m , such as t^(2^i) ≡ 1 */  in fp_sqrt()
236 				ret = -2;  in fp_sqrt()
240 		/* - Let b ≡ c^(2^(m-i-1)), and set r ≡ r*b, t ≡ t*b^2 , c ≡ b^2 and m = i. */  in fp_sqrt()