In questo lavoro si considerano due tests probabilistici di primalità (precisamente i test di Solovay-Strassen e Rabin) per interi dispari n di forma qualsiasi. Gli algoritmi sono tali che se n è dichiarato composto allora lo è certamente mentre se n è dichiarato primo il risultato ha un certo margine di errore, che può essere reso arbitrariamente piccolo. Un programma scritto e compilato in linguaggio FORTRAN, applicabile ad interi fino a 10 elevato alla 2000 ed adatto anche a personal computer, permette un confronto fra i due test sulla base del tipo dei risultati e del tempo di elaborazione, fornendo diverse opzioni ed una stima del limite superiore per l'eventuale errore in una dichiarazione di porobabile primalità.
Implementation of probabilistic tests of primality
CODECA', Paolo;BIASINI, Luciano;ZANGHIRATI, Gaetano
1992
Abstract
In questo lavoro si considerano due tests probabilistici di primalità (precisamente i test di Solovay-Strassen e Rabin) per interi dispari n di forma qualsiasi. Gli algoritmi sono tali che se n è dichiarato composto allora lo è certamente mentre se n è dichiarato primo il risultato ha un certo margine di errore, che può essere reso arbitrariamente piccolo. Un programma scritto e compilato in linguaggio FORTRAN, applicabile ad interi fino a 10 elevato alla 2000 ed adatto anche a personal computer, permette un confronto fra i due test sulla base del tipo dei risultati e del tempo di elaborazione, fornendo diverse opzioni ed una stima del limite superiore per l'eventuale errore in una dichiarazione di porobabile primalità.I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
