Test pierwszości Fermata: Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
poprawa założeń |
|||
Linia 1:
'''Test pierwszości Fermata'''
== 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>
▲:<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>
== Wady ==
Istnieją liczby złożone ([[liczby Carmichaela]]), dla których równość z twierdzenia zachodzi dla wszystkich <math>a,</math>
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
: <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
== Zobacz też ==
* [[
* [[
[[Kategoria:Testy pierwszości|Fermata]]
|