Na pograniczu kryptografii i teorii liczb padł kolejny rekord. Herman te Riele z holenderskiego Centrum voor Wiskunde en Informatica (CWI), koordynator zespołu zajmującego się obliczeniową teorią liczb i bezpieczeństwem danych, doniósł 15 listopada 2000 r., że udało się rozłożyć na czynniki pierwsze 233-cyfrową liczbę  . Okazuje się, że jest ona iloczynem 3, 533371 i trzech wielkich liczb pierwszych: 55-cyfrowej:
p1=1737639742 6392540604 3786152134 4464381695 8298023695 22859,
71-cyfrowej:
p2=2320631622 0078396404 3837771355 3426192838 7046186611 0796621434 3452709356 3
i 102-cyfrowej:
p3=7699633399 9503136605 6411302608 8358909907 6538109069 1440459641 1780665083 47 8629462586 9803477350 7820614633.
Uzyskanie tej informacji wymagało pięciomiesięcznych obliczeń. Prowadzono je równolegle, z użyciem algorytmu, zwanego specjalnym sitem teorioliczbowym, na około 150 stacjach roboczych firm SGI i Sun z procesorami 80-450 MHz i około stu komputerach osobistych z procesorami 266-600 MHz. Podczas jednego z etapów użyto superkomputera Cray C90 (jakieś 130 godzin pracy procesora). Łączny czas pracy procesorów wyniósł mniej więcej 57 lat. Ludzki wkład pracy też był niebagatelny: nad rozkładem  na czynniki pracowało 17 informatyków i matematyków z kilku krajów, nie wspominając o osobach postronnych, które wieczorami i podczas weekendów użyczały wolnego czasu obliczeniowego swych komputerów.
Poprzedni rekord należał do tego samego zespołu. W kwietniu 1999 r. stwierdzono, że liczba
 , tzn. liczba 211-cyfrowa zapisana w układzie dziesiątkowym za pomocą samych jedynek, jest iloczynem dwóch liczb pierwszych, 93-cyfrowej i 118-cyfrowej. (Wymagało to ponad 10 lat czasu obliczeniowego, w tym około 100 godzin pracy superkomputera Cray).
Wiara w to, że rozkładanie dużych liczb złożonych na czynniki pierwsze jest zajęciem bardzo trudnym, tkwi u źródeł przekonania o bezpieczeństwie algorytmów szyfrowania z publicznym kluczem, wykorzystywanych m.in. do potwierdzania tożsamości nadawcy podczas elektronicznego przesyłania danych. (Patrz nowinka: Kwanty, szyfry, komutery i nagrody ). Z najsłynniejszego algorytmu tego typu, sędziwego RSA opracowanego w 1977 r. w MIT przez panów Rivesta, Shamira i Adlemana, korzystał, najczęściej nieświadomie, prawie każdy, kto posługuje się internetową przeglądarką, kartą kredytową, bankomatami czy telefonami komórkowymi. (Patrz też strona www: http://www.rsasecurity.com).
Rekordy speców z CWI - którzy mają na swym koncie również inne sukcesy, np. złamanie dwóch testowych stukilkudziesięciocyfrowych (512-bitowych) kluczy algorytmu RSA - wydają się świadczyć o słuszności wiary w odporność RSA, choć przypominają też o konieczności odpowiednio częstych zmian kluczy. Zalecane przez laboratoria RSA klucze 1024-bitowe są wciąż poza zasięgiem możliwości wszelkich hakerów, choćby i wyposażonych w odpowiednią wiedzę z teorii liczb i dostęp do superkomputera. Poza tym złamanie jednego klucza po wielomiesięcznych, wieloosobowych i obficie sponsorowanych wysiłkach nie oznacza jeszcze możliwości rozwinięcia cichego, rentownego i nielegalnego interesu. Margines bezpieczeństwa jest solidny, w każdym razie do czasu, gdy ktoś znajdzie nowy algorytm rozkładu na czynniki pierwsze...
|
