Bitcoin Forum
October 24, 2017, 04:19:12 AM
 News: Latest stable version of Bitcoin Core: 0.15.0.1  [Torrent]. (New!)
 Home Help Search Donate Login Register
 Pages: [1]
 Author Topic: How do you decompress a public point?  (Read 932 times)
grondilu
Legendary

Offline

Activity: 1134

 June 15, 2012, 01:33:37 PM

EDIT:  It seems that the solution is here:  Tonelli-Shanks algorithm

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.
1508818752
Hero Member

Offline

Posts: 1508818752

Ignore
 1508818752

1508818752
 Report to moderator
1508818752
Hero Member

Offline

Posts: 1508818752

Ignore
 1508818752

1508818752
 Report to moderator
1508818752
Hero Member

Offline

Posts: 1508818752

Ignore
 1508818752

1508818752
 Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1508818752
Hero Member

Offline

Posts: 1508818752

Ignore
 1508818752

1508818752
 Report to moderator
1508818752
Hero Member

Offline

Posts: 1508818752

Ignore
 1508818752

1508818752
 Report to moderator
1508818752
Hero Member

Offline

Posts: 1508818752

Ignore
 1508818752

1508818752
 Report to moderator
grondilu
Legendary

Offline

Activity: 1134

 June 20, 2012, 01:50:24 PM

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?
vuce
Sr. Member

Offline

Activity: 476

 June 20, 2012, 02:29:43 PM

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.
grondilu
Legendary

Offline

Activity: 1134

 June 20, 2012, 02:37:58 PM

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.
Vitalik Buterin
Sr. Member

Offline

Activity: 331

 June 24, 2012, 01:13:04 AM

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.

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.

Argumentum ad lunam: the fallacy that because Bitcoin's price is rising really fast the currency must be a speculative bubble and/or Ponzi scheme.
 Pages: [1]
 « previous topic next topic »