From
https://en.wikipedia.org/wiki/Quadratic_residue and
http://mersennewiki.org/index.php/Modular_Square_Root, if
r^2 = a mod m where m = 3 mod 4 (as
secp256k1's p does)
then
r = +-a^((m+1)/4) mod m
So:
y^2 mod p = (x^3 + 7) mod p
y mod p = +-(x^3 + 7)^((p+1)/4) mod p
So calculate (x^3 + 7)^((p+1)/4) mod p, and if the parity of the first answer you get is wrong, then take the negative of that answer (since we're working modulo an odd number, taking the negative will flip the even/odd parity).
Just for fun, here's some Python code that'll do the calculation in the blink of an eye, preset to work on the public key of (the random) private key 55255657523dd1c65a77d3cb53fcd050bf7fc2c11bb0bb6edabdbd41ea51f641
def pow_mod(x, y, z):
"Calculate (x ** y) % z efficiently."
number = 1
while y:
if y & 1:
number = number * x % z
y >>= 1
x = x * x % z
return number
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
compressed_key = '0314fc03b8df87cd7b872996810db8458d61da8448e531569c8517b469a119d267'
y_parity = int(compressed_key[:2]) - 2
x = int(compressed_key[2:], 16)
a = (pow_mod(x, 3, p) + 7) % p
y = pow_mod(a, (p+1)//4, p)
if y % 2 != y_parity:
y = -y % p
uncompressed_key = '04{:x}{:x}'.format(x, y)
print(uncompressed_key)
