sabato 18 maggio 2013

Fattorizzazione Random per RSA in PARI/GP





{fatto(n)=local(p);
p = nextprime(random(floor(sqrt(n))));
while(n/p != floor(n/p), p =nextprime(random(floor(sqrt(n)))));
print(p);
print(n/p);
}



domenica 5 maggio 2013

Numeri primi con Derive

Anche Derive è un ottimo software matematico per lo studio dei numeri primi.
La funzione FACTOR (FACTOR(n)) fattorizza gli interi come i polinomi ma molto interessante è la funzione NEXT_PRIME(N) che dato il numero N restituisce il numero primo successivo a N. E' molto importante perché si può usare come test di primalità: se voglio sapere se p è primo non devo far altro che calcolare NEXT_PRIME(p-1) = v e se v = p allora deduco che p è primo altrimenti non è primo. Questo semplice criterio logico si applica anche a software come il PARI/GP che ha sia la funzione nextprime(n) sia la funzione isprime(n) o prime(n).

NextPrime(n) può essere impiegato per trovare anche numeri primi molto grandi da impiegare per trovare i fattori p, q nell'algoritmo RSA.

Ad esempio in PARI/GP il codice potrebbe essere:


{primo(p)= local(v);
V = nextprime(v-1);
print(p);
if(v == p, "primo", "no primo");
}
invece di isprime(p)

Altre due funzioni di Derive utili per la teoria dei numeri sono:
-EULER_PHI(n) = per il calcolo della phi di Eulero di un numero n
- MOD(a^m, n) = per il calcolo di a^m modulo n

Calcolare la phi di Eulero di un numero di fatto equivale a fattorizzarlo
Mentre la funzione MOD(a^m, n) può esserci utile per verificare la primalità di un numero con il test di Fermat: se p è primo a^p=a mod p per ogni intero a (ovviamente non sempre vale il viceversa ma i "falsi" primi o primi di Charmicahel sono piuttosto rari)