Geodesic
Questo numero è primo? Sì, forse, dipende ...
Bollettino della Unione matematica italiana, Série 8, 9A (2006) no. 3-1, pp. 449-481.

Voir la notice de l'article provenant de la source Biblioteca Digitale Italiana di Matematica

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.
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). 
@article{BUMI_2006_8_9A_3-1_a3,
     author = {Caire, Luisella and Cerruti, Umberto},
     title = {Questo numero \`e primo? {S{\`\i},} forse, dipende ...},
     journal = {Bollettino della Unione matematica italiana},
     pages = {449--481},
     publisher = {mathdoc},
     volume = {Ser. 8, 9A},
     number = {3-1},
     year = {2006},
     zbl = {1195.00012},
     mrnumber = {2123939},
     language = {it},
     url = {http://geodesic.mathdoc.fr/item/BUMI_2006_8_9A_3-1_a3/}
}
TY  - JOUR
AU  - Caire, Luisella
AU  - Cerruti, Umberto
TI  - Questo numero è primo? Sì, forse, dipende ...
JO  - Bollettino della Unione matematica italiana
PY  - 2006
SP  - 449
EP  - 481
VL  - 9A
IS  - 3-1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/BUMI_2006_8_9A_3-1_a3/
LA  - it
ID  - BUMI_2006_8_9A_3-1_a3
ER  - 
%0 Journal Article
%A Caire, Luisella
%A Cerruti, Umberto
%T Questo numero è primo? Sì, forse, dipende ...
%J Bollettino della Unione matematica italiana
%D 2006
%P 449-481
%V 9A
%N 3-1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/BUMI_2006_8_9A_3-1_a3/
%G it
%F BUMI_2006_8_9A_3-1_a3
Caire, Luisella; Cerruti, Umberto. Questo numero è primo? Sì, forse, dipende .... Bollettino della Unione matematica italiana, Série 8, 9A (2006) no. 3-1, pp. 449-481. http://geodesic.mathdoc.fr/item/BUMI_2006_8_9A_3-1_a3/

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

[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. | DOI | MR

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

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

[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. | DOI | MR | Zbl

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

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

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

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

[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. | DOI | MR | Zbl

[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. | DOI | MR | Zbl

[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

[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

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

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

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

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