Jacobi sum test
The Jacobi sum test is another true primality test. The basic idea is to test a set of congruences which are analogues of Fermat’s theorem (Fact 2.127(i)) in certain cydotomic rings. The running tune of the Jacobi sum test for determining the primality of an integer n is 0((1п ?г)с1п1п1пп) bit operations for some constant c. This is “almost” a polynomialtime algorithm since the exponent In In In n acts like a constant for the range of values for
n of interest. For example, if n < 2512, then In In Inn < 1.78. The version of the Jacobi sum primality test used in practice is a randomized algorithm which terminates within 0(A(lnn)c|nininn) stepS With probability at least 1 - (^)k for every A > 1, and always gives a correct answer. One drawback of the algorithm is that it does not produce a “certificate” which would enable the answer to be verified in much shorter time than running the algorithm itself.
The Jacobi sum test is, indeed, practical in the sense that the primality of numbers that are several hundred decimal digits long can be handled hi just a few minutes on a computer. However, the test is not as easy to program as the probabilistic Miller-Rabin test (Algorithm 4.24), and the resulting code is not as compact. The details of the algorithm are complicated and are not given here; pointers to the literature are given in the chapter notes on page 166.
Tests using elliptic curves
Elliptic curve primality proving algorithms are based on an elliptic curve analogue of Pock- lington’s theorem (Fact 4.40). The version of the algorithm used in practice is usually referred to as Atkin’s test or the Elliptic Cur’e Primality Proving algorithm (ECPP). Under heuristic arguments, the expected running tune of this algorithm for proving the primality of an integer n has been shown to be 0((lnn)6+<) bit operations for any e > 0. Atkin’s test has the advantage over the Jacobi sum test (§4.3.3) that it produces a short certificate of primality which can be used to efficiently verify the primality of the number. Atkin’s test has been used to prove the primality of numbers more than 1000 decimal digits long.
The details of the algorithm are complicated and are not presented here; pointers to the literature are given hi the chapter notes on page 166.