Infinite sets of primes with fast primality tests and quick generation of large primes
HTML articles powered by AMS MathViewer
- by János Pintz, William L. Steiger and Endre Szemerédi PDF
- Math. Comp. 53 (1989), 399-406 Request permission
Abstract:
Infinite sets P and Q of primes are described, $P \subset Q$. For any natural number n it can be decided if $n \in P$ in (deterministic) time $O({(\log n)^9})$. This answers affirmatively the question of whether there exists an infinite set of primes whose membership can be tested in polynomial time, and is a main result of the paper. Also, for every $n \in Q$, we show how to randomly produce a proof of the primality of n. The expected time is that needed for $1\frac {1}{2}$ exponentiations $\bmod n$. We also show how to randomly generate k-digit integers which will be in Q with probability proportional to ${k^{ - 1}}$. Combined with the fast verification of $n \in Q$ just mentioned, this gives an $O({k^4})$ expected time algorithm to generate and certify primes in a given range and is probably the fastest method to generate large certified primes known to belong to an infinite subset. Finally, it is important that P and Q are relatively dense (at least $c{n^{2/3}}/\log n$ elements less than n). Elements of Q in a given range may be generated quickly, but it would be costly for an adversary to search Q in this range, a property that could be useful in cryptography.References
- R. A. Mollin, Recognizing primes, Int. J. Algebra 1 (2007), no. 9-12, 469–476. MR 2380976, DOI 10.12988/ija.2007.07050
- Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), no. 1, 173–206. MR 683806, DOI 10.2307/2006975
- M. B. Barban, Yu. V. Linnik, and N. G. Tshudakov, On prime numbers in an arithmetic progression with a prime-power difference, Acta Arith. 9 (1964), 375–390. MR 171766, DOI 10.4064/aa-9-4-375-390
- John Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria and factorizations of $2^{m}\pm 1$, Math. Comp. 29 (1975), 620–647. MR 384673, DOI 10.1090/S0025-5718-1975-0384673-1 S. Goldwasser & J. Kilian, Almost All Primes Can Be Quickly Certified, Proc. 18th Ann. ACM Sympos. on Theory of Computing, 1986, pp. 316-329.
- M. N. Huxley and M. Jutila, Large values of Dirichlet polynomials. IV, Acta Arith. 32 (1977), no. 3, 297–312. MR 485728, DOI 10.4064/aa-32-3-297-312
- H. W. Lenstra Jr., Primality testing, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 55–77. MR 700258
- Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, DOI 10.1016/S0022-0000(76)80043-8
- Hugh L. Montgomery, Topics in multiplicative number theory, Lecture Notes in Mathematics, Vol. 227, Springer-Verlag, Berlin-New York, 1971. MR 0337847
- Carl Pomerance, Very short primality proofs, Math. Comp. 48 (1987), no. 177, 315–322. MR 866117, DOI 10.1090/S0025-5718-1987-0866117-4
- Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI 10.1016/0022-314X(80)90084-0
- A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
- H. C. Williams, Primality testing on a computer, Ars Combin. 5 (1978), 127–185. MR 504864
Additional Information
- © Copyright 1989 American Mathematical Society
- Journal: Math. Comp. 53 (1989), 399-406
- MSC: Primary 11Y11; Secondary 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-1989-0968154-X
- MathSciNet review: 968154