Warning: Missing argument 2 for wpdb::prepare(), called in /home/stromber/public_html/kryptoblog/wp-content/plugins/wp-super-edit/wp-super-edit.core.class.php on line 109 and defined in /home/stromber/public_html/kryptoblog/wp-includes/wp-db.php on line 1222
Tal på 307 siffror faktoriserat » Kryptoblog

Tal på 307 siffror faktoriserat

May 24th, 2007 by Joachim Strömbergson Leave a reply »

En grupp forskare från Ecole Polytechnique i Lausanne, Frankrike, universitetet i Bonn, Tyskland och NTT i Japan har tillsammans satt ett nytt rekord i primtalsfaktorisering. Talet som faktoriserades var, 21039-1 ett tal med 307 siffror – vilket motsvarar ett tal med 1023 bitar. Det speciella med talet som faktoriserades är att det är nära en jämn tvåpotens, men forskarna anser ändå att resultatet går att överföra till icke speciella tal.

Forskarna använde en variant på number sievetekniken och den distribuerade körningen tog 11 månader och (enl nyhetsblänkaren) krävde ett sekels beräkningskraft (vad det nu är för ett mått.). Forskarna säger själva att resultatet går att applicera på säkerheten för RSAkrypto:

Is the writing on the wall for 1024-bit encryption” “The answer to that question is an unqualified yes,” says Lenstra. For the moment the standard is still secure, because it is much more difficult to factor a number made up of two huge prime numbers, such as an RSA number, than it is to factor a number like this one that has a special mathematical form. But the clock is definitely ticking. “Last time, it took nine years for us to generalize from a special to a non-special hard-to factor number (155 digits). I won’t make predictions, but let’s just say it might be a good idea to stay tuned.”

Även Bruce Schneier har kommenterat resultatet med:
I hope RSA applications would have moved away from 1024-bit security years ago, but for those who haven’t yet: wake up.

Det man kan notera, förutom att det börjar bli hög tid att använda RSA-nycklar på 1024 bitar är att det här resultatet i första hand är baserat på teknisk utveckling och bättre kommunikation, inte ett algoritmiskt faktoriseringsgenombrott. Jag hittade en mer detaljerad beskrivning av faktoriseringen:

We are pleased to announce the factorization of the 1039th Mersenne
number (2,1039- in the Cunningham table) by SNFS.
The factorization is:
2^1039-1 = p7 * p80 * p227 where
p7 = 5080711
p80 = 558536666199362912607492046583159449686465270184886376480100
52346319853288374753
p227 = 207581819464423827645704813703594695162939708007395209881208
387037927290903246793823431438841448348825340533447691122230
281583276965253760914101891052419938993341097116243589620659
72167481161749004803659735573409253205425523689
The factor 5080711 was already known.


Vill du läsa mer finns hela texten att läsa här.

No related posts.

Related posts brought to you by Yet Another Related Posts Plugin.

Advertisement

5 comments

  1. Mikael Nilsson says:

    Primtal kan inte faktoriseras, det är liksom definitionen…

    Jag tror att du menar att ett stort tal som är en produkt av två stora primtal har faktoriserats.

  2. Mikael says:

    Jag gissar att du inte menar att det var ett /primtal/ som faktoriserades 🙂

  3. daVajj says:

    Nu blir jag fundersam, hur faktoriserar man ett primtal? Det här var väl bara ett mersenne-tal, och inget mersenne-primtal?

    http://en.wikipedia.org/wiki/Mersenne_prime
    “In mathematics, a Mersenne number is a number that is one less than a power of two.”

    Ett primtal har ju den unika egenskapen att den inte är uppbyggd av faktorer, utan är delbart bara med sig själv, och ett.

  4. Joachim says:

    Aloha!

    Jajajaja! NI har rätt, det blev felformulerat så det stänkte om det.

  5. Martin says:

    Är det inte ett tal på 313 siffror?

    2^{1039}-1 skrivs med 1039 ettor, då kan det väl inte motsvara ett tal på 1023 bitar?

Leave a Reply

You must be logged in to post a comment.