Schoof's algorithm: Difference between revisions

Revision as of 01:23, 1 December 2018

Revision as of 17:02, 7 January 2019

Line 23:

</math>

This powerful result, given by Hasse in 1934, simplifies our problem by narrowing down <math>\# E(\mathbb{F}_{q})</math> to a finite (albeit large) set of possibilities. Defining <math>t</math> to be <math>q + 1 - \# E(\mathbb{F}_{q})</math>, and making use of this result, we now have that computing the cardinalityvalue 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>\# 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.