Caire, Cerruti: Questo numero è primo? Sì, forse, dipende ...

Caire, Luisella and Cerruti, Umberto:
Questo numero è primo? Sì, forse, dipende ...
Bollettino dell'Unione Matematica Italiana Serie 8 9-A (2006) —La Matematica nella Società e nella Cultura, fasc. n.3-1, p. 449-481, Unione Matematica Italiana (Italian)
pdf (343 Kb), djvu (270 Kb). | MR2309899 | Zbl 1195.00012

Sunto

In this paper we outline some algorithms answering the question if a given number is prime: primally criteria, that are deterministic (they positively reply yes or not) and unconditional, but inefficient (technically not polynomial-time); algoritms that are efficient, but only probabilistic (to say they give absolute certainty if they answer not, whereas they only give a low boundary of the probability for the number to be prime if they answer yes); algorithms that are the same time deterministic and efficient, but conditioned, that is they depend on the extended Riemann conjecture(yet to be proved).

Referenze Bibliografiche

[1] L. M. ADLEMAN - C. POMERANCE - R. S. RUMELY, On distinguishing prime numbers from composite numbers, Annals of Mathematics, 117 (1983), 173-206. | Zbl 0526.10004

[2] A. N. AGADZHANOV, Unusual infinity of prime numbers, URL: http://citeseer.ifi.unizh.ch/agadzhanov01unusual.html, 2001

[3] M. AGRAWAL - N. KAYAL - N. SAXENA, PRIMES is in P, Annals of Mathematics, 160 (2004), 781-793. | fulltext (doi) | MR 2123939

[4] W. R. ALFORD - A. GRANVILLE - C. POMERANCE, There are infinitely many Carmichael numbers, Annals of Mathematics, 139 (1994), 703-722. | fulltext (doi) | MR 1283874 | Zbl 0816.11005

[5] R. BAILLIE - S. S. WAGSTAFF, Jr., Lucas pseudoprimes, Mathematics of Computation, 35 (1980), 1391-1417. | fulltext (doi) | MR 583518

[6] D. J. BERNSTEIN, Distinguishing prime numbers from composite numbers: the state of the art in 2004, URL: http://cr.yp.to/papers.html#prime2004 (2004).

[7] J. BRILLHART - D. H. LEHMER - J. L. SELFRIDGE, New Primality Criteria and Factorizations for $2^m \pm 1$, Mathematics of Computations, 29 (1975), 620-647. | fulltext (doi) | MR 384673 | Zbl 0311.10009

[8] R. CRANDALL - C. POMERANCE, Prime Numbers: a computational perspective, Springer-Verlag, 2002. | fulltext (doi) | MR 1821158 | Zbl 0995.11072

[9] S. GOLDWASSER - J. KILIAN, Primality Testing using Elliptic Curves, Journal of the ACM, 46 (1999), 450-472. | fulltext (doi) | MR 1812127 | Zbl 1064.11503

[10] A. LANGUASCO - A. ZACCAGNINI, Introduzione alla Crittografia, Hoepli Editore, Milano, 2004.

[11] F. LEMMERMEYER, Reciprocity Laws: From Euler to Eisenstein, Springer, 2000. | fulltext (doi) | MR 1761696

[12] E. LUCAS, Sur la recherche des grands nombres premiers, Association Française pour l'Avancement des Sciences, Comptes Rendus, 5 (1876), 61-68.

[13] G. L. MILLER, Riemann's Hypothesis and tests for Primality, J. of Comp. Sys. Sci. 13 (1976), 300-317. | fulltext (doi) | MR 480295 | Zbl 0349.68025

[14] S. MÜLLER, On the combined Fermat/Lucas probable prime test, in Crypto and Coding '99, Lecture Notes in Computer Science 1746, Springer-Verlag 1999, 222-235. | fulltext (doi) | MR 1861844 | Zbl 1017.11068

[15] H. C. POCKLINGTON, Determination of the prime or composite nature of large numbers by Fermat's theorem, Proceedings of the Cambridge Philosophical Society, 18 (1914), 29-30. | Zbl 45.0332.12

[16] C. POMERANCE, Primality testing: variations on a theme of Lucas, in corso di pubblicazione su Proceedings of MSRI Workshop, J. Buhler and P. Stevenhagen, eds. 2005, URL: http://cm.bell-labs.com/cm/ms/who/carlp/primalitytalk5.ps

[17] M. O. RABIN, Probabilistic Algorithms, in 'Algorithms and Complexity: new directions and recent results', J. F. Traub Edt., Academic Press, 1976, 21-39. | MR 464678

[18] M. O. RABIN, Probabilistic Algorithms for Testing Primality, Journal of Number Theory, 12 (1980), 128-138. | fulltext (doi) | MR 566880 | Zbl 0426.10006

[19] P. RIBENBOIM, The Book of Prime Numbers Records, Springer-Verlag, 1988. | fulltext (doi) | MR 931080 | Zbl 0642.10001

[20] R. M. SOLOWAY - V. STRASSEN, A fast Montecarlo test for primality, SIAM Journal on Computing, 6 (1977), 84-85. | fulltext (doi) | MR 429721 | Zbl 0345.10002

[21] S. Y. YAN, Primality testing of large numbers in Maple, Computers and Mathematics with Applications, 12 (1995), 1-8. | fulltext (doi) | MR 1329593 | Zbl 0847.11062

bdim: Biblioteca Digitale Italiana di Matematica

Un progetto SIMAI e UMI

Referenza completa

Sunto

Referenze Bibliografiche