Liczby pierwsze, the prime numbers to ważne zagadnienie programowania. Oto proste metody znajdowania liczb pierwszych oraz wykluczania liczb złożonych w obliczeniach.
Wprowadzenie
Z pewnością każdy z nas miał do czynienia z sytuacją, w której należało rozstrzygnąć, czy dana liczba jest liczbą pierwszą, czy też nie. Ponieważ liczby pierwsze mają dużo zastosowań (między innymi w kryptografii) tak więc umiejętne ich znajdywanie nie powinno wprawnemu programiście przysporzyć wielu problemów. Obecnie najbardziej znane są trzy algorytmy. Pierwszy z nich zna chyba każdy. Po prostu badamy resztę z dzielenia danej liczby przez liczby, po kolei - od 2 do zaokrąglonego pierwiastka kwadratowego tej liczby. Jeżeli w którymkolwiek przypadku otrzymamy wynik 0 to badana liczba na pewno jest złożona, w przeciwnym wypadku dana liczba na pewno jest pierwsza. Specjalnie podkreśliłem słowo "na pewno", ponieważ metoda, którą zaraz zaprezentuję może na pewno powiedzieć, czy dana liczba jest złożona. Czy dana liczba jest pierwsza to metoda to może powiedzieć, ale tylko z wysokim prawdopodobieństwem - nie na 100%. Trzecią metodą jest sito Eratostenesa, która to metoda znajduje wszystkie liczby pierwsze w danym przedziale.
Sprawdzanie, czy liczba jest pseudopierwsza
W drugiej metodzie, którą mam zamiar przedstawić sprawdzamy, czy badana liczba jest pseudopierwsza przy danej podstawie (tą podstawą może być liczba naturalna od 2 wzwyż). Tak więc przejdźmy do konkretów. Liczba n jest pseudopierwsza przy podstawie a wtedy, gdy zachodzi zależność:
(a(n-1)) mod n = 1
Na przykład sprawdźmy, czy liczba 7 jest pseudopierwsza przy podstawie 2. Musimy zatem sprawdzić wartość wyrażenia:
(2(7-1)) mod 7 = (26) mod 7 = 64 mod 7 = 1
Tak więc liczba 7 jest pseudopierwsza przy podstawie z 2 - w rzeczywistości liczba 7 jest pierwsza.
Sprawdźmy teraz, czy liczba 8 jest pseudopierwsza przy podstawie z 3. Zatem liczymy:
(3(8-1)) mod 8 = (37) mod 8 = 2187 mod 8 = 3
Ponieważ wynik obliczeń nie jest liczbą 1, więc możemy powiedzieć, że liczba 8 jest na pewno złożona.
Co zrobić jednak, żeby prawdopodobieństwo, że dana liczba jest pierwsza było zbliżone do 100%. Mianowicie trzeba przeprowadzić kilka prób dla różnych podstaw i gdy w którejś z prób wynikiem nie jest liczba 1 to liczba jest na pewno złożona, w przeciwnym wypadku - im więcej prób tym większa pewność, że badana liczba jest pierwsza. Prawdopodobieństwo dla s prób, że dana liczba nie jest pierwsza (mimo, iż wszystkie wyniki to 1) nie przekracza 2(-s). Można to oczywiście udowodnić. Dla przykładu podam, że przy podstawie 2 jest tylko 22 liczb mniejszych od 10000 dla których algorytm ten się myli (tzn. przy wyniku 1 liczba nie jest pierwsza). Początkowe z nich: 341, 561, 645, 1105. Gdy przyjmiemy za podstawę liczbę 3 to istnieje tylko 255 liczb mniejszych od 100000000 dla których algorytm się myli (są to tzw. liczby Carmichaela).
Jak podnosić liczby do tak wysokich potęg?
Na pewno każdy zadał takie pytanie, gdy chciał sprawdzić trochę większą liczbę, czy jest ona pierwsza. Okazuje się, że i tą sprawę da się rozwiązać. Proszę spojrzeć na następujący przykład potęgowanie, którego wynik jest następnie dzielony modulo:
(34)mod 5 = (3*3*3*3) mod 5 = 81 mod 5 = 1
Specjalnie rozpisałem 3^4. Okazuje się, że można pomnożyć najpierw dwie trójki (co da w wyniku 9), a następnie je podzielić modulo przez 5. Otrzymamy w ten sposób 9 mod 5 = 4. Następnie mnożymy uzyskany wynik przez trzecią trójką i otrzymujemy 12. Znowu dzielimy modulo przez 5 i mamy 12 mod 5 = 2. Teraz tylko wystarczy pomnożyć 2 przez ostatnią z trójek (otrzymujemy 6) i podzielić modulo wynik przez 5. W ten sposób otrzymujemy 1, czyli wynik taki jak w przykładzie powyżej. Zapiszę to teraz:
(34) mod 5 = ((((((3 mod 5)*3) mod 5)*3) mod 5)*3) mod 5
Proszę nie przestraszyć się nawiasów - są tylko dla czytelności. Cała idea potęgowania modularnego (tak się to fachowo nazywa) polega na kolejnym mnożeniu podstawy potęgi i dzieleniu za każdym razem wyniku modulo przez jakąś tam liczbę (w naszym przykładzie była to liczba 5).