## 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, - 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**

*Almost All Primes Can Be Quickly Certified*, Proc. 18th Ann. ACM Sympos. on Theory of Computing, 1986, pp. 316-329.

## 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