1017 bit getal gefactoriseerd
Een nieuw record: onderzoekers van Nippon Telegraph and Telephone Corporation hebben in samenwerking met de universiteit van Bonn en de Ecole Polytechnique Fédérale te Lausanne (EFPL) voor het eerst een getal van meer dan 1000 bits gefactoriseerd. Ze gebruikten hiervoor de Special Number Field Sieve. Het vorige record met dit factorisatiealgoritme bedroeg 911 bits. Het nieuwe resultaat: (21039-1)/5080711 is gelijk aan:
55 853 666 619 936 291 260 749 204 658 315 944 968 646 527 018 488 637 648 010 052 346 319 853 288 374 753
x
20 758 181 946 442 382 764 570 481 370 359 469 516 293 970 800 739 520 988 120 838 703 792 729 090 324 679 382 343 143 884 144 834 882 534 053 344 769 112 223 028 158 327 696 525 376 091 410 189 105 241 993 899 334 109 711 624 358 962 065 972 167 481 161 749 004 803 659 735 573 409 253 205 425 523 689
De factoren zijn respectievelijk 80 en 227 cijfers lang. De onderzoekers gebruikten een zeefprogramma dat aan de universiteit van Bonn ontwikkeld was en voerden de berekening uit in een tijd equivalent met 95 jaar op een Pentium D 3 GHz. Na het zeven komt een stap lineaire algebra: in totaal 146 pc’s voerden parallel berekeningen uit gedurende iets meer dan 2 maanden. De resultaten waren 47 niet-triviale oplossingen van het stelsel van vergelijkingen gedefinieerd door een 70 miljoen bij 70 miljoen grote spaarse matrix. Hieruit konden de onderzoekers dan in de laatste stap de factoren berekenen.
In een persbericht van de EFPL zegt Arjen Lenstra, één van de betrokken onderzoekers, dat dit getal het grootste speciale en moeilijk te factoriseren getal is. Lenstra ontwikkelde de Special Number Field Sieve in de late jaren 1980 samen met zijn broer Hendrik Lenstra en de wiskundigen John Pollard en Mark Manasse.
De moeilijkheid van het factoriseren van grote getallen is de basis van de beveiliging van heel wat internetverkeer, zoals elektronische banktransacties en digitale handtekeningen met RSA- en DSA-encryptie. Encryptie met 1024 bit RSA-sleutels, die nog heel wijdverbreid zijn, wordt met deze factorisatie stilletjesaan achterhaald. Het gefactoriseerde getal van 1017 bits heeft wel een speciale vorm (het is een Mersennegetal gedeeld door een kleine factor), dus is de factorisatie gemakkelijker dan die van een RSA-sleutel, maar de techniek kan in principe gegeneraliseerd worden. Beveiligingsexpert Bruce Schneier raadt dan ook (al jaren) aan om grotere RSA-sleutels te gebruiken. Ook Lenstra zegt dat de uren van 1024 RSA-sleutels geteld zijn:
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.
Addendum: zie het artikel Veiligheid RSA-encryptie in gevarenzone op Kennislink voor een uitgebreidere versie van dit artikel.
Grote getallen factoriseren at QED on 09 Aug 2007 at 12:21 pm
[...] In het septembernummer van PC-Active gaat mijn Denkwerk-rubriek over het factoriseren van grote getallen. Aanleiding was de factorisatie van 21039 - 1 eind mei. Daar begint het artikel dan ook, maar ik bespreek ook vorige records, vooral van de RSA Factoring Challenge. Ik leg ook in grote lijnen de werking van de Rational Sieve uit om getallen te factoriseren. Dit algoritme is nog aan een algemeen geïnteresseerd publiek uit te leggen, omdat de wiskunde erachter heel wat eenvoudiger is dan bij de Special Number Field Sieve die voor het 1017 bits getal gebruikt werd. De algemene structuur van beide algoritmes is echter gelijkaardig. [...]
Gênante wiskundige ontdekking at QED on 03 Jan 2008 at 7:40 pm
[...] Een bezoeker wil het fijne weten over elektronische banktransacties. Waarschijnlijk heeft hij op mijn blog ontdekt dat priemgetallen een belangrijke rol spelen in de beveiliging hiervan. [...]