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. 26-07-2000  
 Jesteś tutaj
nowinka:
Kwanty, szyfry, algorytmy i nagrody
autor:
Paweł Strzelecki
z dnia:
26-07-2000





Kwanty, szyfry, algorytmy i nagrody
Cóż ma wspólnego mechanika kwantowa z bezpiecznym przesyłaniem informacji i teorią liczb?

Niewiele, zgoła nic, odparłby dziesięć lat temu prawie każdy fizyk i niemal każdy matematyk. Dziś, na szczęście (i na razie...) tylko teoretycznie, sprawa wygląda inaczej.

W 1974 r. panowie Rivest, Shamir i Adleman opracowali algorytm, nazwany od ich inicjałów algorytmem RSA, który umożliwia przesyłanie zaszyfrowanej informacji z tzw. publicznym kluczem: wszyscy wiedzą, jak zaszyfrować list do mnie, bo wyjaśniłem to w płatnych ogłoszeniach w prasie, lecz odczytać zaszyfrowaną informację mogę tylko ja. Bujda na resorach! - wykrzykną czytelnicy "Tańczących sylwetek" Arthura Conan Doyle'a; kto umie zaszyfrować, umie rozszyfrować, czyż nie tak? Otóż, nie zawsze.

Algorytm RSA wykorzystuje fakt, że mnożenie jest łatwiejsze od dzielenia: łatwo pomnożyć dwie pięciocyfrowe liczby; znacznie trudniej rozłożyć liczbę dziesięciocyfrową na czynniki pierwsze, szczególnie wtedy, gdy są tylko dwa. Do tego banalnego spostrzeżenia trzeba dołożyć odrobinkę teorii liczb (niezbyt trudnej, wiedza z pierwszej połowy XIX wieku w zupełności wystarczy) i elegancki pomysł, a powstanie algorytm, w którym znajomość klucza szyfrowania nie pozwala poznać w rozsądnym czasie klucza rozszyfrowywania. Trzeba bowiem w tym celu rozłożyć dużą (kilkusetcyfrową) liczbę złożoną N na czynniki pierwsze. Jest to zadanie z pozoru mechaniczne i bzdurne. Ot, brać kolejne liczby i sprawdzać, czy dzielą N, komputer przecież to potrafi. Potrafi, jednak dla kilkusetcyfrowych N potrzebuje do tego tyle czasu, że w praktyce algorytm RSA powszechnie uznaje się za bezpieczny - i powszechnie stosuje.

Gdzie tu mechanika kwantowa? Otóż, ostatni laureat nagrody Nevanlinny, Peter Shor, podał tzw. kwantowy algorytm rozkładu liczby całkowitej na czynniki pierwsze. Algorytm Shora jest nieporównanie szybszy niż jakikolwiek klasyczny algorytm rozkładania na czynniki pierwsze - działa w czasie z grubsza proporcjonalnym do kwadratu logarytmu liczby cyfr rozkładanej na czynniki liczby. Każdy, kto miałby maszynę, na której działa algorytm Shora, mógłby stosunkowo łatwo łamać wszelkie wiadomości zaszyfrowane za pomocą RSA. A cóż to jest algorytm kwantowy? W gruncie rzeczy to zwykły algorytm, tyle że do jego praktycznej realizacji potrzebny jest kwantowy komputer. W takim razie: cóż to takiego kwantowy komputer?

To, jak na razie, czysto hipotetyczne urządzenie (bankierzy i osoby płacące w Internecie kartami kredytowymi oddychają w tym momencie z ulgą), pomysłu Paula Benioffa, Davida Deutscha i Richarda Feynmana. Chodzi o komputer, który zachowywałby się zgodnie z prawami mechaniki kwantowej i w układzie n rejestrów przechowywał w danej chwili nie jeden z  wszystkich możliwych ciągów n bitów, lecz, w pewnym sensie, wszystkie takie ciągi jednocześnie, w postaci stanu będącego ich kwantową superpozycją (jak powiedziałby fizyk) czy kombinacją liniową (jak woli mówić matematyk). Chwila, w której żądamy od takiego komputera podania wyniku obliczeń, to moment pomiaru. Stan kwantowy zmienia się w stan klasyczny. Za szybkość i nadnaturalną zdolność do magazynowania informacji trzeba zapłacić cenę: wynik obliczeń kwantowego komputera jest prawdziwy tylko z pewnym prawdopodobieństwem. Znaczy to, że np. po - hipotetycznym! - uruchomieniu algorytmu Shora kwantowy komputer czasem faktycznie poda czynniki pierwsze "rozkładanej" liczby, a czasem odległość do Księżyca w milimetrach i podniesiony do sześcianu wiek cioci Basi w sekundach. Dla kwantowych łamaczy szyfrów nie stanowi to jednak kłopotu: sprawdzić odpowiedź jest bardzo łatwo; wystarczy pomnożyć (na zwykłym komputerze!) otrzymane liczby.

Istnieją już eksperymenty fizyczne, pozwalające na konstrukcję "kwantowych rejestrów dwubitowych". Są piekielnie drogie, a od komputera, który można by z nich wybudować, znacznie sprawniejszy jest przeciętny siedmiolatek. Sceptycy twierdzą, że w ogóle wszelki postęp w dziedzinie szybkości obliczeń dokonuje się przede wszystkim dzięki inżynierom, nie zaś za sprawą pomysłowych teoretyków. Wydaje się, że huczek wokół kwantowych komputerów to w znacznej mierze typowy przejaw naukowej mody, podobnie jak szum wokół fraktali. Pożyjemy, zobaczymy. Cieszyć się mogą jedynie twórcy algorytmów. Praca czeka.



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