5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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).

|improve this answer|||||
$\endgroup$
1
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – poncho Mar 22 '13 at 19:13
  • $\begingroup$ 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? $\endgroup$ – venkat Mar 27 '13 at 11:08
  • $\begingroup$ 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. $\endgroup$ – tylo Apr 2 '13 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.