Questo numero è primo? Sì, forse, dipende ...
Caire, Luisella ; Cerruti, Umberto
Bollettino dell'Unione Matematica Italiana, Tome 9-A (2006), p. 449-481 / Harvested from Biblioteca Digitale Italiana di Matematica
Access to full text
Full (PDF)
Full (DjVu)

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).

In questo articolo presentiamo una breve panoramica di alcuni algoritmi il cui compito è decidere se un intero è primo: criteri di primalità, che sono deterministici (cioè rispondono con certezza sì e no) e incondizionati, ma purtroppo inefficienti (tecnicamente non polinomiali); algoritmi efficienti, ma solo probabilistici (cioè che danno la certezza quando rispondono no mentre nel caso di risposta sì assicurano soltanto un limite inferiore alla probabilità che il numero sia primoo; algoritmi che sono al tempo stesso deterministici ed efficienti, ma sono condizionati, cioè dipendono dalla congettura estesa di Rienman, tuttora non dimostrata.

Publié le : 2006-12-01
@article{BUMI_2006_8_9A_3-1_449_0,
     author = {Luisella Caire and Umberto Cerruti},
     title = { Questo numero \`e primo? S\`\i , forse, dipende ...},
     journal = {Bollettino dell'Unione Matematica Italiana},
     volume = {9-A},
     year = {2006},
     pages = {449-481},
     zbl = {1195.00012},
     mrnumber = {2309899},
     language = {it},
     url = {http://dml.mathdoc.fr/item/BUMI_2006_8_9A_3-1_449_0}
}

Caire, Luisella; Cerruti, Umberto.  Questo numero è primo? Sì, forse, dipende .... Bollettino dell'Unione Matematica Italiana, Tome 9-A (2006) pp. 449-481. http://gdmltest.u-ga.fr/item/BUMI_2006_8_9A_3-1_449_0/

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

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

[3] Agrawal, M. - Kayal, N. - Saxena, N., PRIMES is in P, Annals of Mathematics, 160 (2004), 781-793. | MR 2123939

[4] Alford, W. R. - Granville, A. - Pomerance, C., There are infinitely many Carmichael numbers, Annals of Mathematics, 139 (1994), 703-722. | MR 1283874 | Zbl 0816.11005

[5] Baillie, R. - Wagstaff, S. S., Lucas pseudoprimes, Mathematics of Computation, 35 (1980), 1391-1417. | MR 583518

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

[7] Brillhart, J. - Lehmer, D. H. - Selfridge, J. L., New Primality Criteria and Factorizations for 2m±1, Mathematics of Computations, 29 (1975), 620-647. | MR 384673 | Zbl 0311.10009

[8] Crandall, R. - Pomerance, C., Prime Numbers: a computational perspective, Springer-Verlag, 2002. | MR 1821158 | Zbl 0995.11072

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

[10] Languasco, A. - Zaccagnini, A., Introduzione alla Crittografia, Hoepli Editore, Milano, 2004.

[11] Lemmermeyer, F., Reciprocity Laws: From Euler to Eisenstein, Springer, 2000. | MR 1761696

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

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

[14] Müller, S., On the combined Fermat/Lucas probable prime test, in Crypto and Coding '99, Lecture Notes in Computer Science1746, Springer-Verlag1999, 222-235. | MR 1861844 | Zbl 1017.11068

[15] Pocklington, H. C., 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] Pomerance, C., 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] Rabin, M. O., Probabilistic Algorithms, in 'Algorithms and Complexity: new directions and recent results', J. F. Traub Edt., Academic Press, 1976, 21-39. | MR 464678

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

[19] Ribenboim, P., The Book of Prime Numbers Records, Springer-Verlag, 1988. | MR 931080 | Zbl 0642.10001

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

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