# How to calculate Legendre Symbol in secp256k1 Elliptic Curve

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

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?

• You are testing the Legendre symbol on x coordinates of elliptic curve points. Legendre symbol shouldn't be used like that. You can't imply the "degree of G" by looking at x-coordinates. What are you trying to achieve ? Commented Feb 6 at 10:26
• @kelalaka but do you know if the same properties apply to elliptic curves? Commented Feb 6 at 16:32
• No, the same properties do not apply to the elliptic curves themselves (at least, if we're working with a curve with an odd number of points, or a subgroup with odd order - we almost always do). Commented Feb 7 at 13:55
• @Ruggero I was trying to find the parity of x by legendre symbol but finding the right legendre symbol is not possible for this elliptic curve Commented Feb 8 at 8:29

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.

• "And there's no substitute. Using $({\mathtt{A}_X})^{(\mathtt{P}-1)/2}$ comes out of nowhere, and does not work, as the test in the question illustrates."; actually, it cannot work. A valid $\mathtt{A}_X$ value corresponds to two elliptic curve points, and for sec256k1, one has even $x$ and the other has odd $x$ - that test has no way to determine which. Hence, there is no possible test to determine the lsbit of $x$ which examines only $\mathtt{A}_X$ Commented Feb 7 at 17:04
• Don't get me wrong but how can the legendre symbol still be so precise to always give 1 or p-1 in my example in the question? That's the natural outputs expected from the calculation of legendre symbol. Commented Feb 7 at 20:04
• @DevanshuLinux: your legendreSymbol has result $r$ such that $r≡a^{(\mathtt{P}-1)/2}\pmod{\mathtt{P}}$. Thus $r^2≡{\left(a^{(\mathtt{P}-1)/2}\right)}^2≡a^{\mathtt{P}-1}\pmod{\mathtt{P}}$. By Fermat's Little Theorem, since $\mathtt{P}$ of secp256k1 is prime, and since $a\not\equiv0\pmod{\mathtt{P}}$ for your inputs $a$ that are X coordinates on secp256k1, it holds $r^2≡1\pmod{\mathtt{P}}$. That's a second degree equation, thus it has only two solutions in the output set $[-1,p-1)$ of your legendreSymbol, and these are $-1$ and $1$. That's why your $r$ is always one of these.
– fgrieu
Commented Feb 7 at 20:17
• ohhh! @fgrieu thanks a lot, mate! Commented Feb 7 at 20:20