mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2021-01-28, 11:34   #1
RedGolpe
 
RedGolpe's Avatar
 
Aug 2006
Monza, Italy

73 Posts
Default Number of points on elliptic curves over finite fields

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

y2x3 + 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
RedGolpe is offline   Reply With Quote
Old 2021-01-28, 11:58   #2
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

110011110012 Posts
Default

Quote:
Originally Posted by RedGolpe View Post
Can someone point me towards the right direction as to why this happens?
https://en.wikipedia.org/wiki/Hasse%...lliptic_curves
Nick is online now   Reply With Quote
Old 2021-01-28, 12:06   #3
RedGolpe
 
RedGolpe's Avatar
 
Aug 2006
Monza, Italy

73 Posts
Default

I am familiar with Hasse's theorem, but it says nothing about the specific number of points: it only gives a bound.
RedGolpe is offline   Reply With Quote
Old 2021-01-28, 13:04   #4
RedGolpe
 
RedGolpe's Avatar
 
Aug 2006
Monza, Italy

73 Posts
Default

This looks like a good answer.
RedGolpe is offline   Reply With Quote
Old 2021-01-28, 13:33   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

5×19×47 Posts
Default

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
Dr Sardonicus is offline   Reply With Quote
Old 2021-01-28, 14:03   #6
RedGolpe
 
RedGolpe's Avatar
 
Aug 2006
Monza, Italy

1118 Posts
Default

You are just missing the identity point, or the point at infinity.
RedGolpe is offline   Reply With Quote
Old 2021-01-29, 22:29   #7
Robert Holmes
 
Robert Holmes's Avatar
 
Oct 2007

11010102 Posts
Default

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.
Robert Holmes is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 10:50.

Sat Apr 17 10:50:40 UTC 2021 up 9 days, 5:31, 0 users, load averages: 1.70, 2.03, 2.17

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.