Test Pierwszości Fermata

Wstęp

Test Fermata jest to test probabilistyczny, którego wynik może określić czy dana liczba jest złożona czy prawdopodobnie jest (pseudo)pierwsza. Innymi słowy jest to krótki test czy dana liczba ma szansę być pierwsza, ale test Fermata nie rozstrzyga czy jest.

Teoria

Mała Teoria Fermata stwierdza, że jeśli p jest pierwsze oraz a nie dzieli p to:

a^{p - 1} ≡_p 1

W celu sprawdzenia czy p jest liczbą pierwszą to wybieramy losową wartość a z przedziału [2, p - 2], a następnie sprawdzamy czy dana równość zachodzi. Test wykonywany jest dla więcej niż jednej wartości a. Jeśli pomimo

Przykłady

Przypuśćmy, że chcemy sprawdzić czy p = 123 jest liczbą pierwszą. Na początku określamy, że przedział losowanie wartości a to [2, 121]. Przeprowadźmy maksymalnie dziesięć testów, aby sprawdzić czy 123 ma szansę być liczbą pierwszą.

W czwartym teście została znaleziona taka liczba a, że test wykazał złożoność liczby p. Jednak, gdyby wartość 83 nie została wylosowana to możnaby uznać p za liczbę (pseudo)pierwszą, ale dowód na jej pierwszość należałoby przeprowadzić oddzielnie.

Implementacja

Potęgowanie Modulo

Zanim zacznie się pisać test Fermata warto posiadać algorytm do wyliczania potęgi modulo. Ze względu na bardzo wysokie potęgi zakresy podstawowych typów danych mogą okazać się za małe. W celu rozwiązania tego problemu oraz przyśpieszenia procesu obliczania potęgi można skorzystać z poniższego kodu:

1. long potegowanieModulo(long a, long x, long m) {
2.   long q = 1;
3.   long y = a;
4.   while (x > 0) {
5.     if (x % 2 == 1)
6.       q = (q * y) % m;
7.     y = (y * y) % m;
8.     x = x / 2;
9.   }
10.   return q % m;
11. }

Algorytm wykorzystuje fakt, że reszta z dzielenia a·a mod m to (a mod m)(a mod m) mod m. Dodatkowo zoptymalizowany jest proces mnożenia. Jeśli potęga jest nieparzysta to wynik jest mnożony tylko raz przez bazę, a baza jest podnoszona do kwadratu co zmniejsza potęge x dwa razy.

Test Fermata

Przykładowy kod do przeprowadzenia testów Fermata został zamieszczony poniżej. Pozwala on na dostosowanie ilości prób (zmienna prob), które mają zaprzeczyć podejrzenia o pierwszości danej liczby p.

1. bool testFermata(long p, int prob = 20) {
2.   if (p == 1)
3.     return false;
5.   for (int i = 0; i < prob; i++) {
6.     long a = rand() % (p - 1) + 1;
7.     if (potegowanieModulo(a, p - 1, p) != 1) {
8.       return false;
9.     }
10.   }
11.   return true;
12. }

Testowanie funkcji

Poniższy fragment programu wczytuje od użytkownika liczbę, a następnie sprawdza czy dana liczba jest prawdopodobnie pierwsza.

1. int main() {
2.   long a;
3.   cout << "Podaj liczbe do sprawdzenia:\n a = ";
4.   cin >> a;
5.   if (testFermata(a)) {
6.     cout << "Prawdopodobnie liczba (pseudo)pierwsza";
7.   } else {
8.     cout << "Liczba jest zlozona";
9.   }
10.   system("pause");
11.   return 0;
12. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

W powyższym algorytmie może się zdarzyć, że ta sama wartość a zostanie sprawdzona kilka razy. Napisz algorytm w taki sposób, aby do takich sytuacji nie dochodziło.

• Kod źródłowy Zadanie 1