Shafi Goldwasser
Joe Kilian
Abstract
We present a primality proving algorithm—a probablistic primality test that produces short certificates of primality on prime inputs. We prove that the test runs in expected polynomial time for all but a vanishingly small fraction of the primes. As a corollary, we obtain an algorithm for generating large certified primes with distribution statistically close to uniform. Under the conjecture that the gap between consecutive primes is bounded by some polynomial in their size, the test is shown to run in expected polynomial time for all primes, yielding a Las Vegas primality test.
Our test is based on a new methodology for applying group theory to the problem of prime certification, and the application of this methodology using groups generated by elliptic curves over finite fields.
We note that our methodology and methods have been subsequently used and improved upon, most notably in the primality proving algorithm of Adleman and Huang using hyperelliptic curves and in practical primality provers using elliptic curves.
- ADLEMAN, L. M., AND HUANG, M. 1987. Recognizing primes in polynomial time. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (New York, N.Y., May 25-27). ACM, New York, pp. 462-471. Google Scholar
- ADLEMAN, L. M., AND HUANG, M. 1992. Primality testing and Abelian varieties over finite fields. In Lecture Notes in Mathematics, vol. 1512. Springer-Verlag, New York.Google Scholar
- ADLEMAN, L. M., MANDERS, K., AND MILLER, G. L. 1977. On taking roots in finite fields. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science. IEEE, New York, pp. 175-178.Google Scholar
- ADLEMAN, L. M., POMERANCE, C., AND RUMELY, R. 1983. On distinguishing prime numbers from composite numbers. Ann. Math. 117, 173-206.Google Scholar
- ATKIN, A. O.L. 1986a. Schoof's algorithm. Manuscript.Google Scholar
- ATKIN, A. O.L. 1986b. Manuscript.Google Scholar
- ATKIN, A. O.L. 1988. The number of points on an elliptic curve modulo a prime. Manuscript.Google Scholar
- ATKIN, A. O.L. 1992. The number of points on an elliptic curve modulo a prime (II). Manuscript.Google Scholar
- ATKIN, A. O. L., AND MORAIN, f. 1993. Elliptic curves and primality proving. Math. Comput. 61, 203 (July), 29-68.Google Scholar
- BOSMA, W. 1985. Primality testing using elliptic curves. Tech. Rep. 8512. Math. Instituut, Univ. Amsterdam, Amsterdam, The Netherlands.Google Scholar
- BOSMA, W., AND VAN DER HULST, M.P. 1990. Faster primality testing. In Proceedings of EUROC- RYPT '89. Lecture Notes in Computer Science, vol. 434. Springer-Verlag, New York, pp. 652-656. Google Scholar
- BRILLHART, J., LEHMER, D. H., AND SELFRIDGE, J.L. 1975. New primality criteria and factorizations of 2m + 1. Math. Comput. 29, 130, 620-647.Google Scholar
- BRILLHART, J., LEHMER, D. H., SELFRIDGE, J. L., TUCKERMAN, B., AND WAGSTAFF, JR., S.S. 1988. Factorizations of b" + 1; b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers. Cont. Math. 2, 22.Google Scholar
- CHUDNOVSKY, D., AND CHUDNOVSKY, G. 1986. Sequences of numbers generated by addition in formal groups and new primality and factorization tests. Adv. App. Math. 7. Google Scholar
- COHEN, H., AND LENSTRA, JR., H.W. 1984. Primality testing and Jacobi sums. Math. Comput. 42.Google Scholar
- ELKmS, N.D. 1991. Explicit isogenies. Manuscript.Google Scholar
- ELKmS, N. D. 1998. Elliptic and modular curves over finite fields and related computational issues. In Computational Perspectives on Number Theory: Proceedings of a Conference in Honor of A. O. L. Atkins, D. A. Buell and J. T. Teitelbaum, eds. AMS/IP Studies in Advanced Mathematics, vol. 7. American Mathematics Society, Providence, R. I., pp. 21-76.Google Scholar
- GOLDWASSER, S., AND KILIAN, J. 1986. Almost all primes can be quickly certified. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (Berkeley, Calif., May 28-30). ACM, New York, pp. 316-329. Google Scholar
- HEATH-BROWN, D.R. 1978. The differences between consecutive primes. J. London Math. Soc. 2, 18, 7-13.Google Scholar
- I#ALTOFEN, E., VALENTE, T., AND YUI, N. 1989. An improved Las Vegas primality test. In Proceedings of the ACM-SIGSAM 1989 International Symposium on Symbolic and Algebraic Computation (ISSAC '89) (Portland, Ore., July 17-19), Gilt Gonnet, ed. ACM, New York, pp. 26-33. Google Scholar
- KILIAN, J. 1990. Uses of Randomness in Algorithms and Protocols. MIT Press, Cambridge, Mass. Google Scholar
- KONYAGIN, S., AND POMERANCE, C. 1997. On primes recognizable in deterministic polynomial time. In The Mathematics of Paul Erd6s, R. Graham and J. Negetfil, eds. Springer-Verlag, New York, pp. 177-198.Google Scholar
- LENSTRA, JR., H.W. 1987. Factoring, integers with elliptic curves. Ann. Math. 126, 649-673.Google Scholar
- LENSTRA, A., AND LENSTRA, JR., H.W. 1987. Algorithms in number theory. Tech. Rep. 87-008. Univ. Chicago, Chicago, Ill. Google Scholar
- LENSTRA, JR., H. W., PILA, J., AND POMERANCE, C. 1993. A hyperelliptic smoothness test, I. Philos. Trans. Roy Soc. London Ser. A 345, 397-408.Google Scholar
- LENSTRA, JR., H. W., PILA, J., AND POMERANCE, C. 1999. A hyperelliptic smoothness test, II. Manuscript.Google Scholar
- LENSTRA, JR., H. W., PILA, J., AND POMERANCE, C. 1999. A hyperelliptic smoothness test, III. To appear.Google Scholar
- MIHAILESCU, P. 1994. Cyclotomy primality proving--Recent developments. In Proceedings of the 3rd International Algorithmic Number Theory Symposium (ANTS). Lecture Notes in Computer Science, vol. 877. Springer-Verlag, New York, pp. 95-110. Google Scholar
- MILLER, G.L. 1976. Riemann's hypothesis and test for primality. J. Comput. Syst. Sci. 13, 300-317.Google Scholar
- MORAIN, F. 1990. Courbes elliptques et tests de primalit6. Ph.D. dissertation. Univ. Claude Bernard-Lyon I.Google Scholar
- MORAIN, F. 1995. Calcul de nombre de points sur une courbe elliptique dans un corps fini: Aspects algorithmiques. J. Th#or. Nombres Bordeaux 7, 255-282.Google Scholar
- PINTZ, J., STEIGER, W., AND SZEMEREDI, E. 1989. Infinite sets of primes with fast primality tests and quick generation of large primes. Math. Comput. 53, 187, 399-406.Google Scholar
- POMERANCE, C. 1987. Very short primality proofs. Math. Comput. 48, 177, 315-322.Google Scholar
- PRATT, V.R. 1975. Every prime has a succinct certificate. SIAM J. Comput. 4, 3, 214-220.Google Scholar
- RABIN, M. 1980. Probabilistic algorithms for testing primality. J. Numb. Theory 12, 128-138.Google Scholar
- SCHOOF, R. 1985. Elliptic curves over finite fields and the computation of square roots modulo p. Math. Comput. 44, 483-494.Google Scholar
- SCHOOF, R. 1995. Counting points on elliptic curves over finite fields. J. Th#or. Nombres. Bordeaux 7, 219-254.Google Scholar
- SILVERMAN, J. 1986. The arithmetic of elliptic curves. In Graduate Texts in Mathematics, vol. 106. Springer-Verlag, New York.Google Scholar
- SOLOVAY, R., AND STRASSEN, V. 1977. A fast Monte-Carlo test for primality. SIAM J. Comput. 6, 1, 84-85.Google Scholar
- TATE, J. 1974. The arithmetic of elliptic curves. Invent. Math. 23, 179-206.Google Scholar
- WILLIAMS, H.C. 1978. Primality testing on a computer. Ars. Combinat. 5, 127-185.Google Scholar
- WUNDERLICH, M. C. 1983. A performance analysis of a simple prime-testing algorithm. Math. Comput. 40, 162, 709-714.Google Scholar
Index Terms
- Primality testing using elliptic curves
Recommendations
Differential addition on binary elliptic curves
AbstractThis paper presents new and fast differential addition (i.e., the addition of two points with the known difference) and doubling formulas, as the core step in Montgomery scalar multiplication, for various forms of elliptic curves over ...
Highlights- Differential addition and doubling formulas.
- Efficient arithmetic on elliptic ...
On the completeness of certain n-tracks arising from elliptic curves
Complete n-tracks in PG(N,q) and non-extendable Near MDS codes of dimension N+1 over F"q are known to be equivalent objects. The best known lower bound for the maximum number of points of an n-track is attained by elliptic n-tracks, that is, n-tracks ...
Computing projective equivalences of planar curves birationally equivalent to elliptic and hyperelliptic curves▪
AbstractWe present algorithms to find the projective equivalences between two planar curves, birationally equivalent to either elliptic or hyperelliptic curves. The main idea, in both cases, is to find first a corresponding birational mapping ...
Graphical abstractHighlights- Projective equivalences between planar curves birationally equivalent to elliptic or hyperelliptic curves
Comments