Abbiamo visto nei due blog precedenti il Piccolo Teorema di Fermat (PTF) e la generalizzazione di Eulero,
che qui riassumiamo brevemente:
a^n-1 mod n = 1 mod n (1)
a^phi(n) mod n = 1 mod n (2)
dove phi(n) è la funzione totiente di Eulero. Se p=n phi(n) = p-1 e la (2) e la (1) sono equivalenti. La funzione totiente phi(n) è l'insieme di numeri minori di n coprimi con n. Ad esempio phi(8) = 4, perchè i numeri minori di 8 e coprimi con esso sono: 1,3,5,7. Se n è un numero primo ad esempio phi(7) = 6; infatti coprimi con 7 sono: 1,2,3,4,5,6.
La cosa funziona sia con a e n coprimi che non. Se non sono coprimi, si parla di pseudo-primalità di n
rispetto alla base a.
Questo torna utile in vari tipi di problemi. Ad esempio se volessimo sapere qual è l'ultima cifra di 7^222?
Oppure ridurre l'esponente nel calcolo del modulo? Qua è importante che a e n siano coprimi.
Ora 7^222 mod 10 hanno 7 e 10 coprimi e phi(10)=4 {1,3,7,9}.
Dalla (2) allora è 7^4 mod 10 = 1 mod 10 (3).
Per cui tenendo conto della (3)
7^222 mod 10 = 7^4*55+2 mod 10 = 7^(4*55) * 7^2 mod 10 = 1^55 * 7^2 mod 10 = 9 mod 10
Questa tecnica funziona se a ed n sono coprimi e si ottiene elevando la base a al valore phi(n); difatti
se x = y mod phi(n) allora a^x = a^y mod n. Inoltre è quella più "rapida".
Cosa si risparmia? Facciamo il binary(x)
? binary(222)
%1 = [1, 1, 0, 1, 1, 1, 1, 0]
? binary(2)
%2 = [1, 0]
Si risparmia molto, ma è un metodo lento per il test di primalità; adesso vediamo perchè.
Prima beffa
Nel caso di 2^240 mod 241 = 1 mod 241 possiamo fare phi(241)=240 [qua già sappiamo che 241 è primo],
il problema è di avere una eulerphi() che deve fare il MCD (algoritmo di Euclide) di tutti i numeri tra 1 e 241, contando quelli che hanno MCD(x,241)=1. Se il numero è molto più grande di 241, il metodo è lento e richiede, tra l'altro, una pre-elaborazione per la riduzione.
Seconda beffa
Nella primalità quanto si risparmia in bit? nulla : 2^240 mod 241 = 2^240*1 mod 241.
Un'altra idea
L'idea allora è quella di ridurre l'esponente dividendolo per un divisore e trasformare il test:
a^n-1 mod n = 1 mod n
La relazione di sopra comporta che se n è il numero dispari sotto test, n-1 è un pari sicuramente divisibile per 2 ... Per grossi valori di n (n-1)/2 è intero; allora nel caso precedente avremo 2^120 mod 241. Ma quanto abbiamo risparmiato? Facciamo anche qui il binary(x)
? binary(240)
%9 = [1, 1, 1, 1, 0, 0, 0, 0]
? binary(120)
%10 = [1, 1, 1, 1, 0, 0, 0]
Si risparmia un solo bit!! Poco se vogliamo. Conviene quasi di lasciar fare al ModExp col numero integro.
La discussione dimostra in modo semplice, senza tirar fuori la teoria della complessità che la velocità non si ottiene dalla riduzione dell'esponente ma dal numero di step necessari all'operazione modulo. Inoltre il test di primalità se vuole diventare più veloce necessita di ridurre molto il numero di basi di prova.
Alla prox.
giovedì 7 ottobre 2010
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
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
domenica 3 ottobre 2010
Il modulo: strumento per test di primalità e crittografia
I test di primalità sono spesso una combinazione di due tecniche:
- evidenziano rapidamente se un numero è composto
- se non è composto devono avere un algoritmo rapido di primalità: deterministico (AKS, Lehmer, etc) o
probabilistico (Miller-Rabin, Fermat, etc)
Oggi la "grande sfida numerica" per gli sviluppatori, i matematici e chi si interessa di hardware per tali tipi di problemi (primalità), è realizzare hw e/o algoritmi più efficienti di quelli disponibili, anche attraverso lo sviluppo di nuovi Teoremi di Teoria dei numeri.
E' noto che per verificare la primalità di un numero primo o anche per generare le chiavi pubbliche e private
(vedi RSA) nella crittografia, si fa uso dell'operatore aritmetico modulo, che restituisce il resto della divisione intera.
Ad esempio nel Piccolo Teorema di Fermat è noto che "se a^p-1 mod p = 1 mod p allora p è primo. Per evitare i numeri di Carmichel si testa per diverse basi per cui si individua un numero che molto probabilmente è primo.
Il problema che nasce è che se p-1 è un numero molto elevato a^p-1 mod p richiede un tempo notevole di calcolo.
Per tale motivo si usano "tecniche di riduzione" per velocizzare il calcolo, effetto che si nota soprattutto se il numero è di "grandissime dimensioni".
Se ad esempio a=2345 b=2345678 c=341 allora a^b mod c si può sostituire con a^c mod b. Se questo è conveniente perchè adesso l'esponente è minore, col Piccolo Teorema di Fermat non è conveniente; difatti da a^p-1 mod p si passa a a^p mod p-1 come l'algoritmo che segue (ma abbiamo peggiorato le cose sostituendo p-1 con p):
/*
** Simple Method
*/
pMod(base,exponent,modulus)= local(ret=1); {
ret = lift(Mod(base, modulus)^exponent);
return(ret);
}
Un'altra possibilità, se l'esponente è troppo grande, in Mod(a,N)^n è di usare una riduazione del tipo Mod(n, phi(N)), dove phi(N) è la funzione totiente di Eulero.
Una modalità più efficiente è di lavorare con gli esponenti in binario ( tra l'altro sono possibili creazioni
di processori che lavorano in questo modo): tale tecnica è nota come "exponentiation squaring", proposta
da Bruce Schneier nel suo Applied Cryptography, 2e, ISBN 0471117099. Questo metodo richiede un tempo costante indipendente dall'input, si dice che è a complessità lineare.
/*
** Fast Mod Exp: exponentiation by squaring
**
** Concrete implementation by R. Turco
*/
ModExp(base,exponent, modulus) = local(ret=1,i=1); {
b = binary(exponent);
i = length(b);
while(exponent>0 & i>0,
if(b[i]==1,
ret = lift(Mod((ret * base), modulus));
);
exponent = exponent >> 1;
base = lift(Mod((base * base), modulus));
i--;
);
return(ret);
}
La tecnica mette insieme anche l'altra tecnica dello "Square e Multiply" che vediamo di seguito, anche questa con esponenziazione binaria:
/*
** Square & Multiply
**
*/
SqMod(base,exponent,modulus)= local(residue=1); {
b = binary(exponent);
len = length(b);
for(i=1,len,
residue=(lift(Mod(residue,modulus)^2)*(base^b[i])) % modulus;
);
return(residue);
}
Lo square & multiply, usato nel RSA o altri come AES per le chiavi, potrebbe essere soggetto ad attacchi furbi per il crack delle chiavi stesse.
Esistono anche altri algoritmi basati sulla tecnica "Montgomery reduction" e varianti come la "Barrett’s reduction" che usano un pre-processing e che sono interessanti per la produzione di HW ad hoc (sia basati sul binario ma preferibilmente sulle word). La "Montgomery reduction" è possibile anche sulle curve ellittiche GF(2^k).
Riferimenti
http://en.wikipedia.org/wiki/Montgomery_reduction
http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
http://en.wikipedia.org/wiki/RSA
http://www.it.uu.se/edu/course/homepage/security/vt09/labs/lab2
Propri lavori su tecniche di primalità
http://www.gruppoeratostene.com/articoli/PrimTech.pdf
http://www.gruppoeratostene.com/articoli/Rtc2009.pdf
http://www.gruppoeratostene.com/articoli/PDC.pdf
http://www.gruppoeratostene.com/articoli/Mersenne.pdf
http://www.gruppoeratostene.com/articoli/Rtac.pdf
Implementazioni Software
http://www.gruppoeratostene.com/programmi/programmi.htm
- evidenziano rapidamente se un numero è composto
- se non è composto devono avere un algoritmo rapido di primalità: deterministico (AKS, Lehmer, etc) o
probabilistico (Miller-Rabin, Fermat, etc)
Oggi la "grande sfida numerica" per gli sviluppatori, i matematici e chi si interessa di hardware per tali tipi di problemi (primalità), è realizzare hw e/o algoritmi più efficienti di quelli disponibili, anche attraverso lo sviluppo di nuovi Teoremi di Teoria dei numeri.
E' noto che per verificare la primalità di un numero primo o anche per generare le chiavi pubbliche e private
(vedi RSA) nella crittografia, si fa uso dell'operatore aritmetico modulo, che restituisce il resto della divisione intera.
Ad esempio nel Piccolo Teorema di Fermat è noto che "se a^p-1 mod p = 1 mod p allora p è primo. Per evitare i numeri di Carmichel si testa per diverse basi per cui si individua un numero che molto probabilmente è primo.
Il problema che nasce è che se p-1 è un numero molto elevato a^p-1 mod p richiede un tempo notevole di calcolo.
Per tale motivo si usano "tecniche di riduzione" per velocizzare il calcolo, effetto che si nota soprattutto se il numero è di "grandissime dimensioni".
Se ad esempio a=2345 b=2345678 c=341 allora a^b mod c si può sostituire con a^c mod b. Se questo è conveniente perchè adesso l'esponente è minore, col Piccolo Teorema di Fermat non è conveniente; difatti da a^p-1 mod p si passa a a^p mod p-1 come l'algoritmo che segue (ma abbiamo peggiorato le cose sostituendo p-1 con p):
/*
** Simple Method
*/
pMod(base,exponent,modulus)= local(ret=1); {
ret = lift(Mod(base, modulus)^exponent);
return(ret);
}
Un'altra possibilità, se l'esponente è troppo grande, in Mod(a,N)^n è di usare una riduazione del tipo Mod(n, phi(N)), dove phi(N) è la funzione totiente di Eulero.
Una modalità più efficiente è di lavorare con gli esponenti in binario ( tra l'altro sono possibili creazioni
di processori che lavorano in questo modo): tale tecnica è nota come "exponentiation squaring", proposta
da Bruce Schneier nel suo Applied Cryptography, 2e, ISBN 0471117099. Questo metodo richiede un tempo costante indipendente dall'input, si dice che è a complessità lineare.
/*
** Fast Mod Exp: exponentiation by squaring
**
** Concrete implementation by R. Turco
*/
ModExp(base,exponent, modulus) = local(ret=1,i=1); {
b = binary(exponent);
i = length(b);
while(exponent>0 & i>0,
if(b[i]==1,
ret = lift(Mod((ret * base), modulus));
);
exponent = exponent >> 1;
base = lift(Mod((base * base), modulus));
i--;
);
return(ret);
}
La tecnica mette insieme anche l'altra tecnica dello "Square e Multiply" che vediamo di seguito, anche questa con esponenziazione binaria:
/*
** Square & Multiply
**
*/
SqMod(base,exponent,modulus)= local(residue=1); {
b = binary(exponent);
len = length(b);
for(i=1,len,
residue=(lift(Mod(residue,modulus)^2)*(base^b[i])) % modulus;
);
return(residue);
}
Lo square & multiply, usato nel RSA o altri come AES per le chiavi, potrebbe essere soggetto ad attacchi furbi per il crack delle chiavi stesse.
Esistono anche altri algoritmi basati sulla tecnica "Montgomery reduction" e varianti come la "Barrett’s reduction" che usano un pre-processing e che sono interessanti per la produzione di HW ad hoc (sia basati sul binario ma preferibilmente sulle word). La "Montgomery reduction" è possibile anche sulle curve ellittiche GF(2^k).
Riferimenti
http://en.wikipedia.org/wiki/Montgomery_reduction
http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
http://en.wikipedia.org/wiki/RSA
http://www.it.uu.se/edu/course/homepage/security/vt09/labs/lab2
Propri lavori su tecniche di primalità
http://www.gruppoeratostene.com/articoli/PrimTech.pdf
http://www.gruppoeratostene.com/articoli/Rtc2009.pdf
http://www.gruppoeratostene.com/articoli/PDC.pdf
http://www.gruppoeratostene.com/articoli/Mersenne.pdf
http://www.gruppoeratostene.com/articoli/Rtac.pdf
Implementazioni Software
http://www.gruppoeratostene.com/programmi/programmi.htm
Iscriviti a:
Post (Atom)
Post
