Counting points on elliptic curves

An important aspect in the study of <a href="/facts/Elliptic_curves/60jvaHSA">elliptic curves</a> is devising effective ways of counting points on the curve. There have been several approaches to do so, and the <a href="/facts/Algorithms/fnl5NmRt">algorithms</a> devised have proved to be useful tools in the study of various fields such as <a href="/facts/Number_theory/zhoa7zrc">number theory</a>, and more recently in <a href="/facts/Cryptography/e94PEVau">cryptography</a> and Digital Signature Authentication (See <a href="/facts/Elliptic_curve_cryptography/YbjcXIWk">elliptic curve cryptography</a> and <a href="/facts/Elliptic_curve_DSA/gl0mfnS1">elliptic curve DSA</a>). While in number theory they have important consequences in the solving of <a href="/facts/Diophantine_equations/mYaHp7oX">Diophantine equations</a>, with respect to cryptography, they enable us to make effective use of the difficulty of the <a href="/facts/Discrete_logarithm_problem/k8TXh5bL">discrete logarithm problem</a> (DLP) for the group 
 
 
 
 E
 (
 
 
 F
 
 
 q
 
 
 )
 
 
 {\displaystyle E(\mathbb {F} _{q})}
 
, of elliptic curves over a <a href="/facts/Finite_field/UkMGJo3m">finite field</a> 
 
 
 
 
 
 F
 
 
 q
 
 
 
 
 {\displaystyle \mathbb {F} _{q}}
 
, where q = pk and p is a prime. The DLP, as it has come to be known, is a widely used approach to <a href="/facts/Public_key_cryptography/gowoFTxS">public key cryptography</a>, and the difficulty in solving this problem determines the <a href="/facts/Level_of_security/z7BMcnjn">level of security</a> of the cryptosystem. This article covers algorithms to count points on elliptic curves over fields of large characteristic, in particular p > 3. For curves over fields of small characteristic more efficient algorithms based on p-adic methods exist.

Counting points on elliptic curves open-in-new

Counting points on elliptic curves