Number of points on elliptic curves over finite fields

RedGolpe · 2021-01-28, 11:34

Hi all, I noticed that for elliptic curves of the form

y² ≡ x³ + a (mod p)

sometimes the number of points is always p+1 for any choice of a. This seems to be the case for all p ≡ 5 (mod 6).

Moreover, when this does not happen, i.e., for p ≡ 1 (mod 6), it looks like there are exactly zero curves of such form where the number of points is p+1.

Can someone point me towards the right direction as to why this happens?

Nick · 2021-01-28, 11:58

Quote:

Originally Posted by RedGolpe

Can someone point me towards the right direction as to why this happens?

https://en.wikipedia.org/wiki/Hasse%...lliptic_curves

RedGolpe · 2021-01-28, 12:06

I am familiar with Hasse's theorem, but it says nothing about the specific number of points: it only gives a bound.

RedGolpe · 2021-01-28, 13:04

This looks like a good answer.

Dr Sardonicus · 2021-01-28, 13:33

If p == 5 (mod 6) then gcd(3, p-1) = 1, so x -> x^3 (mod p) is invertible. In fact, x -> x^((2p-1)/3) (mod p) is the inverse map.

Thus if p == 5 (mod 6), x^3 is "any residue mod p" and x^3 + a is "any residue mod p."

If x^3 + a is one of the (p-1)/2 quadratic non-residues (mod p) there are no points (x, y) on the curve y^2 = x^3 + a.

If x^3 + a is one of the (p-1)/2 nonzero squares (mod p) there are two points (x,y) and (x, -y) on the curve.

If x^3 + a = 0 (mod p) there is one point (x, 0) on the curve.

That makes p points in all. I seem to be missing one point.

RedGolpe · 2021-01-28, 14:03

You are just missing the identity point, or the point at infinity.

Robert Holmes · 2021-01-29, 22:29

The key term here is supersingular elliptic curves. For p = 2 mod 3, any curve of the form y^2 = x^3 + B is supersingular, p > 3.

Another common case is p = 3 mod 4, in which case y^2 = x^3 + x is also known to be supersingular.

2021-01-28, 11:34	#1
RedGolpe Aug 2006 Monza, Italy 73₁₀ Posts	Number of points on elliptic curves over finite fields Hi all, I noticed that for elliptic curves of the form y² ≡ x³ + a (mod p) sometimes the number of points is always p+1 for any choice of a. This seems to be the case for all p ≡ 5 (mod 6). Moreover, when this does not happen, i.e., for p ≡ 1 (mod 6), it looks like there are exactly zero curves of such form where the number of points is p+1. Can someone point me towards the right direction as to why this happens? Last fiddled with by RedGolpe on 2021-01-28 at 11:46 Reason: more info

2021-01-28, 13:33	#5
Dr Sardonicus Feb 2017 Nowhere 4,643 Posts	If p == 5 (mod 6) then gcd(3, p-1) = 1, so x -> x^3 (mod p) is invertible. In fact, x -> x^((2p-1)/3) (mod p) is the inverse map. Thus if p == 5 (mod 6), x^3 is "any residue mod p" and x^3 + a is "any residue mod p." If x^3 + a is one of the (p-1)/2 quadratic non-residues (mod p) there are no points (x, y) on the curve y^2 = x^3 + a. If x^3 + a is one of the (p-1)/2 nonzero squares (mod p) there are two points (x,y) and (x, -y) on the curve. If x^3 + a = 0 (mod p) there is one point (x, 0) on the curve. That makes p points in all. I seem to be missing one point. Last fiddled with by Dr Sardonicus on 2021-01-28 at 13:44 Reason: xifnig posty

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Finite fields of Mersenne prime order	toktarev	Math	1	2019-12-05 14:43
Need help with elliptic curves...	WraithX	Math	12	2010-09-29 09:34
On the basis of finite fields	meng_luckywolf	Math	6	2007-12-13 04:21
Elliptic factoring with points NOT on the curve	bongomongo	Factoring	5	2006-12-21 18:19
Elliptic curves in NFS	otkachalka	Factoring	5	2005-11-20 12:22

2021-01-28, 12:06	#3
RedGolpe Aug 2006 Monza, Italy 73 Posts	I am familiar with Hasse's theorem, but it says nothing about the specific number of points: it only gives a bound.

2021-01-28, 13:04	#4
RedGolpe Aug 2006 Monza, Italy 73 Posts	This looks like a good answer.

2021-01-28, 14:03	#6
RedGolpe Aug 2006 Monza, Italy 73 Posts	You are just missing the identity point, or the point at infinity.

2021-01-29, 22:29	#7
Robert Holmes Oct 2007 6A₁₆ Posts	The key term here is supersingular elliptic curves. For p = 2 mod 3, any curve of the form y^2 = x^3 + B is supersingular, p > 3. Another common case is p = 3 mod 4, in which case y^2 = x^3 + x is also known to be supersingular.