Witam!
Mam pytanie do ludzi bardziej zaawansowanych w matematyce niż ja. Otóż piszę programik, który ma testować pierwszość danej liczby nieparzystej za pomocą testów probabilistycznych i mam pewien problem. Jak wiadomo istnieją pewne liczby zwane liczbami Carmichaela, które według źródeł jakie czytałem są pseudopierwsze przy każdej podstawie a. Liczby te przez test oparty o MTW powinny zostać uznane za pierwsze jednak jeżeli ustawie w moim programie większą liczbę losowań powiedzmy powyżej 10 to zawsze znajdzie się jakaś liczba dla której kongurencja nie jest spełniona. Wszystkie programy o podobnej funkcjonalności jakie znalazłem w Internecie zachowują się podobnie, czyli uznają liczby Carmichaela za złożone (ciekawe dlaczego). Podejrzewam, że kluczem może być niepoprawna implementacja funkcji ModPow (Modular Exponential), która operuje na dosyć dużych liczbach i być może coś źle zaokrągla. Jednak aby się upewnić korzystałem również z funkcji ModPow pochodzącej z różnych bibliotek i zawsze efekt był taki sam.
Zależy mi na tym aby te liczby nie były uznawane za złożona, ponieważ chcę wykazać wady tego algorytmu w stosunku do testu solovaya-strassena.
Co może być nie tak z moim programem i czy liczby Carmichaela aby na pewno są pseudopierwsze przy KAŻDEJ podstawie???
Test pierwszości Fermata
-
- Użytkownik
- Posty: 6607
- Rejestracja: 16 sty 2007, o 19:42
- Płeć: Mężczyzna
- Podziękował: 119 razy
- Pomógł: 1823 razy
Test pierwszości Fermata
Wynika to wprost z definicji tych liczb, a na pewno już nie z żadnej niedokładności. Zresztą nie wiem nawet jak niby operacja modulo miała by być nieprecyzyjna dla liczb całkowitych...
Ogólnie masz napisane np. tutaj:
w podpunkcie drugim założenia, jakie musi spełniać taka liczba. A to założenie z góry zakłada, że jaką liczbę 'a' nie wylosujemy, to test fermata będzie zawsze spełniony, czyli liczba będzie prawdopodobnie pierwsza.
Pozdrawiam.
Ogólnie masz napisane np. tutaj:
w podpunkcie drugim założenia, jakie musi spełniać taka liczba. A to założenie z góry zakłada, że jaką liczbę 'a' nie wylosujemy, to test fermata będzie zawsze spełniony, czyli liczba będzie prawdopodobnie pierwsza.
Pozdrawiam.
-
- Użytkownik
- Posty: 6
- Rejestracja: 19 mar 2008, o 11:58
- Płeć: Mężczyzna
- Lokalizacja: sępólno krajeńskie
- Podziękował: 1 raz
Test pierwszości Fermata
No właśnie tego chciałbym się dowiedzieć dlaczego teoria rozjeżdża mi się z praktyką. Liczba 561 jest liczbą Carmichaela a z mojej funkcji wynika że;
\(\displaystyle{ 119 ^{561-1} mod 561 = 34}\) a nie 1
gdzie 119 jest wylosowanym a z przedziału od 1 do n-1
Co w takim razie robię źle?
Może też inaczej zadam pytanie:
Czy ktoś mógłby opisać jak powinien wyglądać test Fermata krok po kroku?
Póki co robię tak że wybieram dokładność testu 9 liczbę losowań k
losuję tyle razy liczbę z przedziału 1 do n-1
sprawdzam a^p-1 % p =1
\(\displaystyle{ 119 ^{561-1} mod 561 = 34}\) a nie 1
gdzie 119 jest wylosowanym a z przedziału od 1 do n-1
Co w takim razie robię źle?
Może też inaczej zadam pytanie:
Czy ktoś mógłby opisać jak powinien wyglądać test Fermata krok po kroku?
Póki co robię tak że wybieram dokładność testu 9 liczbę losowań k
losuję tyle razy liczbę z przedziału 1 do n-1
sprawdzam a^p-1 % p =1
-
- Użytkownik
- Posty: 374
- Rejestracja: 21 cze 2007, o 11:28
- Płeć: Mężczyzna
- Lokalizacja: Łostowice
- Pomógł: 146 razy
Test pierwszości Fermata
Istotnie posłużyłeś się wariantem twierdzenia,
które nie jest zawsze spełnione dla liczb Carmichaela,
co pozwala łatwiej wyłowić liczby pseudopierwsze.
Sprawdzając warunek dla podstawowej wersji twierdzenia,
\(\displaystyle{ (a ^p - a)\ mod\ p = 0}\)
\(\displaystyle{ (119 ^{561} - 119)\ mod\ 561 = 0}\)
otrzymujemy wynik taki jak dla liczby pierwszej.
które nie jest zawsze spełnione dla liczb Carmichaela,
co pozwala łatwiej wyłowić liczby pseudopierwsze.
Sprawdzając warunek dla podstawowej wersji twierdzenia,
\(\displaystyle{ (a ^p - a)\ mod\ p = 0}\)
\(\displaystyle{ (119 ^{561} - 119)\ mod\ 561 = 0}\)
Kod: Zaznacz cały
int main() {
int BASE = 119, CARMI = 561, base = BASE, i;
for(i = 1; i < CARMI; i++) {
base *= BASE; // podnosimy do kolejnej potęgi
base %= CARMI; // ustalamy resztę z dzielenia
}
printf( "(%d^%3d - %d) mod %d = %3d
", BASE, i, BASE, CARMI, (base - BASE) % CARMI);
return 0;
}
-
- Użytkownik
- Posty: 374
- Rejestracja: 21 cze 2007, o 11:28
- Płeć: Mężczyzna
- Lokalizacja: Łostowice
- Pomógł: 146 razy
Test pierwszości Fermata
Odnośnie do problemu zachowania się liczb z testu, mam taką sugestię, test dotyczy liczb względnie pierwszych tzn takich, że liczba testowana i podstawa nie mają wspólnych podzielników.
W podanym przykładzie tak nie jest gdyż
119 = 17 * 7
561 = 17 * 11 * 3
Dlatego jako podstawę najlepiej brać liczby pierwsze.
W podanym przykładzie tak nie jest gdyż
119 = 17 * 7
561 = 17 * 11 * 3
Dlatego jako podstawę najlepiej brać liczby pierwsze.