M(2n) e la fattorizzazione

M(2n) e la fattorizzazione

Abbiamo visto che i i numeri di Mersenne con esponenti pari non saranno mai primi.

Sono del tipo M(2n)=2^(2n)-1.

Per essi vale sempre una esplicita fattorizzazione del tipo:

x^2 - y^2 = (x - y)*(x + y)

Difatti è:

M(2*n) = 2^(2*n) - 1 = (2^n)^2 - 1^2 = (2^n - 1)*(2^n + 1)
= M(n)*(M(n) + 2)

Per cui se si cercano i fattori di M(2*n) essi sono nient'altro che M(n) e M(n)+2.

Cosa vi ricorda M(n)+2 ? M(n)+2= 3 W Se M(n) è primo W è il Wagstaff number associato!

Una parte del Cunningham Project cerca di trovare con una tecnica simile i fattori 2-,
2+, 2^n-1 per n dispari e 2^n+1 per tutti gli n.

Esiste, difatti, un'altra fattorizzazione algebrica sullo stile della precedente che
può funzionare per i numeri 2+ per determinati n:

2^(4*a - 2) + 1 = (2^(2*a - 1) - 2^a + 1)
*(2^(2*a - 1) + 2^a + 1)
Esempio.

Sappiamo che:
2^14 + 1 = 16385 = 5*29*113

dove n = 14 = 4*a - 2, con a = 4. Da cui:

2^14 + 1 = 2^(4*4 - 2) + 1 = (2^(2*4 - 1) - 2^4 + 1)
*(2^(2*4 - 1) + 2^4 + 1)
= (2^7 - 16 + 1)*(2^7 + 16 + 1)
= (128 - 15)*(128 + 17)
= 113*145
= 113*5*29

Il 5 appare sempre nella fattorizzazione completa 2+ se n è pari.
Ad esempio M(4) = 15 e 5 divide il 15.

Il 3 anche appare sempre, nei 2-
Ad esempio
2^14 - 1 = 16383 = 3*43*127 = 129*127 dove 127= 2^7 - 1 = M(7).


Alla prossima

Scherzi algebrici e geometrici

Scherzi algebrici e geometrici

In Algebra l'equazione di secondo grado è la classica espressione

ax^2+bx+c=0 (1)

In realtà la usiamo tutti i giorni a partire dagli antichi egiziani, anche se
quest'ultimi non lo sapevano e per loro erano fondamentali i problemi di Geometria.

E' noto che le radici o soluzioni di una equazione di secondo grado hanno la proprietà
che:

x1*x2 = A (2)
x1+x2 = B (3)

Se dalla (2) poniamo x2=A/x1 e andiamo nella (2) a sostituire x2 otteniamo
x1 + A/x1 - B = 0

da cui si ottiene:
x1^2 - B*x1 + A = 0 e quindi ritorniamo alla forma generale (1).

Ogni aspetto algebrico ha un significato equivalente geometrico.

Ad esempio:
a. la (2) è l'area di un rettangolo o di un quadrato nel "piano reale" (nell'ambito della geometria Euclidea)
b. la (3) è il semiperimetro del rettangolo o del quadrato


Un momento!

Un'equazione di secondo grado potrebbe avere anche due radici immaginarie; ad esempio:

x1 = +i e x2= -i.

Il che succede ad esempio con l'equazione di secondo grado

x^2+1=0 (con A=1 e B=0).

Uhmmm! OK. Ma qual è il significato geometrico? Dalla (2) L'area = 1 e dalla (3) il semiperimetro = 0.

Buffo! Ma che figure sono nel piano? Esiste una figura del genere?

E' un punto? una retta? Ma dove è localizzata?

Intanto non siamo più nel piano reale, ma in quello immaginario di Gauss e dei numeri complessi.

Ricordiamoci che quando disegniamo un rettangolo o un quadrato nel piano reale, in realtà alla base della figura è associabile l'asse reale delle ascisse; mentre all'altezza della figura l'asse reale delle ordinate.

In questo caso particolare abbiamo a che fare con numeri complessi a+ib senza parte reale (la a).
Quindi siamo nel piano complesso e le figure sono rettangoli o quadrati complessi a cui sono associati l'asse immaginario positivo che va verso l'altro e l'asse immaginario negativo che va verso sinistra.

Simpatico no?

Massimizzazione dell'area.

Usiamo un'altra regolina, quella del quadrato di un binomio e calcoliamo:

(x1+y1)^2 - (x1-y1)^2 = 4x1*x2 (4)

Prima abbiamo visto che x1*x2 è l'area di un rettangolo x1=base e x2=altezza.

Ora sappiamo anche che il perimetro

p=2(x1+x2) (5)

e che l'area = b*h =x1*x2 si può riscrivere quindi sfruttando la (4):

Area = 1/4 * [(p/2)^2 -(x1-x2)^2] = P^2/16 - (x1-x2)^2/4 (6)

La (6) dice che l'Area massima si ha quando x1=x2! ovvero con un quadrato.

Ora lo sapete!

Alla prossima.

MM37156667 = 2^( 2^37156667 - 1 ) - 1 is prime?!

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