On Primality Tests
Daniel J. Lehmann · SIAM Journal on Computing · 1982
Whether an odd number m is prime can be decided on the knowledge of the image of the function $a \mapsto a^{(m - 1)/2} (m)$. As a consequence, an algorithm for testing primality is proposed (under the extended Riemann hypothesis) which is more efficient than ones proposed by Miller [Pros. 7th ACM Symp. Theory of Computing, 1975, pp. 234–239] and Vélu [SIGACT News, 10 (1978), pp. 58–59]. A probabilistic version is compared with the algorithm of Solovay and Strassen [SIAM J. Comput., 6 (1977), pp. 84–85; erratum, 7 (1978), p. 118].