MM37156667 = 2^( 2^37156667 - 1 ) - 1 is prime?!
Giochiamo con i numeri di Mersenne: Mersenne, Goldbach e vulnerabilità del RSA
MM37156667 = 2^( 2^37156667 - 1 ) - 1 is prime?! Boh! chi lo dice? E' un numero supercolossale, per testarlo ai vari progetti dedicati ai numeri primi di Mersenne occorrono anni.
Al momento anche PARI/GP solo per rappresentare l'esponente in parentesi ha difficoltà di memoria RAM, pur facendo allocatemem(500*1024*1024) il software ed il PC si rifiutano.
Il titolo è provocatorio. L'unica sarebbe riuscire a progettare un Teorema valido e semplice per superare i limiti anche elaborativi e il tempo elevato necessario a elaborare.
Attualmente nei vari progetti si usa trovare un piccolo fattore per dimostrare che il numero è composto.
Proviamo a vedere cosa oggi si può dire di nuovo (rispetto al test di Lucas-Lehmer).
Lemma 1
A Mersenne's prime number Mp is always of form 4k+3.
Dem. Lemma 1
If Mp=2^p-1=4k+1 then
4k+1=2^p-1 -> 4k+2=2^p-> 2(2k+1)=2^p -> 2k+1 = 2^(p-1)
It's absurd: odd=even!
So
if Mp=2^p-1=4k+3 then
4k+3=2^p-1 -> 4k+4=2^p-> 4(k+1)=2^p -> k+1 = 2^(p-2) -> k=2^(p-2)-1
it is possible.
Euler showed:
Theorem: If k>1 and p=4k+3 is prime, then 2p+1 is prime if and only if 2p = 1 (mod 2p+1).
so
Lemma 2
if p=4k+3 or p=4k-1 a prime number and 2p+1 is a prime number then the Mersenne number 2^p-1 is composite.
Lemma 3
Let be p = 4k-1 a prime number, with k>0 and k = 0 mod 3 and S=2p+1 is prime then Mp=2^p-1 isn't a prime number.
Dem.
It follows from Lemma 2
Examples:
p=11=4*2+3=4*3-1 k=3*1 S=2*11+1=23 prime Mp=2^11-1 not prime
p=23=4*5+3=4*6-1 k=3*2 S=2*23+1=47 prime Mp=2^23-1 not prime
In some case Mp must be verified:
p=47=4*11+3=4*12-1 k=3*4 S=2p+1 not prime Mp? Mp =2^47-1 not prime
Lemma 5
If W =(4k+5)/3 is an odd with k>1 and W>3, if W is a Wagstaff's prime number then k = Mp is a Mersenne's prime Number with k=(3W-5)/4 integer.
Dem.
If W is a Wagstaff's prime number then w=(2^p+1)/3 an p is a prime number.
Mp= 2^p-1 so W=(Mp+2)/3 but from Lemma 1 Mp=4k+3 then W=(4k+5)/3
If p is a prime number and W a Wagstaff prime number then k is integer and a Mersenne's prime number.
We know
Let p and q be primes. If q divides Mp = 2^p-1, then
q = +/-1 (mod 8) and q = 2kp + 1 for some integer k.
For example:
Mp=2^11-1
q= 2*11+1=23
Mp/q= 89
Mp isn't a Mersenne's prime!
-1 mod 8 is equal also 7 mod 8.
In this mode we can show if Mp is composite, but also MMp because MMp = 2^Mp - 1
Theorem New Mersenne Conjecture
For each p prime number, if are true two conditions:
a. p=2^k ± 1 or p = 4^k ± 3.
b. (2^p + 1) / 3 is a prime number (Wagstaff) then
Mp=2^p-1 is a Mersenne's prime number.
Dem. The demonstration follows from lemmas previous. If Lemma 3 is true (p = 4k-1 with k>1 and k=0 mod3), Mp isn't a prime, so to avoid that we can choose p=2^k± 1
For example:
2^2+1=4*1+1=5
2^4+1=4*4+1=17
2^8+1=4*64+1=257
The prime numbers of form 4^k± 3 are of type 4k±3 and in this mode i can find Mersenne's prime numbers.
Giochiamo con i numeri di Mersenne
Siano p e q dei numeri primi.
p*q = A (1)
p+q = B (2)
La A in (1) è notoriamente un semiprimo RSA. La (2) è l'equivalente della congettura forte di Goldbach: "ogni numero naturale pari e maggiore di 2 è somma di due numeri primi".
In realtà notoriamente la (1) e la (2) danno il prodotto e la somma delle due radici di una equazione di secondo grado del tipo ax^2+bx+c = 0.
Dalla (1) e la (2) si arriva a scoprire sia p che q e a crackare l'RSA (Vedi "Sulle spalle dei giganti").
L'unica difesa è far sì che p e q siano molto grandi in termini di numero di cifre (al di sopra di 100).
Ma se p e q sono numeri primi di Mersenne, che succede?
Supponiamo:
p=2^a-1 numero primo di Mersenne con a numero primo
q=2^b-1 numero primo di Mersenne con b numero primo
Quindi la (1) e la (2) diventano:
(2^a-1)*(2^b-1) = A (1)
2^a+2^b-2 = B (2)
Proviamo a sommare membro a membro la (1) e la (2).
2^(a+b) - 2^a - 2^b + 1 + 2^a + 2^b - 2 = A + B
ovvero:
2^(a+b)-1 = A+B (3)
Proprietà :
"In generale sommando il prodotto di due numeri primi di Mersenne (1) A=2^a-1 e B=2^b-1, con a maggiore di 1 e b maggiore di 1, con la somma degli stessi due numeri primi di Mersenne (2) si ottiene un nuovo numero di Mersenne (3), non necessariamente primo, il cui esponente è la somma dei precedenti esponenti".
"Se la somma degli esponenti nella (3) è pari sia a>2 che b>2 e dispari".
"Se la somma deglil esponenti nella (3) è pari A+B=2^(a+b)-1 sarà sempre composto"
Esempi
(2^2-1)*(2^3-1) = 21
(2^2-1)+(2^3-1) = 10
la somma effettivamente mi dà 31 = 2^(2+3) -1 = 2^5-1 numero primo.
(2^3-1)*(2^7-1) = 889
(2^3-1)+(2^7-1) = 134
2^10-1 = 1023 non numero primo.
Mersenne, Goldbach e vulnerabilità del RSA
La (1) e la (2) possono crackare l'RSA, ma il fatto che due numeri primi siano di Mersenne aiuta?
Purtroppo sì, grazie alla (3).
Facciamo un esempio A=889
Cerchiamo per tentativi il primo numero di Mersenne dopo 889 con M=2^x-1 e incrementando x=3..n con passo 2 si trova x=10 con M=1023 da cui: A+B=1023 con A=889 già noto; x=a+b=10 ovviamente a minore di 10 e b minore di 10 ed a e b sono dispari e primi e maggiori di 2.
Allora è applicabile Goldbach a x e troviamo tutte le coppie che danno x=10 e che rispettano la (1) ovvero a=3 b=7; per cui ritornando nella (1) A è scomposto in fattori e senza nemmeno verificare la primalità di a e b.
Ma occorre sommare a x sempre 2? in realtà no. Perchè già al primo tentativo si sa quanto bassi si è con M rispetto al valore A ed è possibile decidere di incrementare x anche per multipli maggiori di 2.
Dov'è il vantaggio? Se i due numeri primi di Mersenne sono enormi, anzicchè scomporre in fattori A e lavorare con la moltiplicazione, ci riconduciamo alla somma dei due esponenti: numeri di dimensione inferiore.
Questo vuol dire ad esempio che certe implementaziondi di RSA, se non ben curate, sono vulnerabili!!
Da tali implementazioni vanno escluse la generazione dei numeri primi che sono:
- numeri primi di Sophie Germain S=2p+1 con S e p primi
- numeri gemelli
- numeri primi di Mersenne
- primi che producono quadrati perfetti
- numeri primi che producono numeri perfetti
- numeri primi Repunit (quelli in base 2 sono i numeri di Mersenne)
Conclusioni
Quali sarebbero le conseguenze di saper testare la primalità degi MMp?
1. Avremmo un nuovo test di primalità per gli MMp
2. Estenderemo la frontiera della conoscenza dei numeri primi a numeri molto più grandi, a partire dai vari record ed ex-record di cui possediamo un lista
3. Faremo un passo avanti sulla verifica dell'infinità dei numeri primi di Mersenne
4. Già adesso possiamo comprendere meglio le vulnerabilità dei codici e come generare i numeri primi
Alla prossima
Al momento anche PARI/GP solo per rappresentare l'esponente in parentesi ha difficoltà di memoria RAM, pur facendo allocatemem(500*1024*1024) il software ed il PC si rifiutano.
Il titolo è provocatorio. L'unica sarebbe riuscire a progettare un Teorema valido e semplice per superare i limiti anche elaborativi e il tempo elevato necessario a elaborare.
Attualmente nei vari progetti si usa trovare un piccolo fattore per dimostrare che il numero è composto.
Proviamo a vedere cosa oggi si può dire di nuovo (rispetto al test di Lucas-Lehmer).
Lemma 1
A Mersenne's prime number Mp is always of form 4k+3.
Dem. Lemma 1
If Mp=2^p-1=4k+1 then
4k+1=2^p-1 -> 4k+2=2^p-> 2(2k+1)=2^p -> 2k+1 = 2^(p-1)
It's absurd: odd=even!
So
if Mp=2^p-1=4k+3 then
4k+3=2^p-1 -> 4k+4=2^p-> 4(k+1)=2^p -> k+1 = 2^(p-2) -> k=2^(p-2)-1
it is possible.
Euler showed:
Theorem: If k>1 and p=4k+3 is prime, then 2p+1 is prime if and only if 2p = 1 (mod 2p+1).
so
Lemma 2
if p=4k+3 or p=4k-1 a prime number and 2p+1 is a prime number then the Mersenne number 2^p-1 is composite.
Lemma 3
Let be p = 4k-1 a prime number, with k>0 and k = 0 mod 3 and S=2p+1 is prime then Mp=2^p-1 isn't a prime number.
Dem.
It follows from Lemma 2
Examples:
p=11=4*2+3=4*3-1 k=3*1 S=2*11+1=23 prime Mp=2^11-1 not prime
p=23=4*5+3=4*6-1 k=3*2 S=2*23+1=47 prime Mp=2^23-1 not prime
In some case Mp must be verified:
p=47=4*11+3=4*12-1 k=3*4 S=2p+1 not prime Mp? Mp =2^47-1 not prime
Lemma 5
If W =(4k+5)/3 is an odd with k>1 and W>3, if W is a Wagstaff's prime number then k = Mp is a Mersenne's prime Number with k=(3W-5)/4 integer.
Dem.
If W is a Wagstaff's prime number then w=(2^p+1)/3 an p is a prime number.
Mp= 2^p-1 so W=(Mp+2)/3 but from Lemma 1 Mp=4k+3 then W=(4k+5)/3
If p is a prime number and W a Wagstaff prime number then k is integer and a Mersenne's prime number.
We know
Let p and q be primes. If q divides Mp = 2^p-1, then
q = +/-1 (mod 8) and q = 2kp + 1 for some integer k.
For example:
Mp=2^11-1
q= 2*11+1=23
Mp/q= 89
Mp isn't a Mersenne's prime!
-1 mod 8 is equal also 7 mod 8.
In this mode we can show if Mp is composite, but also MMp because MMp = 2^Mp - 1
Theorem New Mersenne Conjecture
For each p prime number, if are true two conditions:
a. p=2^k ± 1 or p = 4^k ± 3.
b. (2^p + 1) / 3 is a prime number (Wagstaff) then
Mp=2^p-1 is a Mersenne's prime number.
Dem. The demonstration follows from lemmas previous. If Lemma 3 is true (p = 4k-1 with k>1 and k=0 mod3), Mp isn't a prime, so to avoid that we can choose p=2^k± 1
For example:
2^2+1=4*1+1=5
2^4+1=4*4+1=17
2^8+1=4*64+1=257
The prime numbers of form 4^k± 3 are of type 4k±3 and in this mode i can find Mersenne's prime numbers.
Giochiamo con i numeri di Mersenne
Siano p e q dei numeri primi.
p*q = A (1)
p+q = B (2)
La A in (1) è notoriamente un semiprimo RSA. La (2) è l'equivalente della congettura forte di Goldbach: "ogni numero naturale pari e maggiore di 2 è somma di due numeri primi".
In realtà notoriamente la (1) e la (2) danno il prodotto e la somma delle due radici di una equazione di secondo grado del tipo ax^2+bx+c = 0.
Dalla (1) e la (2) si arriva a scoprire sia p che q e a crackare l'RSA (Vedi "Sulle spalle dei giganti").
L'unica difesa è far sì che p e q siano molto grandi in termini di numero di cifre (al di sopra di 100).
Ma se p e q sono numeri primi di Mersenne, che succede?
Supponiamo:
p=2^a-1 numero primo di Mersenne con a numero primo
q=2^b-1 numero primo di Mersenne con b numero primo
Quindi la (1) e la (2) diventano:
(2^a-1)*(2^b-1) = A (1)
2^a+2^b-2 = B (2)
Proviamo a sommare membro a membro la (1) e la (2).
2^(a+b) - 2^a - 2^b + 1 + 2^a + 2^b - 2 = A + B
ovvero:
2^(a+b)-1 = A+B (3)
Proprietà :
"In generale sommando il prodotto di due numeri primi di Mersenne (1) A=2^a-1 e B=2^b-1, con a maggiore di 1 e b maggiore di 1, con la somma degli stessi due numeri primi di Mersenne (2) si ottiene un nuovo numero di Mersenne (3), non necessariamente primo, il cui esponente è la somma dei precedenti esponenti".
"Se la somma degli esponenti nella (3) è pari sia a>2 che b>2 e dispari".
"Se la somma deglil esponenti nella (3) è pari A+B=2^(a+b)-1 sarà sempre composto"
Esempi
(2^2-1)*(2^3-1) = 21
(2^2-1)+(2^3-1) = 10
la somma effettivamente mi dà 31 = 2^(2+3) -1 = 2^5-1 numero primo.
(2^3-1)*(2^7-1) = 889
(2^3-1)+(2^7-1) = 134
2^10-1 = 1023 non numero primo.
Mersenne, Goldbach e vulnerabilità del RSA
La (1) e la (2) possono crackare l'RSA, ma il fatto che due numeri primi siano di Mersenne aiuta?
Purtroppo sì, grazie alla (3).
Facciamo un esempio A=889
Cerchiamo per tentativi il primo numero di Mersenne dopo 889 con M=2^x-1 e incrementando x=3..n con passo 2 si trova x=10 con M=1023 da cui: A+B=1023 con A=889 già noto; x=a+b=10 ovviamente a minore di 10 e b minore di 10 ed a e b sono dispari e primi e maggiori di 2.
Allora è applicabile Goldbach a x e troviamo tutte le coppie che danno x=10 e che rispettano la (1) ovvero a=3 b=7; per cui ritornando nella (1) A è scomposto in fattori e senza nemmeno verificare la primalità di a e b.
Ma occorre sommare a x sempre 2? in realtà no. Perchè già al primo tentativo si sa quanto bassi si è con M rispetto al valore A ed è possibile decidere di incrementare x anche per multipli maggiori di 2.
Dov'è il vantaggio? Se i due numeri primi di Mersenne sono enormi, anzicchè scomporre in fattori A e lavorare con la moltiplicazione, ci riconduciamo alla somma dei due esponenti: numeri di dimensione inferiore.
Questo vuol dire ad esempio che certe implementaziondi di RSA, se non ben curate, sono vulnerabili!!
Da tali implementazioni vanno escluse la generazione dei numeri primi che sono:
- numeri primi di Sophie Germain S=2p+1 con S e p primi
- numeri gemelli
- numeri primi di Mersenne
- primi che producono quadrati perfetti
- numeri primi che producono numeri perfetti
- numeri primi Repunit (quelli in base 2 sono i numeri di Mersenne)
Conclusioni
Quali sarebbero le conseguenze di saper testare la primalità degi MMp?
1. Avremmo un nuovo test di primalità per gli MMp
2. Estenderemo la frontiera della conoscenza dei numeri primi a numeri molto più grandi, a partire dai vari record ed ex-record di cui possediamo un lista
3. Faremo un passo avanti sulla verifica dell'infinità dei numeri primi di Mersenne
4. Già adesso possiamo comprendere meglio le vulnerabilità dei codici e come generare i numeri primi
Alla prossima
Post
Fantastico !!!!!!!!!!!!!!!
RispondiElimina