Rekordowa faktoryzacja

[KopalniaWiedzy.pl 357]

Nike Dattani z uniwersytetów w Kioto i Oksfordzie oraz Nathaniel Bryans z Microsoftu i Uniwersity of Calgary ustanowili rekord kwantowej faktoryzacji. Obaj uczeni rozłożyli na czynniki pierwsze liczbę 58 153. Wcześniejszy rekord faktoryzacji ustanowiono w 2012 roku, kiedy to udało się rozłożyć liczbę 143.

Rozkładu liczby 58 153 dokonano za pomocą tej samej techniki, to rozkładu 143. Dattani i Bryans wykorzystali pracujący w temperaturze pokojowej atomowy rezonans magnetyczny. Faktoryzacji dokonano za pomocą algorytmu wykorzystującego 4 kubity (bity kwantowe). Uczeni wykazali też teoretycznie, że ich algorytm pozwoli na wykorzystanie zaledwie 6 kubitów do faktoryzacji liczby 291 311.

Obliczenia kwantowe były przez dziesięciolecia zaledwie ciekawostką, która zajmowali się fizycy teoretyczni. Sytuacja uległa gwałtownej zmianie w 1994 roku gdy Peter Shor opracował algorytm faktoryzacji, czyli rozkładu wielkich liczb na czynniki pierwsze. To pokazało, że komputery kwantowe mogą błyskawicznie dokonać faktoryzacji. Błyskawiczny rozkład wielkich liczb oznaczałby złamanie wielu nowoczesnych szyfrów. Prace nad obliczeniami kwantowymi ruszyły więc z kopyta, gdyż z jednej strony rozpoczął się wyścig o to, kto pierwszy złamie szyfry przeciwnika, a z drugiej – istniała obawa o bezpieczeństwo własnych szyfrów. Prace to idą jednak dość powoli. Największą liczbą sfaktoryzowaną za pomocą algorytmu Shora jest 21. Dattani i Bryans wykorzystali inny algorytm, który został opracowany w 2001 roku i jest ciągle udoskonalany. To za jego pomocą dokonano faktoryzacji liczby 143 (11 x 13), a obecnie 56 153 (241 x 233). Mimo tak olbrzymiego sukcesu kwantowe urządzenia liczące są wciąż daleko w tyle za klasycznymi komputerami. Najdłuższym szyfrem RSA sfaktoryzowanym za pomocą klasycznego komputera jest RSA-768, który składa się z 768 bitów. Faktoryzacja zajęła dwa lata - mówi Dattani. Szyfry RSA to olbrzymie liczby, które składają się z iloczynu dwóch wielkich liczb pierwszych. Są szczególnie trudne do złamania, dlatego powszechnie wykorzystują je rządy czy banki. Liczba 56 153 to liczba 16-bitowa. Jednak to dwukrotnie dłuższa liczba niż te faktoryzowane przez algorytm Shora. Co więcej do faktoryzacji potrzebowaliśmy zaledwie 4 kubitów, podczas gdy sfaktoryzowanie 21 za pomocą akgorytmu Shora wymagało 10 kubitów - zaznacza Dattani.

« powrót do artykułu