Google+ Followers

Translate

Post in evidenza

SimpleGNFS in PARI GP - parte 4

Ecco oggi ho un pò di tempo per mostrarvi praticamente una semplice versione di GNFS in PARI GP. Il simpleGNFS di Rosario Turco e niente pi...

mercoledì 6 ottobre 2010

Miller-Rabin e i Numeri di Carmichael croce e delizia di Fermat

Il Piccolo Teorema di Fermat (PTF), dovuto a Pierre de Fermat e dimostrato successivamente da Eulero ha un fascino inesauribile pur provenendo dal lontano Seicento. E' quasi sempre tirato in ballo, anche nei nuovi metodi di primalità come AKS etc.

Vediamo in che consiste.

PTF:
 se a^n mod n = a mod n allora n è primo (1)  o alternativamente
 se a^n-1 mod n = 1 mod n allora n è primo. (2)

La versione di Eulero tiene conto della funzione totiente phi(n) per cui:  a^phi(n) mod n = a mod n.

Pierre de Fermat all'epoca pensava al solo test 2^n mod n = 2 mod n, che se era verificato allora n era un numero primo.

Solo che ci si accorse presto che alcuni composti, detti 'numeri di Carmichael', superavano il test e per cui affinchè il PTF fosse valido l'idea fu quello di testare n per vari valori di a, almeno un centinaio. In tal modo, visto che i numeri di Carmichael tendono al crescere di n ad essere rarefatti e molto distanti,allora il test era ancora valido e forniva una pseudo-primalità a-SPRP, cioè n risulta 'molto probabilmente' primo, se ha superato il test (1) per 100 valori di a.

Se n molto è grande, testarne la primalità per 100 basi è un test troppo lento, anche se di solito siamo abituati, purtroppo, a lasciare lavorare i computer per diversi giorni.

L'obiettivo di chi fa tali attività è trovare scorciatoie, per cercare di ottenere la primalità con poche risorse macchina e con poco tempo. Il che è difficilissimo, in molti casi impossibile!

Però a pensarci, possiamo ideare insieme un metodo. Poi dopo vediamo quanto è veloce e con quale complessità (cercherò di non annoiarvi).

Il problema del PTF non è il PTF stesso ma i numeri di Carmichael. Una lista di numeri Carmichael
è presente a http://oeis.org/classic/A002997.

Il bello della faccenda che il PTF funziona bene alla rovescia: certifica con certezza i composti ma fornisce una pseudo-primalità per i primi! Ma questo è vero per tutti i test probabilistici (Miller-Rabin etc).

Le domande che ci si può porre sono:
1) Potremmo rendere l'algoritmo che si basa sul PTF un pò meno di pseudo-primalità?
2) Possiamo fare solo un paio di test?

Forse sì, forse no. Solo due test: uno che dovrebbe ridurre di parecchio il fatto che n sia un numero di Carmichael ed uno costituito dal PTF con a=2. Un sogno finora...

Il Teorema di Chernick dice che i numeri di Carmichael generici sono tali da avere una forma
(6k+1)*(12k+1)*(18k+1) con ogni fattore primo.

Un'idea semplice è allora scrivere in PARI/GP un Charmichael's Test:

/*
*  Carmichael's test
*
*/
CT(number)= local(ret=0,x=0); {
/* Se lo trova esce 0 */
 if( number == 561 | number == 1105, return(0););  
 trap( , return(1),
   x=solve(k=1,number,(6*k+1)*(12*k+1)*(18*k+1) - number);
   if(frac(x)!=0.0, ret=1); /* Only integer */
 );
 return(ret);
}

Fissato  number l'idea è quella di risolvere una equazione cubica (6*k+1)*(12*k+1)*(18*k+1) - number = 0, se ha una soluzione intera abbiamo individuato un composto di Carmichael e sicuramente i tre fattori sono primi. E' stato introdotto il correttivo che l'equazione non individua cioè i due numeri 561 e 1105.

