Matematyka dyskretna 2/Test 7: Zastosowanie teorii liczb w kryptografii

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Dla małych wartości użytych liczb pierwszych łatwo można złamać RSA. Jeśli jest kluczem publicznym RSA to kluczem dekodującym jest:

żaden z pozostałych


Załóżmy, że jest naszym kluczem dekodującym w kryptosystemie RSA. Otrzymaliśmy jednostkę szyfrogramu o wartości . Wartość zdekodowanej jednostki to:


Niech dla pewnych liczb pierwszych oraz niech dla pewnego . Wtedy:

znany jest algorytm wielomianowy, który mając na wejściu i liczy

znany jest algorytm wielomianowy, który mając na wejściu i liczy i

znany jest algorytm wielomianowy, który mając na wejściu i wylicza takie, że

znany jest algorytm wielomianowy, który mając na wejściu i liczy spełniające


Jeśli liczba przeszła testów Fermata, to:

jest złożona z prawdopodobieństwem

jest pierwsza z prawdopodobieństwem

jest liczbą Carmichaela z prawdopodobieństwem

żadna z pozostałych


Liczba Carmichaela:

przechodzi test Fermata dla dowolnie wylosowanej podstawy

jest iloczynem przynajmniej trzech liczb pierwszych

mogą być parzyste

mogą być podzielne przez


Niech będzie liczbą nieparzystą oraz , gdzie . Jeśli jest silnie pseudopierwsza przy podstawie to:

istnieje takie, że

jest pseudopierwsza przy podstawie

jeśli dla pewnego to


Jeśli liczba przeszła testów Millera-Rabina to:

jest złożona z prawdopodobieństwem co najwyżej

jest pierwsza z prawdopodobieństwem co najwyżej

jest pierwsza, o ile prawdziwa jest Uogólniona Hipoteza Riemanna

żadna z pozostałych