Bitcoin Forum
March 30, 2017, 02:49:57 PM *
News: Latest stable version of Bitcoin Core: 0.14.0  [Torrent]. (New!)
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: How do you decompress a public point?  (Read 869 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.
1490885397
Hero Member
*
Offline Offline

Posts: 1490885397

View Profile Personal Message (Offline)

Ignore
1490885397
Reply with quote  #2

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

Posts: 1490885397

View Profile Personal Message (Offline)

Ignore
1490885397
Reply with quote  #2

1490885397
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!