Strona A wybiera dwie duże liczby pierwsze p i q, albo obie przystające do 1 albo obie przystające do 3 modulo 4 (do znalezienia dużych liczb pierwszych można użyć np. testu Millera-Rabina). Strona A przekazuje stronie B wynik mnożenia tych dwóch liczb: N = pq, zachowując p i q w tajemnicy. Łatwo obliczyć, że N zawsze będzie przystawało do 1 modulo 4. Wybrane liczby muszą być na tyle duże, żeby faktoryzacja N była niewykonalna dla strony B w czasie przeznaczonym na wykonanie następnego kroku. Strona B wybiera wynik: „1” albo „3”, określając do jakiej liczby przystają p i q modulo 4. Strona A ogłasza wartości p i q, i czy B odgadła prawidłowo. Strona B może łatwo sprawdzić, czy to są prawidłowe liczby sprawdzając czy są pierwsze i mnożąc je przez siebie (jeśli są pierwsze, to N nie ma innych rozkładów na czynniki).
Zobacz też Loteria Paradoks hazardzisty kość do gry
Przypisy
Linki zewnętrzne
Kategoria:Gry losowe Kategoria:Rachunek prawdopodobieństwa Kategoria:Monety Kategoria:Gry towarzyskie