Niekiedy bywają sytuacje, w których musimy dokonać pewnego wyboru (np. gdzie spędzić wieczór, na jaki seans wybrać się do kina ze swoją drugą połową, kto ma zacząć partię szachów). Gdy nie możemy się spotkać i wyboru tego dokonujemy przez Internet, chcemy żeby był on sprawiedliwy oraz by został dokonany w sposób losowy. Możemy rzucić monetą i wynik tego rzutu przesłać drugiej osobie, ale łatwo w ten sposób kogoś oszukać. My chcemy, by oszustwo w naszym doświadczeniu nie było możliwe! Na tapetę weźmy sytuację, w której dwie osoby mają dwa różne typy np. spędzenia czasu wolnego w piątkowy wieczór. Spór chcemy rozwiązać możliwie jak najbardziej sprawiedliwie, zaś nie możemy się spotkać osobiście, by rzucić monetą i by każdy widział wynik tego rzutu. W takich przypadkach z pomocą przychodzi nam matematyka!
Liczby pierwsze to takie liczby naturalne, które mają dokładnie dwa dzielniki - jedynkę i samą siebie (np. 2, 3, 5, 7, 11, ...). To właśnie z ogromu własności tych liczb będziemy korzystać rozwiązując nasz problem. Zauważmy, że wszystkie liczby pierwsze z wyjątkiem 2 są nieparzyste, więc jeśli podzielimy jedną z nieparzystych liczb pierwszych przez 4, pozostanie nam reszta 1 lub 3. Dopiero w XIX wieku Peter Dirichlet wykazał, że tych liczb jest dokładnie tyle samo (pomijając drobne nieścisłości związane z pojęciem ,,tyle samo'' w nieskończoności). Mamy już więc kandydatów na ,,orła'' i ,,reszkę''. Utożsamimy resztę z dzielenia przez 4 równą 1 z wyrzuceniem ,,reszki'', a z resztą 3 - ,,orła''.
Zauważmy, że iloczyn dwóch liczb pierwszych z określonej grupy wcale nie musi do niej należeć, spójrzmy na grafikę poniżej. Wyjaśnię jeszcze zapis z pierwszej linijki - oznacza on, że reszta z dzielenia 17 przez 4 wynosi 1.
A zatem iloczyn liczb pierwszych nie daje nam wskazówki z jakiej grupy (,,reszek'' czy ,,orłów'') ona pochodzi. Własność tę wykorzystamy przy ,,rzucie monetą'' przez Internet. Zasada jest taka: rzucamy monetą - jeśli wypadnie reszka, to wybieram dwie liczby pierwsze z grupy reszek, jeśli orzeł - z grupy orłów. Wynik wymnożenia tych liczb przesyłam za pośrednictwem Internetu do drugiej osoby. Powiedzmy, że jest to liczba 697 i wyrzuciliśmy reszkę. Nasz partner po znajomości jedynie liczby ,,697'' nie jest w stanie określić z jakiej grupy były czynniki. Teraz jego zadaniem jest wybór orła lub reszki i zadeklarowanie tego wyboru drugiej osobie. Żeby sprawdzić kto wygrał, pierwsza osoba wysyła drugiej wybrane liczby. Czy jednak sposób ten jest wystarczająco dobry?
Liczby pierwsze mają tę własność, że przy odpowiednio dużych wartościach nawet bardzo szybkie komputery mają problem znaleźć odpowiedni iloczyn liczb pierwszych, który da nam żądany wynik. Póki będziemy wybierać odpowiednio duże wartości, metoda ta jest bardzo bezpieczna. Spójrzmy na tabelę, która oznajmi nam, że branie dwucyfrowych liczb wcale może nie być bezpieczne (wtedy posługując się tą tabelą od razu możemy wskazać jakie liczby braliśmy do iloczynu i odgadnąć co wyrzucił przeciwnik!).
Współczesne algorytmy szyfrowania i liczby kontrolne w numerach np. kont bankowych wykorzystują własności dużych liczb pierwszych, trudno jest wtedy złamać zabezpieczenia. Z pewnością jeszcze przeczytacie o tym na blogu!
Brak komentarzy:
Prześlij komentarz