Re: [crypto] Re: fattorizzato un numero di 1039 bit (Lapo Luchini)

Il giorno ven, 01/06/2007 alle 10.15 +0200, Lapo Luchini ha scritto:
> Spank wrote:
> > Chiedo scusa, ma cos'ha di speciale 2^1039-1 a parte il fatto di
> > essere immenso e di avere 1039 bit settati a uno nella sua
> > rappresentazione binaria? Ricordo dal corso di crittografia che aveva
> > un paio di particolarità, ma non riesco a ricordare quali... 
> Non so se questo c'entri con le ottimizzazioni fatte per la
> fattorizzazione, ma sicuramente è un numero di Mersenne[1] (ovvero nella
> forma 2^p-1 con p primo), quindi hanno potuto usare un test di
> Lucas-Lehmer[2] per essere sicuri a priopri che fosse fattorizzabile
> (d'altra parte conoscevano già un piccolo fattore, quindi in effetti
> dubito abbiano avuto bisogno del test di LL, dato che non dice niente
> più che se ne ha o meno).

Il test non c'entra niente, anche perché è banale verificare che quel
numero non è primo: ad esempio, 3^(2^1039-2) non è congruente ad uno
modulo 2^1039 - 1

Il fatto è che esistono tecniche particolari per fattorizzare i numeri
di Mersenne; quindi, di per sé, aver fattorizzato 2^1039-1 non dice
niente su RSA; ma secondo Lenstra (vedi il mio primo messaggio
sull'argomento) questo non è un buon segno. Non vedo come non si possa
dargli ragione.

Ottavio