linux user group brescia

Luca Giuzzi wrote:

> Il check_prime() effettua una analisi del tutto in tre fasi:
>  a. divisibilita' per primi piccoli
>  b. test di Fermat
>     2^(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).

Grazie mille per i commenti, adesso il codice è un tantinello più chiaro :)

Simone