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

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).

Link:
1: http://it.wikipedia.org/wiki/Numero_di_Mersenne
2: http://it.wikipedia.org/wiki/Test_di_Lucas_-_Lehmer

-- 
Lapo Luchini
lapo@xxxxxxx (OpenPGP & X.509)
www.lapo.it (Jabber, ICQ, MSN)