Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
3  
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

2 Answers 2

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

share|improve this answer

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.

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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