# How to calculate y value from ((y*y) mod prime) efficiently

i am working ECC-224 bit. can any one tell me, how to calculate y value from ((y*y) mod prime) efficiently for large bit numbers.

-
Try this –  fgrieu Mar 21 '13 at 9:03
This will take care of multiplication and this question is about modulo. –  rath Mar 21 '13 at 17:37
Mathematical routines for the NIST prime elliptic curves describes an algorithm for modular square roots as required by NIST P-224. "Routines 3.2.4, 3.2.5, 3.2.6, and 3.2.7 are all auxilliary to 3.2.8, which is used to compute square roots modulo p 224 . The method is based on an algorithm of Pocklington described in [Ber]." which refers to Bernstein - Faster square roots in annoying finite fields –  CodesInChaos Oct 1 '13 at 14:52
Duplicate of crypto.stackexchange.com/q/6518/351 –  D.W. Oct 1 '13 at 17:59

square roots in prime order groups are simple to calculate, if you know the group order $p$ and are able to factorize $p-1$ (usually this is 2 times another prime):

Calculate the inverse of 2 mod $p-1$ (with the extended euclidean algorithm): $$a = 2^{-1} \text{ mod }(p-1)$$ $$\Rightarrow y = (y^2)^{a} \text{ mod } p$$

Implementation in any language supporting big integers and modular exponentiation should be easy.

edit: ouch, poncho's comment is true, obviously. With $p-1$ being even, 2 has no inverse. But in case $p=2q+1$ with $q$ prime, this can be easily fixed: $$a= 2^{-1} \text{ mod } q\\ \Rightarrow y = \pm (y^2)^{a}$$

This is actually the same as the other suggested algorithm. However, if the totient of the prime is something more complex than $2q$ or a higher root is required, it helps to know the basic principle behind the modular square root algorithm.

-
Oops, sorry, but 2 will never have have a multiplicative inverse modulo $p-1$, because $p-1$ is always even. Se fgrieu's comment for the correct answer. –  poncho Mar 22 '13 at 19:13
In some cases (y^2) mod p does not exit. means for every (y^2) mod p there is no need to existence of y-value. In that case also it will work? –  venkat Mar 27 '13 at 11:08
it's the other way around: You can square any value, but not every value has a square root. If you have $y^2$, then $\pm y$ will be the two square roots. If you just try to calculate the root of a random value, there might not be one. –  tylo Apr 2 '13 at 9:26

By "ECC-224", I suppose that you mean "NIST curve P-224". This actually matters.

To compute the square root of $z$ modulo a prime $p$, there are several methods which depend on $p$. If $p = 3 \pmod 4$ then it suffices to compute:

$$y = z^{(p+1)/4} \pmod p$$

If $z$ is indeed a square, this will yield a value $y$, and the other square root will be $-y$ (to check whether $z$ is really a square, just compute $y^2 \pmod p$ and see if it yields back your value $z$ or not).

Now, in NIST curve P-224, computations are done modulo a prime $p$ which is such that $p = 1 \pmod 4$, and the method above does not work. You have to use Tonelli-Shanks algorithm which is slightly more complex, and, in the general case, requires knowledge of a value modulo $p$ which is not a square (half o values modulo $p$ are not squares, so finding one is not hard, but this is enough to make the algorithm, in all generality, probabilistic).

-