Questo numero è primo? Sì, forse, dipende ...

Luisella Caire; Umberto Cerruti

Bollettino dell'Unione Matematica Italiana (2006)

  • Volume: 9-A, Issue: 3-1, page 449-481
  • ISSN: 0392-4041

Abstract

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

How to cite

top

Caire, Luisella, and Cerruti, Umberto. " Questo numero è primo? Sì, forse, dipende ...." Bollettino dell'Unione Matematica Italiana 9-A.3-1 (2006): 449-481. <http://eudml.org/doc/289587>.

@article{Caire2006,
abstract = {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).},
author = {Caire, Luisella, Cerruti, Umberto},
journal = {Bollettino dell'Unione Matematica Italiana},
language = {ita},
month = {12},
number = {3-1},
pages = {449-481},
publisher = {Unione Matematica Italiana},
title = { Questo numero è primo? Sì, forse, dipende ...},
url = {http://eudml.org/doc/289587},
volume = {9-A},
year = {2006},
}

TY - JOUR
AU - Caire, Luisella
AU - Cerruti, Umberto
TI - Questo numero è primo? Sì, forse, dipende ...
JO - Bollettino dell'Unione Matematica Italiana
DA - 2006/12//
PB - Unione Matematica Italiana
VL - 9-A
IS - 3-1
SP - 449
EP - 481
AB - 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).
LA - ita
UR - http://eudml.org/doc/289587
ER -

References

top
  1. ADLEMAN, L. M. - POMERANCE, C. - RUMELY, R. S., On distinguishing prime numbers from composite numbers, Annals of Mathematics, 117 (1983), 173-206. Zbl0526.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. MR2123939DOI10.4007/annals.2004.160.781
  4. ALFORD, W. R. - GRANVILLE, A. - POMERANCE, C., There are infinitely many Carmichael numbers, Annals of Mathematics, 139 (1994), 703-722. Zbl0816.11005MR1283874DOI10.2307/2118576
  5. BAILLIE, R. - WAGSTAFF, S. S., Lucas pseudoprimes, Mathematics of Computation, 35 (1980), 1391-1417. MR583518DOI10.2307/2006406
  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 2 m ± 1 , Mathematics of Computations, 29 (1975), 620-647. Zbl0311.10009MR384673DOI10.2307/2005583
  8. CRANDALL, R. - POMERANCE, C., Prime Numbers: a computational perspective, Springer-Verlag, 2002. Zbl0995.11072MR1821158DOI10.1007/978-1-4684-9316-0
  9. GOLDWASSER, S. - KILIAN, J., Primality Testing using Elliptic Curves, Journal of the ACM, 46 (1999), 450-472. Zbl1064.11503MR1812127DOI10.1145/320211.320213
  10. LANGUASCO, A. - ZACCAGNINI, A., Introduzione alla Crittografia, Hoepli Editore, Milano, 2004. 
  11. LEMMERMEYER, F., Reciprocity Laws: From Euler to Eisenstein, Springer, 2000. MR1761696DOI10.1007/978-3-662-12893-0
  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. Zbl0349.68025MR480295DOI10.1016/S0022-0000(76)80043-8
  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. Zbl1017.11068MR1861844DOI10.1007/3-540-46665-7_26
  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. 
  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. MR464678
  18. RABIN, M. O., Probabilistic Algorithms for Testing Primality, Journal of Number Theory, 12 (1980), 128-138. Zbl0426.10006MR566880DOI10.1016/0022-314X(80)90084-0
  19. RIBENBOIM, P., The Book of Prime Numbers Records, Springer-Verlag, 1988. Zbl0642.10001MR931080DOI10.1007/978-1-4684-9938-4
  20. SOLOWAY, R. M. - STRASSEN, V., A fast Montecarlo test for primality, SIAM Journal on Computing, 6 (1977), 84-85. Zbl0345.10002MR429721DOI10.1137/0206006
  21. YAN, S. Y., Primality testing of large numbers in Maple, Computers and Mathematics with Applications, 12 (1995), 1-8. Zbl0847.11062MR1329593DOI10.1016/0898-1221(95)00052-Z

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.