Bitcoin Forum
January 18, 2017, 08:40:58 PM *
News: Latest stable version of Bitcoin Core: 0.13.2  [Torrent]. (New!)
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: How do you decompress a public point?  (Read 857 times)
grondilu
Legendary
*
Offline Offline

Activity: 1134


View Profile
June 15, 2012, 01:33:37 PM
 #1

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.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1484772058
Hero Member
*
Offline Offline

Posts: 1484772058

View Profile Personal Message (Offline)

Ignore
1484772058
Reply with quote  #2

1484772058
Report to moderator
1484772058
Hero Member
*
Offline Offline

Posts: 1484772058

View Profile Personal Message (Offline)

Ignore
1484772058
Reply with quote  #2

1484772058
Report to moderator
grondilu
Legendary
*
Offline Offline

Activity: 1134


View Profile
June 20, 2012, 01:50:24 PM
 #2



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 Offline

Activity: 476


View Profile
June 20, 2012, 02:29:43 PM
 #3

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

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

Activity: 1134


View Profile
June 20, 2012, 02:37:58 PM
 #4

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

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 Offline

Activity: 331


View Profile
June 24, 2012, 01:13:04 AM
 #5

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]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!