Bitcoin Forum

EDIT:  It seems that the solution is here:  Tonelli-Shanks algorithm (http://en.wikipedia.org/wiki/Shanks0.000000E+002)


So I've learnt about compressed public points recently and I have a question:  How do you decompress one?

I mean, with a compressed public point you have the X position, and a boolean telling you whether Y is odd or even.

So I thought:

« ok I just have to compute the square root of X^3 + aX+ b, ie the square root of X^3 + 7 »,

but since this is modular arithmetics, is it only possible??  I thought quite a bit about it and I could not find the beginning of an idea.

I know I could have a look a the source code of openssl, but if someone could give me a quick explanation, that would spare me some hassle.

In the Tonelli-Shanks article mentionned above, it is said that when p = 3 [mod 4], then the answer is simply:

n^((p+1)/4)

[Remainder:  we want to compute the p-modular square root of n]

It's cool because precisely with secp256k1 we are in this particular case.

Yet I confess I don't understand why this relation is true.

If p = 3 [mod 4], then there is q such that:   p = 4*q + 3

Ok so (p+1)/4 =  (4*q+4)/4 = q+1.

So:

n^((p+1)/4) = n^(q+1)

Ok that's great.  But so what??   I don't see how this shows me that (n^((p+1)/4))  ^ 2 = n (which is what we want).


I can live without understanding that.  But it's kind of annoying.  Can anyone enlighten me?

 (n^((p+1)/4))  ^ 2 =  (n^((p+1)/2)) =  (n^((p-1 + 2)/2)) =  (n^((p-1)/2))*n =(*) n

(*) By the definition of legendre symbol, if n is a quadratic residue (which in this case it is), (n^((p-1)/2)) = 1 (mod p) (proving this is good practice :))

The reason p = 3 (mod 4) has to hold is so that (p+1)/4 is an integer.

Ok, so it was not obvious and required some understanding of Legendre symbol, Euler criterium and stuff like that, right?

I had no reason to be ashamed of not understanding.  That's a relief.

Thanks anyway.

PS.  jeez, modular arithmetics is tough.

Fuller explanation:

When you have powers of an integer modulo a certain other integer, those powers always go in a cycle. For example, let n = 3,p = 10, and the notation (3,k,10) = 3 ^ k mod 10.

(3,1,10) = 3
(3,2,10) = [(3,1,10) * 3] mod 10 = (3*3) mod 10 = 9
(3,3,10) = [(3,2,10) * 3] mod 10 = (9*3) mod 10 = 7
(3,4,10) = [(3,3,10) * 3] mod 10 = (7*3) mod 10 = 1
(3,5,10) = [(3,4,10) * 3] mod 10 = (1*3) mod 10 = 3
(3,6,10) = [(3,5,10) * 3] mod 10 = (3*3) mod 10 = 9
(3,7,10) = [(3,6,10) * 3] mod 10 = (9*3) mod 10 = 7
(3,8,10) = [(3,7,10) * 3] mod 10 = (7*3) mod 10 = 1

And so on.

It so turns out that for prime numbers the cycle length has to be a factor of p-1, so n^(p-1) mod p = 1, although it can also equal 1 at one or more intermediate points. You can find proofs of this here: http://en.wikipedia.org/wiki/Proofs_of_Fermat's_little_theorem#Necklaces (http://en.wikipedia.org/wiki/Proofs_of_Fermat's_little_theorem#Necklaces).

For example, for n = 3, p = 11, the cycle looks like this:

3,9,5,4,1,3,9,5,4,1,3...

Notice how 3^10 mod 11 = 1, although 3^5 mod 11 also = 1. For n = 6, p = 11, the cycle goes:

6,3,7,9,10,5,8,4,2,1,6...

The criterion for a number to cycle in (p-1)/2 steps rather than (p-1) is that the number has to be a quadratic residue, meaning that it has to be a square of another number modulo p. For p=11, for example, 3 = 6^2 mod 11 (since 6^2 = 36, and the nearest multiple of 11 below 36 is 33). The reason why this is the case is simple: if n is a quadratic residue, it can be represented as k^2 mod p. Since k has to cycle every p-1 steps and each step of n corresponds to 2 steps of k, n can cover the cycle in (p-1)/2 steps.

Now, on to the main problem.

We are trying to find the square root of n mod p. What this means is that we want to find some number k such that k^2 mod p = n. However, we know that this k exists, so n must be a quadratic residue. This means that the cycle length of n is (p-1)/2, meaning that:

n ^ [(p-1)/2] mod p = 1

n ^ [(p-1)/2 + 1] mod p = n

n ^ [(p+1)/2] mod p = n

If (p+1)/2 is itself an even number, then we can go exactly (p+1)/4 steps to get k. Now, what is the value of k^2 mod p?

k^2 mod p = {n ^ [(p+1)/4] } ^ 2 mod p = {n ^ [(p+1)/2] } mod p = n

And there you have it, you've found a value k that satisfies the condition that makes it a square root of n. The only condition for this algorithm is that (p+1) / 2 is even, ie. p+1 is a multiple of 4, or p mod 4 = 3.