Primality testing and Abelian varieties over finite fields (Q1189509)

In this monograph the authors present the first random polynomial time primality test. In other words, they describe an algorithm that decides whether a given integer \(n\) is prime or composite and this algorithm runs in time bounded by \(\log^ \alpha n\) for some \(\alpha>0\). The algorithm uses ``random'' numbers. It is not guaranteed to give an answer, but there is a positive chance that it will and if it does so, the answer is certainly correct. The algorithm is related to a polynomial time primality test of \textit{S. Goldwasser} and \textit{J. Kilian} [Theory of Computing, Proc. 18th ACM Symp. (ACM, 1991)]. Given \(n\), which we may assume to be a large integer which is probably prime, Goldwasser and Kilian pick random elliptic curves \(E\) over \(\mathbb Z/n\mathbb Z\) and they calculate the order of the set of points \(E(\mathbb Z/n\mathbb Z)\). This is done by means of an algorithm due to \textit{R. Schoof} [Math. Comput. 44, 483--494 (1985; Zbl 0579.14025)], which for prime \(n\) runs in (deterministic) polynomial time. It is easy to see that if an elliptic curve \(E\) is found for which the order of the group \(E(\mathbb Z/n\mathbb Z)\) is \(2q\) with \(q\) prime, then \(n\) must be prime as well. In this way, proving the primality of \(n\) is reduced to proving the primality of \(q\). Since, if \(n\) is prime, the number \(q\) is approximately equal to \(n/2\), one can now complete the proof ``inductively''. At present, one cannot show the algorithm to work for all primes however. This is caused by the fact that with the present knowledge of analytic number theory, one cannot prove that one is likely to find an elliptic curve \(E\) with \(\#E(\mathbb Z/n\mathbb Z)=2q\) with \(q\) prime. This problem is avoided by the present authors by exploiting abelian varieties of dimension 2. Given \(n\), the authors pick random curves of genus 2 over \(\mathbb Z/n\mathbb Z\) and they count the number of points over \(\mathbb Z/n\mathbb Z\) on their Jacobians \(A\), which are abelian varieties of dimension 2. This is done by means of an extension of Schoof's algorithm. As the authors put it, there is now some \textit{good news} and some \textit{bad news}. It can on the one hand be shown that, if \(n\) is prime, one is likely to find an abelian variety \(A\) such that the group of points \(A(\mathbb Z/n\mathbb Z)\) has prime order \(q\). As before, one reduces the proof of the primality of \(n\) to that of \(q\). On the other hand, the prime \(q\) will be much larger than \(n\): by Weil's theorem one has that \(q\approx n^ 2!\) However, from a slight generalization of a result by \textit{H. Iwaniec} and \textit{M. Jutila} [Ark. Mat. 17, 167--176 (1979; Zbl 0408.10029)] in analytic number theory, it follows that by repeating this procedure three times, one is likely to encounter a number \(q\) of points on an abelian variety of dimension 2, that can be proved prime by means of the algorithm of Goldwasser and Kilian. Note that this number \(q\) is approximately equal to the eight power of the number \(n\). In order to obtain their main theorem, the authors proves several results concerning abelian varieties and Jacobian varieties over finite fields. These results are of interest in themselves.