Questo numero è primo? Sì, forse, dipende ...
Bollettino della Unione matematica italiana, Série 8, 9A (2006) no. 3-1, pp. 449-481
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.
@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},
year = {2006},
volume = {Ser. 8, 9A},
number = {3-1},
zbl = {1195.00012},
mrnumber = {MR2309899},
language = {it},
url = {http://geodesic.mathdoc.fr/item/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/