linux user group brescia

On Fri, Dec 19, 2003 at 02:13:18PM +0100, Simone wrote:
> 
> Luca Giuzzi wrote:
> 
> > Risposta breve:
> > cipher/primegen.c
> > 
> > Risposta lunga:
> > 'http://citeseer.nj.nec.com/155623.html'
> 
> Meglio la risposta lunga, nella risposta breve mi stavo giusto chiedendo 
> perchè il metodo "check_prime" ritorna "true if this _may_ be a prime" e 
> il metodo "is_prime" ritorna "true if n is _probably_ a prime" :)
> 
Il sito della nec (citeseer.nj.nec.com) e' veramente comodo se devi
cercare degli articoli di Computer Science (e anche un po' di articoli
di matematica): referenze bibliografiche incrociate, accesso full
text ai ps e ai pdf e (cosa fondamentale) il tutto e' gratuito.

Il check_prime() effettua una analisi del tutto in tre fasi:
 a. divisibilita' per primi piccoli
 b. test di Fermat
    p^(p-1) % p = 1
 c. richiama is_prime()

La funzione is_prime() e' invece il "solito" Miller-Rabin che
e' un algoritmo probabilistico (iterato n volte) ...
osserva che sebbene esista un algoritmo esatto che e' O(n) per
testare la primalita' di un numero, e' COMUNQUE meglio usare
il MR per primi "abbordabili" (a causa dell'overhead dell'algoritmo
lineare).

ciao,
 lg

> Grazie ancora!
> 
> Simone
> -- 
> "With my cross-bow I shot the Albatross..."

--