Rozdział Elementy teorii złożoności



Pobieranie 1,74 Mb.
Strona14/19
Data23.02.2018
Rozmiar1,74 Mb.
1   ...   11   12   13   14   15   16   17   18   19

Definicja 2.10


Liczba nN jest pseudopierwsza jeżeli w<n (w, n) = 1  wn–1  1 mod n.
Test Fermata sprawdza, czy dana liczba jest pseudopierwsza. Niestety nie każda liczba pseudopierwsza jest pierwsza. Okazuje się, że istnieją liczby złożone dla których wszystkie liczby od nich mniejsze i z nią względnie pierwsze są jej świadkami pierwszości.
Definicja 2.11

Liczbę, która jest pseudopierwsza ale nie jest pierwsza nazywamy liczbą Carmichaela.


Najmniejszą liczbą Carmichaela jest 561. Nie wiadomo ile jest liczb Carmichaela ale dotąd znaleziono ich bardzo niewiele.
Pomimo istnienia liczb Carmichaela test Fermata stosowany jest w praktyce (np. w pakiecie PGP). Lepszym rozwiązaniem jest zastosowanie testu Millera – Rabina, który wolny jest od powyższej wady.
          1. Test Millera – Rabina

Badamy, czy liczba nN jest pierwsza.


Niech n – 1 = 2tm, gdzie m jest liczbą nieparzystą. Powtarzamy k razy:


  1. losujemy liczbę 1 < a < n,

  2. jeżeli (a, n)  1, to test daje odpowiedź, że n jest złożona i kończy działanie,

  3. obliczamy w = am mod n,

  4. obliczamy w2, w4, w8, ..., (mod n) przerywając, gdy  1 mod n lub i = t,

  5. jeśli  1 mod n lub dla i > 0  – 1 mod n, to test daje odpowiedź, że n jest złożona i kończy działanie.





1   ...   11   12   13   14   15   16   17   18   19


©operacji.org 2017
wyślij wiadomość

    Strona główna