Wikipedia

Test pierwszości Fermata: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja przejrzana][wersja przejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
poprawa założeń
Linia 1:
'''Test pierwszości Fermata''' to– [[algorytm probabilistyczny|probabilistyczny]] test umożliwiający sprawdzenie, czy dana liczba jest [[liczbyLiczba złożonezłożona|złożona]], czy ''prawdopodobnie'' [[liczbyLiczba pierwszepierwsza|pierwsza]]. Jest jednym z najprostszych testów pierwszości i pomimo swoich wad jest wykorzystywany w algorytmach szyfrowania [[Pretty Good Privacy|PGP]].
 
== Zasada działania ==
[[Małe twierdzenie Fermata]] mówi, że jeśli <math>p</math> jest liczbą pierwszą i <math>a</math> nie dzieli się przez <math>p,</math>, to
: <math>a^{p-1} \equiv 1 \ (\operatorname{mod}\, p).</math>.▼
 
▲:<math>a^{p-1} \equiv 1 \ (\operatorname{mod}\, p)</math>.
 
Aby stwierdzić, czy <math>p</math> jest pierwsza, można wybrać kilka losowych wartości <math>a</math> względnie pierwszych z <math>p</math> i sprawdzić, czy ta równość jest dla nich spełniona. Jeśli dla którejkolwiek z nich nie jest, to na pewno <math>p</math> jest liczbą złożoną. Jeśli wszystkie ją spełniają, <math>p</math> jest prawdopodobnie liczbą pierwszą albo [[liczby pseudopierwsze|pseudopierwszą]]
 
Używając [[algorytm szybkiego potęgowania|algorytmu szybkiego potęgowania]], możemy wykonać to w czasie <math>\Omicron (k \cdot \log^3 n),</math>, gdzie <math>k</math> jest liczbą losowo wybranych <math>a.</math>.
 
== Wady ==
Istnieją liczby złożone ([[liczby Carmichaela]]), dla których równość z twierdzenia zachodzi dla wszystkich <math>a,</math>, takich że [[Największy wspólny dzielnik|<math>\operatorname{NWD}(a,n) = 1</math>]]. Tym samym test ma bardzo duże prawdopodobieństwo uznania takich liczb za pierwsze.
 
W ogólności, jeśli ''n'' nie jest liczbą Carmichaela, wtedy co najmniej połowa <math>a\in(\mathbb{Z}/n\mathbb{Z})^*</math> nie spełnia równości. Aby to udowodnić, należy założyć, że równość nie jest spełniona dla ''a'' i jest spełniona dla ''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''s''</sub>. Wtedy▼
 
▲W ogólności, jeśli ''n'' nie jest liczbą Carmichaela, wtedy co najmniej połowa <math>a\in(\mathbb{Z}/n\mathbb{Z})^*</math> nie spełnia równości. Aby to udowodnić, należy założyć, że równość nie jest spełniona dla ''a'' i jest spełniona dla ''a''<sub>1</submath>a_1, ''a''<sub>2</sub>a_2, ...\dots, ''a''<sub>''s''a_s.</submath>. Wtedy
: <math>(a \cdot a_i)^{n-1} \equiv a^{n-1} \cdot a_i^{n-1} \equiv a^{n-1} \not\equiv 1 \ (\operatorname{mod}\, n),</math>,
 
zatem równość nie jest też spełniona dla wszystkich ''<math>a'' •\cdot ''a''<sub>ia_i</submath> dla ''<math>i'' = 1, 2, ...\dots, ''s''.</math>
 
== Zobacz też ==
* [[Testtest pierwszości]]
* [[Testtest Millera-Rabina]]
 
[[Kategoria:Testy pierwszości|Fermata]]
Źródło: „https://pl.wikipedia.org/wiki/Test_pierwszości_Fermata”