Infinite sets of primes with fast primality tests and quick generation of large primes
Authors:
János Pintz, William L. Steiger and Endre Szemerédi
Journal:
Math. Comp. 53 (1989), 399406
MSC:
Primary 11Y11; Secondary 11Y16
MathSciNet review:
968154
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Infinite sets P and Q of primes are described, . For any natural number n it can be decided if in (deterministic) time . 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 , we show how to randomly produce a proof of the primality of n. The expected time is that needed for exponentiations . We also show how to randomly generate kdigit integers which will be in Q with probability proportional to . Combined with the fast verification of just mentioned, this gives an 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 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.
 [1]
R.
A. Mollin, Recognizing primes, Int. J. Algebra
1 (2007), no. 912, 469–476. MR 2380976
(2008m:11242)
 [2]
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 (84e:10008), http://dx.doi.org/10.2307/2006975
 [3]
M.
B. Barban, Yu.
V. Linnik, and N.
G. Tshudakov, On prime numbers in an arithmetic progression with a
primepower difference, Acta Arith. 9 (1964),
375–390. MR 0171766
(30 #1993)
 [4]
John
Brillhart, D.
H. Lehmer, and J.
L. Selfridge, New primality criteria and
factorizations of 2^{𝑚}±1, Math.
Comp. 29 (1975),
620–647. MR 0384673
(52 #5546), http://dx.doi.org/10.1090/S00255718197503846731
 [5]
S. Goldwasser & J. Kilian, Almost All Primes Can Be Quickly Certified, Proc. 18th Ann. ACM Sympos. on Theory of Computing, 1986, pp. 316329.
 [6]
M.
N. Huxley and M.
Jutila, Large values of Dirichlet polynomials. IV, Acta Arith.
32 (1977), no. 3, 297–312. MR 0485728
(58 #5550)
 [7]
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
(85g:11117)
 [8]
Gary
L. Miller, Riemann’s hypothesis and tests for primality,
J. Comput. System Sci. 13 (1976), no. 3,
300–317. Working papers presented at the ACMSIGACT Symposium on the
Theory of Computing (Albuquerque, N.M., 1975). MR 0480295
(58 #470a)
 [9]
Hugh
L. Montgomery, Topics in multiplicative number theory, Lecture
Notes in Mathematics, Vol. 227, SpringerVerlag, BerlinNew York, 1971. MR 0337847
(49 #2616)
 [10]
Carl
Pomerance, Very short primality proofs,
Math. Comp. 48 (1987), no. 177, 315–322. MR 866117
(88b:11088), http://dx.doi.org/10.1090/S00255718198708661174
 [11]
Michael
O. Rabin, Probabilistic algorithm for testing primality, J.
Number Theory 12 (1980), no. 1, 128–138. MR 566880
(81f:10003), http://dx.doi.org/10.1016/0022314X(80)900840
 [12]
A.
Schönhage and V.
Strassen, Schnelle Multiplikation grosser Zahlen, Computing
(Arch. Elektron. Rechnen) 7 (1971), 281–292 (German,
with English summary). MR 0292344
(45 #1431)
 [13]
H.
C. Williams, Primality testing on a computer, Ars Combin.
5 (1978), 127–185. MR 504864
(80d:10002)
 [1]
 L. M. Adleman & M. A. Huang, Recognizing Primes in Random Polynomial Time, Proc. 19th Ann. ACM Sympos. on Theory of Computing, 1987, pp. 462469. MR 2380976 (2008m:11242)
 [2]
 L. M. Adleman, C. Pomerance & R. S. Rumely, "On distinguishing prime numbers from composite numbers," Ann. of Math., v. 117, 1983, pp. 173206. MR 683806 (84e:10008)
 [3]
 M. B. Barban, Ju. V. Linnik & N. G. Tshudakov, "On prime numbers in an arithmetic progression with a primepower difference," Acta Arith., v. 9, 1964, pp. 375390. MR 0171766 (30:1993)
 [4]
 J. Brillhart, D. H. Lehmer & J. L. Selfridge, "New primality criteria and factorization of ," Math. Comp., v. 29, 1975, pp. 620647. MR 0384673 (52:5546)
 [5]
 S. Goldwasser & J. Kilian, Almost All Primes Can Be Quickly Certified, Proc. 18th Ann. ACM Sympos. on Theory of Computing, 1986, pp. 316329.
 [6]
 M. Huxley & M. Jutila, "Large values of Dirichlet polynomials IV", Acta Arith., v. 32, 1977, pp. 297312. MR 0485728 (58:5550)
 [7]
 H. W. Lenstra, Jr., "Primality testing," Computational Methods in Number Theory, Math. Centrum Tracts, no. 154, Math. Centrum, Amsterdam, 1982, pp. 5577. MR 700258 (85g:11117)
 [8]
 G. L. Miller, "Riemann's hypothesis and tests for primality," J. Comput. System Sci., v. 13, 1976, pp. 300317. MR 0480295 (58:470a)
 [9]
 H. L. Montgomery, Topics in Multiplicative Number Theory, Lecture Notes in Math., Vol. 227, SpringerVerlag, Berlin, 1971. MR 0337847 (49:2616)
 [10]
 C. Pomerance, "Very short primality proofs," Math. Comp., v. 48, 1987, pp. 315322. MR 866117 (88b:11088)
 [11]
 M. Rabin, "Probabilistic algorithms for testing primality," J. Number Theory, v. 12, 1980, pp. 128138. MR 566880 (81f:10003)
 [12]
 A. Schönhage & V. Strassen, "Schnelle Multiplikation grosser Zahlen," Computing, v. 7, 1971, pp. 281292. MR 0292344 (45:1431)
 [13]
 H. C. Williams, "Primality testing on a computer," Ars Combin. v. 5, 1978, pp. 127185. MR 504864 (80d:10002)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
11Y11,
11Y16
Retrieve articles in all journals
with MSC:
11Y11,
11Y16
Additional Information
DOI:
http://dx.doi.org/10.1090/S0025571819890968154X
PII:
S 00255718(1989)0968154X
Article copyright:
© Copyright 1989
American Mathematical Society
