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

--===============1767709540==
Content-type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable

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=C3=A0, ma non riesco a ricordare quali...=20
> Non so se questo c'entri con le ottimizzazioni fatte per la
> fattorizzazione, ma sicuramente =C3=A8 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=C3=A0 un piccolo fattore, quindi in effet=
ti
> dubito abbiano avuto bisogno del test di LL, dato che non dice niente
> pi=C3=B9 che se ne ha o meno).

Il test non c'entra niente, anche perch=C3=A9 =C3=A8 banale verificare ch=
e quel
numero non =C3=A8 primo: ad esempio, 3^(2^1039-2) non =C3=A8 congruente a=
d uno
modulo 2^1039 - 1

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

Ottavio


--===============1767709540==
Content-Type: text/plain; charset="iso-8859-1"
MIME-Version: 1.0
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

________________________________________________________
http://www.sikurezza.org - Italian Security Mailing List
--===============1767709540==--