How to calculate Legendre Symbol in secp256k1 Elliptic Curve

Question

In this answer by fkraiem he proves a property that:

$a^{(p-1)/2} = 1$ if and only if $x$ is even

But this doesn't seem to work in my test with the secp256k1 Elliptic Curve. Here is my Python 2 code:

ECLib.py:

P = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
GPoint = (int(Gx),int(Gy))
Acurve = 0

def legendreSymbol(a,p=P): #Legendre Symbol Calculation
    ls = pow(a, (p - 1) / 2, p)
    if ls == p - 1: return -1
    else: return ls

def modinv(a,n): # Extended Euclidean Algorithm
    lm, hm = 1,0
    low, high = a%n,n
    while low > 1:
        ratio = high/low
        nm = hm - lm * ratio
        new = high - low * ratio
        hm = lm
        high = low
        lm = nm
        low = new
    return lm % n

def ECadd(xp,yp,xq=Gx,yq=Gy): # EC point addition
    m = ((yq-yp) * modinv(xq-xp,P))%P
    xr = (m*m-xp-xq)%P
    yr = (m*(xp-xr)-yp)%P
    return (xr,yr)

def ECdouble(xp,yp): # EC point doubling
    LamNumer = 3*xp*xp+Acurve
    LamDenom = 2*yp
    Lam = (LamNumer * modinv(LamDenom,P)) % P
    xr = (Lam*Lam-2*xp) % P
    yr = (Lam*(xp-xr)-yp) % P
    return (xr,yr)

Test.py:

import ECLib

Point = (ECLib.Gx, ECLib.Gy)
Deg = 1

print 'Degree of G \t\t\t Legendre Symbol'

for i in range(8):
  Point = ECLib.ECdouble(Point[0], Point[1])
  Deg = Deg * 2
  print '\t' + str(Deg) + '\t\t\t\t' + str(ECLib.legendreSymbol(Point[0]))

Output:

Degree of G                      Legendre Symbol
        2                               1
        4                               -1
        8                               -1
        16                              1
        32                              -1
        64                              -1
        128                             1
        256                             1

As I am doubling, the power of G is always even, so Legendre Symbol should always be 1 but that is not the case. Why is that?

Answer 1

This answer extends @poncho's comment.

The property “ $a^{(p-1)/2}=1\text{ if and only if }x\text{ is even}$ ” stated in the answer linked in the question is for the multiplicative group modulo an odd prime $p$, and assumes $a=g^x$ with $g$ a generator of that group. The group, thus generator $g$, has even order $p-1$ (the $-1$ is because $0$ is not a member of the group). That even order of $g$ is essential for proving the property.

The present question is for an elliptic curve group over prime field $\mathbb F_\mathtt{P}$ of prime order $\mathtt{N}$, and a generator $\mathtt{G}$ (all given numerically). That happens to be secp256k1. Customarily, elliptic curve groups are noted additively rather than multiplicatively. Indeed $A=x\,\mathtt{G}$ in the elliptic curve group parallels $a=g^x$ in multiplicative group modulo $p$. The point at infinity $\mathcal O$ parallels $1$. $G$ parallels $g$. $N$ parallels $p-1$.

The property “ $((N-1)/2)\,\mathtt{A}=\mathcal O\text{ if and only if }x\text{ is even}$ ” would parallel $a^{(p-1)/2}=1$ if $N$ was even. But it's not! That would require a different elliptic curve (and then, for a curve used in ECDSA, $G$ would be chosen of prime order, thus not a generator of the whole curve).

And there's no substitute. Using ${(\mathtt{A}_X)}^{(\mathtt{P}-1)/2}=1$ comes out of nowhere, and does not work, as the test in the question illustrates (and @poncho generalizes in another comment).

For the parameters of secp256k1, there is no known computationally feasible method to guess the parity of $x$ from $x\,\mathtt{G}$ alone for random $x\in[1,\mathtt{N})$. Argument: If there was a practical method for this consistently working significantly better than a random guess, that method could demonstrably be leveraged to compute the private key matching any public key.