point_counting
system:sage


<h2> A naive point counting algorithm </h2>

{{{id=8|
def point_count(E):
    '''Point counting algorithm using legendre symbols.
       Assume E is in form y^2 = x^3 + ax + b.
    '''
    
    F = E.base_field()
    R.<X> = PolynomialRing(F)
    f = X^3 + E.a4()*X + E.a6()   # defining equation for E
    
    n = 1                    # have to count the point at infinity!
    for x in F:
        w = f(x)
        if w == 0:
            n += 1           # only 1 possible y value when f(x) = 0
        elif w.is_square():
            n += 2           # 2 possible y values when f(x) is a square
    return n
///
}}}

Let's test it on a random curve:

{{{id=2|
def random_curve(p):
    F = GF(p)
    return EllipticCurve([F.random_element(),F.random_element()])
///
}}}

{{{id=19|
E = random_curve(31); E
///
}}}

{{{id=20|
point_count(E)
///
}}}

Did it work?  Here's a list of all the points on $E$:

{{{id=21|
L = E.points(); L
///
}}}

{{{id=22|
len(L)
///
}}}

It worked!

<p>However, this method of counting points is very slow.

{{{id=9|
p = next_prime(123456);
E = random_curve(p); E
///
}}}

{{{id=13|
time point_count(E)
///
}}}

The built in method <tt>point_count</tt>, which uses Schoof's algorithm (Washington section 4.5), is <b>much</b> faster:

{{{id=15|
time E.count_points()
///
}}}

In fact, variations of Schoof's algorithm have been used to count points on curves over fields with more than 5000 digits!  See <a href="http://math.mit.edu/~drew/SEArecords.html">elliptic curve point counting record</a>.

<h2>How many points are on a random curve? </h2>

{{{id=1|
p = next_prime(10^50); p
///
}}}

{{{id=3|
E = random_curve(p); E
///
}}}

{{{id=4|
E.count_points()
///
}}}

{{{id=5|
for i in range(10):
   E = random_curve(p)
   print E.count_points()
///
}}}

It looks like the number of points is <i>really really</i> close to the field size -- roughly the first half of the digits are the same (modulo carries).  <b>Hasse's theorem</b> says that this is always the case.

{{{id=18|

///
}}}