Purtroppo  sono possibili forme di Carmichael anche a più di 3 fattori:
(7k+1)(8k+1)(11k+1)
(6k+1)(12k+1)(18k+1)(36k+1)
(18k+1)(36k+1)(108k+1)(162k+1)
(24k+1)(72k+1)(192k+1)(288k+1)
(60k+1)(90k+1)(300k+1)(450k+1)
(60k+1)(240k+1)(300k+1)(600k+1)
(42k+1)(252k+1)(588k+1)(882k+1)
 etc.

Inoltre il test di sopra andrebbe male ad esempio con 885 (altra forma del tipo kl(n)+1), anch'esso numero di
Carmichael.

Versione generalizzata del Teorema di Chernick
Se un numero di Carmichael n è considerato nella sua forma canonica n  =  k lambda(n) + 1  e se qualche divisore d di k è tale che il numero   p  =  d l(n) + 1  sia primo, allora pn è un altro numero di Carmichael, dove lambda(n) è la funzione ridotta totiente, detta anche funzione lambda di Carmichael.

lambda(n) è il più piccolo intero positivo tale che x^m = 1 (mod n) per tutti gli x relativamente primi a n; in tal caso m=lambda(n); lambda(n) è anche l'esponente del gruppo moltiplicativo Zn.

La funzione lambda di Charmichael può essere calcolata nel seguente modo:
   lambda(1) = 1, 
   lambda(2) = 1,
   lambda(2^2) = 2,
   lambda(2^e) = 2^(e-2) for e > 2,
   lambda(p^e) = (p-1)*p^(e-1) for p > 2 and prime,
   lambda(p[1]^e[1]*...*p[r]^e[r]) =
                   LCM[lambda(p[1]^e[1]),...,lambda(p[r]^e[r])],
                                                all p[i]'s prime.
LCM è il minimo comune multiplo.
Inoltre l(q) = phi(q) se q è una potenza di un primo.

Ad esempio:
   lambda(2^e*5^f) = 2^(e-2)*5^(f-1), e > 3.

Per valutare 9^170489 = a (mod 5000000), si puà calcolare nell'ordine

   9^2 = 81 (mod 5000000)
   9^4 = (9^2)^2 = 81^2 = 6561 (mod 5000000)
   9^5 = (9^4)*9 = 6561*9 = 59049 (mod 5000000)
   9^10 = (9^5)^2 = 59049^2 = 1784401 (mod 5000000)
   9^20 = (9^10)^2 = 1784401^2 = 1928801 (mod 5000000)
   9^40 = (9^20)^2 = 1928801^2 = ...
   9^41 = 9^40*9 = ...
   9^82 = (9^41)^2 = ...
   9^83 = ...
   9^166 = ...
   9^332 = ...
   9^664 = ...
   9^665 = ...
   9^1330 = ...
   9^1331 = ...
   9^2662 = ...
   9^2663 = ...
   9^5326 = ...
   9^5327 = ...
   9^10654 = ...
   9^10655 = ...
   9^21310 = ...
   9^21311 = ...
   9^42622 = ...
   9^85244 = ...
   9^170488 = ...
   9^170489 = ... = a (mod 5000000).

Ad ogni step si fa il quadrato dell'esponente (by squaring) oppure aggiungendo 1 ad esso (multiplying by 9). Ciò è relazionato alla espansione binaria di 170489. Possiamo ricordare tutti i numeri relativamente piccoli con la riduzione modulo 5000000 dopo ogni step.

Anzicchè usare il lambda(n), forse la tecnica di esponenziazione by squaring del blog precedente, simile, ma risulta più rapida.

Repunit
Se stiamo testando dei Repunit abbiamo meno problemi: un numero Repunit difficilmente è un numero di Carmichael! I repunit sono i numeri ottenibili ad esempio da (10^n-1)/9  e caratterizzati da tutti 1.

Ad esempio
(10^n - 1)/9 = (6*k+1)*(12*k+1)*(18*k+1) difficilmente ha soluzione intera.

Seppoi lo trovate il Repunit-Carmichael siete da record!

Quanto conta ridurre un esponente? Quasi sicuramente non serve. Si riduce di 1 bit o qualcosina di più.

Ma è più veloce:
2^a mod a = 2 mod a

piuttosto che
2^a-1 mod a = 1 mod a

