Właściwa strona - http://www.wiw.pl/nowinki/matematyka/200007/20000726-001.asp Wiw Matematyka i przyroda: Astronomia Biologia Fizyka Matematyka Humanistyka: Historia Kultura antyczna Literatura Plastyka Czytaj: Biblioteka Delta Inne: Słowniki Szkoły wyższe Wszechświat w obrazkach Nowinki Nowości Jesteś tutaj: Wirtualny Wszechświat Matematyka Nowinki matematyczne Jesteś tutaj nowinka: Kwanty, szyfry, algorytmy i nagrody autor: Paweł Strzelecki z dnia: 26-07-2000 Najświeższe nowinki Najlepsza matematyka w Internecie Inernetowa witryna ScientificAmerican.com, związana ze słynnym czasopismem "Scientific American" którego polska edycja ukazuje się jako "Świat Nauki", ogłosiła listę najlepszych naukowych witryn w anglojęzycznej Sieci - po pięć w każdej z dziesięciu dziedzin. Kostyczny, dogmatyczny pedant 18 marca 2001 r. minęło 130 lat od śmierci angielskiego matematyka o nazwisku znanym niemal każdemu dziecku, które w szkole liznęło odrobinę logiki zdań. Historycy matematyki podejrzewają go o rozpowszechnianie złośliwej anegdoty o Bogu, Diderocie i Eulerze. Wszystkie nowinki Powrót Matematyka - strona główna Nowinki Wirtualnego Wszechświata Szukacz Przeszukaj za pomocą Szukacza: witrynę Matematyka cały Wirtualny Wszechświat Przeszukaj inne witryny wydawnictwa Prószyński i S-ka Jak zadawać pytania? Zespół Osoby, które przygotowały dla Ciebie witrynę Nowinki 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 - strona główna | Astronomia i kosmologia | Biologia | Fizyka | Matematyka | Historia | Kultura antyczna | Literatura | Szkoła-Plastyka | Nowinki | Nowości | Szkoły wyższe | Biblioteka | Wszechświat w obrazkach | Słowniki | Copyright Prószyński i S-ka SA 2000. All rights reserved. Wszystkie prawa zastrzeżone.