Schoof's algorithm: Difference between revisions

Revision as of 00:34, 8 January 2018

Revision as of 12:39, 26 April 2018

Line 16:

==Hasse's theorem==

{{main|Hasse's theorem on elliptic curves}}

Hasse's theorem states that if <math>E/\mathbb{F}_{q}</math> is an elliptic curve over the finite field <math>\mathbb{F}_{q}</math>, then <math>\sharp# E(\mathbb{F}_q)</math> satisfies

: <math>

\mid q + 1 - \sharp# E(\mathbb{F}_{q}) \mid \leq 2\sqrt{q}.

</math>

This powerful result, given by Hasse in 1934, simplifies our problem by narrowing down <math>\sharp# E(\mathbb{F}_{q})</math> to a finite (albeit large) set of possibilities. Defining <math>t</math> to be <math>q + 1 - \sharp# E(\mathbb{F}_{q})</math>, and making use of this result, we now have that computing the cardinality of <math>t</math> modulo <math>N</math> where <math>N > 4\sqrt{q}</math>, is sufficient for determining <math>t</math>, and thus <math>\sharp# E(\mathbb{F}_{q})</math>. While there is no efficient way to compute <math>t \pmod N</math> directly for general <math>N</math>, it is possible to compute <math>t \pmod l</math> for <math>l</math> a small prime, rather efficiently. We choose <math>S=\{l_1,l_2,...,l_r\}</math> to be a set of distinct primes such that <math>\prod l_i = N > 4\sqrt{q}</math>. Given <math>t \pmod {l_i}</math> for all <math>l_i\in S</math>, the [[Chinese remainder theorem]] allows us to compute <math>t \pmod N</math>.

In order to compute <math>t \pmod l</math> for a prime <math>l \neq p</math>, we make use of the theory of the Frobenius endomorphism <math>\phi</math> and [[division polynomials]]. Note that considering primes <math>l \neq p</math> is no loss since we can always pick a bigger prime to take its place to ensure the product is big enough. In any case Schoof's algorithm is most frequently used in addressing the case <math>q=p</math> since there are more efficient, so called <math>p</math> adic algorithms for small-characteristic fields.