o addirittura tecniche ulteriori di divisione di a-1 per fattori anche primi.

Quello che conta è, invece, il numero di operazioni impiegate per il ModExp. Più si riducono e più il software diventa veloce (Sapreste trovare un metodo più corto?).

Un altro Metodo simile
Nei primi 100 milioni di numeri ci sono solo 255 numeri di Carmichael e
più si va oltre e più si rerafanno. Solo che è stato dimostrato il Teorema:"I numeri di Carmichael sono infiniti." (Uffa!)

L'idea delle equazioni però è sempre alla base di queste cose ed ha fatto già accendere la lampadina a qualcun altro (gli americani la lampadina la chiamano quoziente intelletivo "ah!") : Miller-Rabin.

Se nella (2) poniamo che n-1= 2^t * u dove u è dispari e t>=1, allora la (2) è equivalente a:

(3) a^u*(2t) = mod n

In sostanza la (3) suggerisce di calcolare a^u mod n e poi di elevare il risultato al quadrato per t volte!

Inizialmente è:
x0 = a^u mod n
ad ogni step invece:
xi = xi-1^2 mod n

per cui alla fine abbiamo l'equazione xt^n-1 = 1 mod n (oppure -1 mod n)

Poichè l'unità mod n ha radici non banali se e solo se il numero non è un primo, allora è possibile creare una funzione witness(a,n) che se durante l'elevazione al quadrato trova una radice banale dell'unità modulo n allora restituisce subito 0, se non trova radici non banali restituisce alla fine 1. Si deve però provare con diverse basi tra 1 e n: per tutte deve essere verificato.

Vediamo come si comporta con un numero primo. Supponiamo che n=29 allora n-1 = 28 = 2^2 * 7.

Sia a=10. Qui 2^t=2^2 u=7, t=2 allora è:
x0 = 10^u mod n = 10^7  mod 29 = 17
x1 = x0^2 mod n = 17^2 mod 29 = 28
x2 = x1^2 mod n = 28^2 mod 29 = 1  STOP (la radice banale sintomo di primo!)

Sia a=2. Qui 2^t=2^2 u=7, t=2 allora è:
x0 = 2^u mod n = 2^7  mod 29 = 12
x1 = x0^2 mod n = 12^2 mod 29 = 28
x2 = x1^2 mod n = 28^2 mod 29 = 1  STOP (la radice banale sintomo di primo!)

Se si verifica tra 1 e n,  è sempre lo stesso discorso. Quindi è primo.

Vediamo n=561 che è un numero di Carmichael, allora n-1 = 560 = 2^4 * 35. Supponiamo che la base scelta sia 2. Qui 2^t=2^4 u=35, t=4 allora è:

x0 = 2^u  mod n = 2^35  mod 560 = 368
x1 = x0^2 mod n = 368^2 mod 560 = 464
x2 = x1^2 mod n = 464^2 mod 560 = 256
x3 = x2^2 mod n = 256^2 mod 560 = 16
x4 = x3^2 mod n =  16^2 mod 560 = 16

Se si ripete per a=10

x0 = 10^u  mod n = 10^35  mod 560 = 320

x1 = x0^2 mod n = 320^2 mod 560 = 480
x2 = x1^2 mod n = 464^2 mod 560 = 240
x3 = x2^2 mod n = 256^2 mod 560 = 480
x4 = x3^2 mod n =  16^2 mod 560 = 240

Uhmmm ...

E' composto.


Quante basi?
Ce lo suggeriscono due teoremi

Teorema 1
Se n e' un numero dispari non primo, allora il numero di elementi per cui la funzione witness da esito positivo sono almeno (n−1)/2.

Teorema 2
Per ogni intero dispari n > 2 e per ogni intero positivo b (numero di base), la probabilità che Miller-Rabin(n,b) si sbagli è al massimo 2^−b.

Quindi la scelta di b >= 40 potrebbero essere sufficienti, grazie ad una probabilità migliore al solo PTF su 100 basi.

Riferimentihttp://www.numericana.com/answer/modular.htm#carmlarge
http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html

Nessun commento:

Posta un commento