Test pierwszości Fermata

[br3t3s]

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???

[soku11]

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.

[br3t3s]

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

[smiechowiec]

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}\)

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;
}

otrzymujemy wynik taki jak dla liczby pierwszej.

[br3t3s]

dzięki xD

[smiechowiec]

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.