Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
Sprawdzić, czy liczba naturalna p jest pierwsza.
Zainteresowanie testami pierwszości (ang. primality testing) wzrosło w ostatnich latach z uwagi na powszechne wprowadzenie do użytku różnych publicznych systemów kryptograficznych. Systemy te wymagają szybkich algorytmów weryfikacji, czy dana liczba naturalna jest liczbą pierwszą – liczby pierwsze są potrzebne do tworzenia tzw. kluczy szyfrujących. Z uwagi na charakter procesu szyfrowania informacji testowane liczby są bardzo duże. Zatem zwykłe metody testowania pierwszości, np. przez próbne dzielenia liczby przez czynniki, nie zdają egzaminu z powodu swojej powolności. Dla przykładu rozważmy test pierwszości liczby 200 cyfrowej. Możemy ją przybliżyć następująco:
p ≈ 10200
Aby sprawdzić, czy liczba p jest pierwsza, dzielimy ją próbnie przez liczby z przedziału <2, √p>. Liczb tych jest:
d ≈ 10100
Jeśli wyeliminujemy z tego przedziału liczby podzielne przez 2 lub przez 3, to pozostanie ich 1/3 w stosunku do pierwotnej liczby, zatem:
d' ≈ 10100 / 3
Tyle musimy wykonać dzieleń próbnych w algorytmie naiwnym. Wyobraźmy sobie, iż dysponujemy superkomputerem, który w ciągu 1 sekundy jest w stanie wykonać sto miliardów (1011) takich testów podzielności (zwykłe Pentium IV tego nie potrafi, być może jakiś super Cray przyszłości lub komputer kwantowy). Zatem wykonanie operacji zajmie:
t ≈ 10100 / 1011 = 10100 / (3 × 1011) = 1089 / 3 [s] ≈ 3,33 × 1088 [s] ≈ 1081 [lat]
Widzimy wyraźnie, iż czas obliczeń jest niewyobrażalnie duży – cały
nasz Wszechświat istnieje "zaledwie"
Ideą takich metod jest wyszukiwanie własności, które spełniają tylko liczby
pierwsze lub własności spełnianych jedynie przez liczby złożone. Następnie
sprawdzamy, czy badana liczba spełnia określoną własność i na tej podstawie
wnioskujemy o jej pierwszości. Pierwsza wskazówka pojawiła się około 500 lat
p.n.e. w Chinach, gdzie odkryto fakt, iż jeśli liczba p jest
pierwsza, to wyrażenie
p = 2, 2p - 2 = 22 - 2 = 4 - 2 = 2 = 1 × p p = 3, 2p - 2 = 23 - 2 = 8 - 2 = 6 = 2 × p p = 5, 2p - 2 = 25 - 2 = 32 - 2 = 30 = 6 × p p = 7, 2p - 2 = 27 - 2 = 128 - 2 = 126 = 18 × p p = 11, 2p - 2 = 211 - 2 = 2048 - 2 = 2046 = 186 × p …
Powyższą własność można zapisać w postaci twierdzenia:
Niech p będzie liczbą naturalną większą od 1. Jeśli liczba 2p nie jest przystająca do liczby 2 modulo p, to p jest liczbą złożoną.
Innymi słowy, jeśli 2p mod p ≠ 2, to p jest złożone.
Jeśli twierdzenie jest spełnione, to mamy pewność, iż p jest liczbą złożoną. Niestety, jeśli jednak twierdzenie nie jest spełnione, czyli 2p mod p = 2, to liczba p jest albo pierwszą (wszystkie liczby pierwsze p dzielą 2p - 2), albo pseudopierwszą przy podstawie 2 (ang. base 2 pseudoprime), czyli złożoną dzielącą 2p - 2. Na szczęście liczby pseudopierwsze przy podstawie 2 występują bardzo rzadko. Jeśli zatem liczba p nie spełnia testu, to istnieje tylko prawdopodobieństwo około 0,002%, iż mimo wszystko p jest liczbą złożoną.
Podstawowym problemem chińskiego testu pierwszości jest obliczanie dużych
potęg liczby 2. Na pierwszy rzut oka możemy odnieść wrażenie, iż zadanie nie
jest wykonalne w zakresie liczb oferowanym przez podstawowe typy danych. Na
przykład liczby 64-bitowe posiadają jedynie zakres od
Wynik operacji arytmetycznej
ax+y mod n = (ax mod n) × (ay mod n) mod n
Oznacza to, iż zamiast wyliczać resztę potęgi
Przykład:
Obliczyć 2387 mod 13.
Rozbijamy liczbę 387 na sumę
387 = 256 + 128 + 2 + 1 2387 mod 13 = (2256 mod 13) × (2128 mod 13) × (22 mod 13) × (21 mod 13) mod 13
Teraz obliczamy reszty
21 mod 13 = 2 mod 13 = 2 22 mod 13 = (21 mod 13) × (21 mod 13) mod 13 = (2 × 2) mod 13 = 4 mod 13 = 4 24 mod 13 = (22 mod 13) × (22 mod 13) mod 13 = (4 × 4) mod 13 = 16 mod 13 = 3 28 mod 13 = (24 mod 13) × (24 mod 13) mod 13 = (3 × 3) mod 13 = 9 mod 13 = 9 216 mod 13 = (28 mod 13) × (28 mod 13) mod 13 = (9 × 9) mod 13 = 81 mod 13 = 3 232 mod 13 = (216 mod 13) × (216 mod 13) mod 13 = (3 × 3) mod 13 = 9 mod 13 = 9 264 mod 13 = (232 mod 13) × (232 mod 13) mod 13 = (9 × 9) mod 13 = 81 mod 13 = 3 2128 mod 13 = (264 mod 13) × (264 mod 13) mod 13 = (3 × 3) mod 13 = 9 mod 13 = 9 2256 mod 13 = (2128 mod 13) × (2128 mod 13) mod 13 = (9 × 9) mod 13 = 81 mod 13 = 3
Mając reszty potęg (zaznaczone na czerwono),
wymnażamy je
2387 mod 13 = (2256 mod 13) × (2128 mod 13) × (22 mod 13) × (21 mod 13) mod 13
2387 mod 13 = (3 × 9 × 4 × 2) mod 13 = 216 mod 13 = 8
Zwróć uwagę, iż w obliczeniu końcowym biorą udział potęgi
387(10) = 110000011(2)
Spostrzeżenie to wykorzystuje poniższy algorytm szybkiego wyznaczania reszty
K01: w ← 0 ; wynik mnożenia K02: m ← 1 ; maska bitowa K03: Dopóki m ≠ 0: wykonuj kroki K04…K06 K04: Jeśli b and m ≠ 0, ; sprawdzamy ustawione bity w mnożniku to w ← w + a mod n K05: a ← ( a shl 1) mod n ; przesuwamy mnożną o 1 bit w lewo K06: m ← m shl 1 ; przesuwamy bit w masce K07: Pisz w K08: Zakończ
K01: p ← a ; wartość początkowa potęgi a1 K02: w ← 1 ; wynik K03: m ← 1 ; maska bitowa – ustawiony bit b0 K04: Dopóki m ≠ 0: ; obliczamy 2e mod n wykonuj kroki K05…K07 K05: Jeśli e and m ≠ 0, ; sprawdzamy, czy e posiada ustawiony bit na pozycji z m to w ← w × p mod n ; jeśli tak, to wynik wymnażamy przez potęgę K06: p ← p × p mod n ; wyliczamy następną potęgę K07: m ← m shl 1 ; przesuwamy w lewo bit maski K08: Pisz w K09: Zakończ
Uwaga: Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program odczytuje z pierwszego wiersza dwie liczby: e – wykładnik potęgi liczby 2 oraz n – moduł. W drugim wierszu wypisuje wynik 2e mod n. |
Pascal// Reszty potęg 2 modulo n // Data : 4.04.2008 // (C)2020 mgr Jerzy Wałaszek //---------------------------- program prg; // Funkcja mnoży a i b mod n //-------------------------- function MnozModulo (a, b, n : qword) : qword; var m, w : qword; begin w := 0; m := 1; while m <> 0 do begin if b and m <> 0 then w := (w + a) mod n; a := (a shl 1) mod n; m := m shl 1; end; MnozModulo := w; end; var e, n, m, p, w : qword; begin readln(e, n); p := 2; w := 1; m := 1; while m <> 0 do begin if e and m <> 0 then w := MnozModulo (w, p, n); p := MnozModulo (p, p, n); m := m shl 1; end; writeln(w); end. |
C++// Reszty potęg 2 modulo n // Data : 4.04.2008 // (C)2020 mgr Jerzy Wałaszek //---------------------------- #include <iostream> using namespace std; typedef unsigned long long ulong; // Funkcja mnoży a i b mod n //-------------------------- ulong MnozModulo (ulong a, ulong b, ulong n) { ulong m, w; w = 0; m = 1; while(m) { if(b & m) w = (w + a) % n; a = (a << 1) % n; m <<= 1; } return w; } int main() { ulong e, n, m, p, w; cin >> e >> n; p = 2; w = m = 1; while(m) { if(e & m) w = MnozModulo (w, p, n); p = MnozModulo (p, p, n); m <<= 1; } cout << w << endl; return 0; } |
Basic' Reszty potęg 2 modulo n ' Data : 4.04.2008 ' (C)2020 mgr Jerzy Wałaszek '---------------------------- ' Funkcja mnoży a i b mod n '-------------------------- Function MnozModulo(Byval a As Ulongint,_ Byval b As Ulongint,_ Byval n As Ulongint)_ As Ulongint Dim As Ulongint m, w w = 0: m = 1 While m if(b And m) <> 0 Then w = (w + a) Mod n a = (a Shl 1) Mod n m = m Shl 1 Wend MnozModulo = w End Function Dim As Ulongint e, n, m, p, w Input e, n p = 2: w = 1: m = 1 While m if(e And m) <> 0 Then w = MnozModulo (w, p, n) p = MnozModulo (p, p, n) m = m Shl 1 Wend Print w End |
Python
(dodatek)# Reszty potęg 2 modulo n # Data : 14.02.2024 # (C)2024 mgr Jerzy Wałaszek # ---------------------------- # sztuczna granica dla int # ---------------------------- G = 2 ** 64 # Funkcja mnoży a i b mod n # ---------------------------- def mnoz_modulo(a, b, n): w, m = 0, 1 while m < G: if b & m: w = (w + a) % n a = (a << 1) % n m <<= 1 return w # ---------------------------- arr = input().split(" ") e = int(arr[0]) n = int(arr[1]) p, w, m = 2, 1, 1 while m < G: if e & m: w = mnoz_modulo(w, p, n) p = mnoz_modulo(p, p, n) m <<= 1 print(w) |
W Pythonie nie ma ograniczenia na wielkość liczb całkowitych, powyższy program wprowadza za pomocą stałej G (granica) sztuczne ograniczenie do liczb 64 bitowych.
Wynik: |
283125637241 551842729812 502162450484 |
Po podaniu algorytmów mnożenia modulo oraz potęgowania modulo przy podstawie 2 chiński test pierwszości (ang. Chinese Primality Test) staje się bardzo prosty. Odczytujemy liczbę p. Obliczamy 2p mod p. Jeśli reszta jest różna od 2, to liczba p na pewno jest liczbą złożoną. Jeśli reszta jest równa 2, to z dużym prawdopodobieństwem p jest liczbą pierwszą.
Uwaga: Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program w pierwszym wierszu czyta liczbę p i w następnym wierszu wypisuje słowo NIE, jeśli p jest liczbą złożoną lub TAK, jeśli liczba p jest pierwsza lub pseudopierwsza przy podstawie 2. Zwróć uwagę, iż testowanie jest błyskawiczne. |
Pascal// Chiński test pierwszości // Data : 4.04.2008 // (C)2020 mgr Jerzy Wałaszek //---------------------------- program prg; // Funkcja mnoży a i b mod n //-------------------------- function MnozModulo(a, b, n : qword) : qword; var m, w : qword; begin w := 0; m := 1; while m <> 0 do begin if b and m <> 0 then w := (w + a) mod n; a := (a shl 1) mod n; m := m shl 1; end; MnozModulo := w; end; // Funkcja oblicza 2^e mod n //-------------------------- function PotegujModulo(e, n : qword) : qword; var m, p, w : qword; begin p := 2; w := 1; m := 1; while m <> 0 do begin if e and m <> 0 then w := MnozModulo(w, p, n); p := MnozModulo(p, p, n); m := m shl 1; end; PotegujModulo := w; end; var p : qword; begin readln(p); if PotegujModulo (p, p) = 2 then writeln('TAK') else writeln('NIE'); end. |
C++// Chiński test pierwszości // Data : 4.04.2008 // (C)2020 mgr Jerzy Wałaszek //---------------------------- #include <iostream> using namespace std; typedef unsigned long long ulong; // Funkcja mnoży a i b mod n //-------------------------- ulong MnozModulo(ulong a, ulong b, ulong n) { ulong m, w; w = 0; m = 1; while(m) { if(b & m) w = (w + a) % n; a = (a << 1) % n; m <<= 1; } return w; } // Funkcja oblicza 2^e mod n //-------------------------- ulong PotegujModulo (ulong e, ulong n) { ulong m, p, w; p = 2; w = m = 1; while(m) { if(e & m) w = MnozModulo (w, p, n); p = MnozModulo (p, p, n); m <<= 1; } return w; } int main() { ulong p; cin >> p; cout << (PotegujModulo (p, p) == 2 ? "TAK": "NIE") << endl; return 0; } |
Basic' Chiński test pierwszości ' Data : 4.04.2008 ' (C)2020 mgr Jerzy Wałaszek '---------------------------- ' Funkcja mnoży a i b mod n '-------------------------- Function MnozModulo(Byval a As Ulongint,_ Byval b As Ulongint,_ Byval n As Ulongint)_ As Ulongint Dim As Ulongint m, w w = 0: m = 1 While m If b And m Then w = (w + a) Mod n a = (a Shl 1) Mod n m = m Shl 1 Wend MnozModulo = w End Function ' Funkcja oblicza 2^e mod n '-------------------------- Function PotegujModulo (Byval e As Ulongint, Byval n As Ulongint) As Ulongint Dim As Ulongint m, p, w p = 2: w = 1: m = 1 While m If e And m Then w = MnozModulo (w, p, n) p = MnozModulo (p, p, n) m = m Shl 1 Wend PotegujModulo = w End Function Dim p As Ulongint Input p If PotegujModulo (p, p) = 2 Then Print "TAK": Else Print "NIE" End |
Python
(dodatek)# Chiński test pierwszości # Data : 14.02.2024 # (C)2024 mgr Jerzy Wałaszek # ---------------------------- G = 2 ** 64 # sztuczna granica int # Funkcja mnoży a i b mod n # -------------------------- def mnoz_modulo(a, b, n): w, m = 0, 1 while m < G: if b & m: w = (w + a) % n a = (a << 1) % n m <<= 1 return w # Funkcja oblicza 2**e mod n # --------------------------- def poteguj_modulo(e, n): p, w, m = 2, 1, 1 while m < G: if e & m: w = mnoz_modulo(w, p, n) p = mnoz_modulo(p, p, n) m <<= 1 return w # -------------------------- p = int(input()) if poteguj_modulo(p, p) == 2: print("TAK") else: print("NIE") |
Wynik: |
9223372036854775783 TAK 9223372036854775787 NIE |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.