Pierwszość liczby naturalnej – Chiński Test Pierwszości


Tematy pokrewne   Podrozdziały
Przedziały liczbowe i liczby
Liczby parzyste i nieparzyste
Liczby podzielne lub niepodzielne przez zadane podzielniki
Ciągi arytmetyczne
NWD – algorytm Euklidesa
Liczby względnie pierwsze
Najmniejsza wspólna wielokrotność
Odwrotność modulo – rozszerzony algorytm Euklidesa
Liczby pierwsze – generacja przez sprawdzanie podzielności
Liczby pierwsze – generacja sitem Eratostenesa
Liczby pierwsze – generacja sitem liniowym
Liczby pierwsze – generacja sitem Atkina-Bernsteina
Czynniki pierwsze – metoda próbnych dzieleń
Czynniki pierwsze – metoda Fermata
Pierwszość liczby naturalnej – algorytmy naiwne
Pierwszość liczby naturalnej – Chiński Test Pierwszości
Pierwszość liczby naturalnej – Małe Twierdzenie Fermata
Pierwszość liczby naturalnej – test Millera-Rabina
Liniowe generatory liczb pseudolosowych
Generator pseudolosowy Park-Miller
Generator pseudolosowy Mersenne Twister
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Liczby Fibonacciego
System liczbowy Fibonacciego
Całkowity pierwiastek kwadratowy
  Wyznaczanie dużych potęg liczby 2 modulo n
Chiński test pierwszości

 

Problem

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 ≈  d  =  10100  =  1089  [s]  3,33 × 1088 [s]  ≈ 1081 [lat]
1011 3 × 1011 3

 

Widzimy wyraźnie, iż czas obliczeń jest niewyobrażalnie duży – cały nasz Wszechświat istnieje "zaledwie" 1,3 × 1010 lat. Musimy zatem sięgnąć do innych metod testowania pierwszości.

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 2p - 2 jest podzielne przez p. Sprawdźmy dla kilku początkowych liczb pierwszych:

 

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ą.

 

Wyznaczanie dużych potęg liczby 2 modulo n

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 0 do 264 - 1. Jednakże nas nie interesuje konkretna wartość potęgi liczby 2, a jedynie reszta z dzielenia tej potęgi przez p. Możemy zatem wykorzystać zasady arytmetyki modularnej (ang. modular arithmetic), w której wynik każdej operacji jest resztą z dzielenia przez moduł.

Na przykład dla modułu n = 5 mamy:

 

3 + 4 mod 5 = 7 mod 5 = 2
4 × 3 mod 5 = 12 mod 5 = 2
24 mod 5 = 16 mod 5 = 1

 

Z przytoczonych przykładów wynika, iż wynik operacji arytmetycznej modulo n wpada w przedział od 0, do n-1. Zatem będzie tego samego rzędu, co n. Dzięki tej własności możemy obliczać reszty potęg dowolnej wielkości – obliczanie potęgi rozbijamy na operacje mnożenia modulo n. W efekcie potęgowanie sprowadza się do wymnażania odpowiednich reszt. Idea opiera się na prostej zależności:

 

ax + y mod n = (ax mod n) × (ay mod n) mod n

 

Oznacza to, iż zamiast wyliczać resztę potęgi ax+y mod n, możemy wyznaczyć reszty modulo n potęg ax oraz ay i wymnożyć je modulo n. Dla potęg ax i ay można dokonać rekurencyjnie takiego samego rozkładu.

 

Przykład:

Obliczyć 2367 mod 13.

Rozbijamy liczbę 387 na sumę potęg 2:

 

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 potęg 2:

 

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 modulo 13:

 

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 liczby 2, które odpowiadają wagom bitów ustawionych na 1 w reprezentacji dwójkowej wykładnika potęgowego:

 

387(10) = 110000011(2)

 

Spostrzeżenie to wykorzystuje poniższy algorytm szybkiego wyznaczania reszty modulo n potęgi liczby 2. Bada on stan bitów wykładnika i na tej podstawie tworzy wynik. Mnożenie modulo n można rozbić na dodawanie modulo n wielokrotności mnożnej. Dzięki temu wynik częściowy nie wykroczy wiele poza moduł i operację będzie można przeprowadzać dla dużych liczb.

 

Algorytm obliczania a × b mod n

Wejście
a, b    mnożone liczby, a,b N
n  – moduł operacji mnożenia, n N
Wyjście:

w = a × b mod n

Elementy pomocnicze:
m  –  maska bitowa służąca do testowania ustawionych w b bitów
Lista kroków:
K01: w ← 0 ; wynik mnożenia
K02: m ← 1 ; maska bitowa
K03: Dopóki m ≠ 0, wykonuj K04...K06  
K04:     Jeśli b and m ≠ 0,
    to ww + a mod n
; sprawdzamy ustawione bity w mnożniku
K05:     a  ← (a shl 1) mod n ; przesuwamy mnożną o 1 bit w lewo
K06:     mm shl 1 ; przesuwamy bit w masce
K07: Pisz w  
K08: Zakończ  

 

Algorytm obliczania ae mod n

Wejście
a  –  podstawa potęgi, a N
e  –  wykładnik dla potęgi a, e N
n    moduł, n N, n > 1
Wyjście:

w = 2e mod n

Elementy pomocnicze:
m  –  maska bitowa służąca do testowania ustawionych w e bitów
p  – reszta z kolejnych potęg a modulo n, p N
Lista kroków:
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, wykonuj K05...K07 ; obliczamy 2e mod n
K05:     Jeśli e and m ≠0,
    to ww × p mod n
; sprawdzamy, czy e posiada ustawiony bit na pozycji z m
; jeśli tak, to wynik wymnażamy przez potęgę
K06:     pp × p mod n ; wyliczamy następną potęgę
K07:     mm shl 1 ; przesuwamy w lewo bit maski
K08: Pisz w  
K09: Zakończ  

 

Program

Ważne:

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.

 

Lazarus
// Reszty potęg 2 modulo n
// Data   : 4.04.2008
// (C)2012 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.
Code::Blocks
// Reszty potęg 2 modulo n
// Data   : 4.04.2008
// (C)2012 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;
}
Free Basic
' Reszty potęg 2 modulo n
' Data   : 4.04.2008
' (C)2012 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
Wynik
283125637241 551842729812
4916904288980

 

Chiński test pierwszości

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ą.

 

Program

Ważne:

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.

 

Lazarus
// Chiński test pierwszości
// Data   : 4.04.2008
// (C)2012 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.
Code::Blocks
// Chiński test pierwszości
// Data   : 4.04.2008
// (C)2012 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;
}
Free Basic
' Chiński test pierwszości
' Data   : 4.04.2008
' (C)2012 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
Wynik
9223372036854775783
TAK

9223372036854775787
NIE

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.