Post
Topic
Board Development & Technical Discussion
Re: Pubkeys with even y coordinate correspond to privKeys that are less than n/2?
by
o_e_l_e_o
on 18/09/2022, 20:09:42 UTC
What will happen if we try to "half" this public key using these methods?
You cannot divide in the normal way when working with elliptic curves. Instead you use something known as the multiplicative inverse.

The multiplicative inverse (x) of a number (y) on an elliptic curve with order n, is such that x*y mod n = 1. That is to say, the when a number is multiplied be its multiplicative inverse modulo the curve order, the answer is 1. So on a curve modulo 7, then the multiplicative inverse of 2 would be 4, since 2*4 = 8, mod 7 = 1. On a curve modulo 37, then the multiplicative inverse of 2 would be 19, since 2*19 = 38, mod 37 = 1.

To divide a number by 2, you can also multiply it by 1/2. So to divide a number by 2 on an elliptic curve, you instead multiply it by its multiplicative inverse. So on a curve modulo 37, half of 15 is 26, since 15*19 = 285, mod 37 is 26. And the reverse is also true: 26*2 = 52, mod 37 = 15.

In bitcoin, the curve order n is:
Code:
115792089237316195423570985008687907852837564279074904382605163141518161494337

This means that the multiplicative inverse is:
Code:
57896044618658097711785492504343953926418782139537452191302581570759080747169

This is because:
Code:
57896044618658097711785492504343953926418782139537452191302581570759080747169 * 2 mod 115792089237316195423570985008687907852837564279074904382605163141518161494337 = 1

So, to half a public key, you multiply the coordinates by the multiplicative inverse given above, and take the result modulo n.