Informacje
  Wiw.pl   Na bieżąco:  Informacje   Co nowego   Matematyka i przyroda:  Astronomia   Biologia   Fizyka   Matematyka   Modelowanie rzeczywistości   Humanistyka:  Filozofia   Historia   Kultura antyczna   Literatura   Sztuka   Czytaj:  Biblioteka   Delta   Wielcy i więksi   Przydatne:  Słowniki   Co i gdzie studiować   Wszechświat w obrazkach    
  Jesteś tutaj:  Wirtualny Wszechświat > Informacje > Nowinki 2000-2002 > Matematyka > Nowinka z dn. 22-11-2000  
 Jesteś tutaj
nowinka:
Nowy rekord
autor:
Paweł Strzelecki
z dnia:
22-11-2000





Nowy rekord
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...

Paweł Strzelecki
[  góra strony  ]

Wiw.pl  |  Na bieżąco  |  Informacje  |  Co nowego  |  Matematyka i przyroda  |  Astronomia  |  Biologia  |  Fizyka  |  Matematyka  |  Modelowanie rzeczywistości  |  Humanistyka  |  Filozofia  |  Historia  |  Kultura antyczna  |  Literatura  |  Sztuka  |  Czytaj  |  Biblioteka  |  Delta  |  Wielcy i więksi  |  Przydatne  |  Słowniki  |  Co i gdzie studiować  |  Wszechświat w obrazkach