waxwing on Nostr: A curious, if admittedly useless fact about Bitcoin' elliptic curve equation: The ...
A curious, if admittedly useless fact about Bitcoin' elliptic curve equation:
The 19th century French mathematician V. A. Lebesgue (*not* he of the famous "measure"; different guy), proved that there are *no* solutions in the integers (Z) for y^2 = x^3 + 7.
(That's the equation for secp256k1, except we don't calculate over Z, the infinite set of integers).
How?
First he points out that x is odd, since 8k+7 is never a square (if this bothers you, look up "quadratic residues").
Then he rewrites: y^2 + 1 = x^3 + 8 then factors the RHS as (x+2)(x^2 - 2x + 4) and completes the square of the second factor, and claims (x-1)^2 + 3 = 3 mod 4. (Do you see why x has to be odd?). This, he says, proves there is at least one prime p that is 3 mod 4 which divides x^2 -2x + 4. But y^2 +1 = 0 mod p is not possible if the prime p is 3 mod 4 (why? see: Legendre symbol; something that gets referred to quite regularly in libsecp and related calculations, btw, e.g. in BIP340).
Source : Silverman's "Arithmetic of Elliptic Curves" IX.7
#mathematics #bitcoin #cryptography
The 19th century French mathematician V. A. Lebesgue (*not* he of the famous "measure"; different guy), proved that there are *no* solutions in the integers (Z) for y^2 = x^3 + 7.
(That's the equation for secp256k1, except we don't calculate over Z, the infinite set of integers).
How?
First he points out that x is odd, since 8k+7 is never a square (if this bothers you, look up "quadratic residues").
Then he rewrites: y^2 + 1 = x^3 + 8 then factors the RHS as (x+2)(x^2 - 2x + 4) and completes the square of the second factor, and claims (x-1)^2 + 3 = 3 mod 4. (Do you see why x has to be odd?). This, he says, proves there is at least one prime p that is 3 mod 4 which divides x^2 -2x + 4. But y^2 +1 = 0 mod p is not possible if the prime p is 3 mod 4 (why? see: Legendre symbol; something that gets referred to quite regularly in libsecp and related calculations, btw, e.g. in BIP340).
Source : Silverman's "Arithmetic of Elliptic Curves" IX.7
#mathematics #bitcoin #cryptography