Algorytmy i Struktury Danych - Chiński test pierwszości

SPIS TREŚCI

Podrozdziały

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\approx10^{200}\)

Aby sprawdzić, czy liczba \(p\) jest pierwsza, dzielimy ją próbnie przez liczby z przedziału \({[2;\sqrt{p}]}\). Liczb tych jest:

\(d\approx10^{100}\)

Jeśli wyeliminujemy z tego przedziału liczby podzielne przez \(2\) lub przez \(3\), to pozostanie ich \(\frac{1}{3}\) w stosunku do pierwotnej liczby, zatem:

\(d'\approx\dfrac{10^{100}}{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 (\(10^{11}\)) 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:

\[
\begin{array}{rl}
t\approx\dfrac{1}{3}\cdot\dfrac{10^{100}}{10^{11}}&=\\
\dfrac{10^{100}}{3\cdot10^{11}}&=\\
\dfrac{10^{89}}{3}[\text{s}]&\approx\\
3{,}33\cdot10^{88}[\text{s}]&\approx10^{81}[\text{lat}]
\end{array}
\]

Widzimy wyraźnie, iż czas obliczeń jest niewyobrażalnie duży – cały nasz Wszechświat istnieje "zaledwie" \({1{,}3\cdot10^{10}}\) 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 \({2^p–2}\) jest podzielne przez \(p\). Sprawdźmy dla kilku początkowych liczb pierwszych:

\[
\begin{array}{r r r r r r}
p = & 2, & \quad 2^p - 2 = &2^2-2= & 4-2= & 2 = & 1\cdot p \\
p = & 3, & \quad 2^p - 2 = &2^3-2= & 8-2= & 6 = & 2\cdot p \\
p = & 5, & \quad 2^p - 2 = &2^5-2= & 32-2= & 30 = & 6\cdot p \\
p = & 7, & \quad 2^p - 2 = &2^7-2= & 128-2= & 126 = & 18\cdot p \\
p = & 11, & \quad 2^p - 2 = &2^{11}-2= & 2048-2= & 2046 = & 186\cdot p &\quad \dots
\end{array}
\]

Powyższą własność można zapisać w postaci twierdzenia:

Niech \(p\) będzie liczbą naturalną większą od \(1\). Jeśli liczba \(2^p\) nie jest przystająca do liczby \({2^p\bmod p}\), to \(p\) jest liczbą złożoną. Innymi słowy, jeśli \({2^p\bmod p\ne2}\), 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 \({2^p\bmod p=2}\), to liczba \(p\) jest albo pierwszą (wszystkie liczby pierwsze \(p\) dzielą \{2^p-2}\)), albo pseudopierwszą przy podstawie \(2\) (ang. base 2 pseudoprime), czyli złożoną dzielącą \({2^p-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{-}\text{bitowe}}\) posiadają jedynie zakres od \(0\) do \({2^{64}-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ł.

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:

\({a^{x+y}\bmod n=(a^x\bmod n)\cdot(a^y\bmod n)\bmod n}\)

Oznacza to, iż zamiast wyliczać resztę potęgi \({a^{x+y}\bmod n}\), możemy wyznaczyć reszty modulo \(n\) potęg \(a^x\) oraz \(a^y\) i wymnożyć je modulo \(n\). Dla potęg \(a^x\) i \(a^y\) można dokonać rekurencyjnie takiego samego rozkładu.

Przykład:

Obliczyć \({2^{387}\bmod 13}\).

Rozbijamy liczbę \(387\) na sumę potęg \(2\):

\({387=256+128+2+1}\)
\({2^{387}\bmod 13=(2^{256}\bmod 13)\cdot(2^{128}\bmod 13)\cdot(2^2\bmod 13)\cdot(2^1\bmod 13)\bmod 13}\)

Teraz obliczamy reszty potęg \(2\):

2¹	mod 13 =	(2	mod 13) = 2
2²	mod 13 =	(2¹	mod 13) ·	(2¹	mod 13) mod 13 = (2 · 2) mod 13 =	4 mod 13 = 4
2⁴	mod 13 =	(2²	mod 13) ·	(2²	mod 13) mod 13 = (4 · 4) mod 13 =	16 mod 13 = 3
8⁸	mod 13 =	(2⁴	mod 13) ·	(2⁴	mod 13) mod 13 = (3 · 3) mod 13 =	9 mod 13 = 9
2¹⁶	mod 13 =	(2⁸	mod 13) ·	(2⁸	mod 13) mod 13 = (9 · 9) mod 13 =	81 mod 13 = 3
2³²	mod 13 =	(2¹⁶	mod 13) ·	(2¹⁶	mod 13) mod 13 = (3 · 3) mod 13 =	9 mod 13 = 9
2⁶⁴	mod 13 =	(2³²	mod 13) ·	(2³²	mod 13) mod 13 = (9 · 9) mod 13 =	81 mod 13 = 3
2¹²⁸	mod 13 =	(2⁶⁴	mod 13) ·	(2⁶⁴	mod 13) mod 13 = (3 · 3) mod 13 =	9 mod 13 = 9
2²⁵⁶	mod 13 =	(2¹²⁸	mod 13) ·	(2¹²⁸	mod 13) mod 13 = (9 · 9) mod 13 =	81 mod 13 = 3

Mając reszty potęg (zaznaczone tu na czerwono), wymnażamy je modulo \(13\):

\({2^{387}\bmod13 = (2^{256}\bmod13)\cdot(2^{128}\bmod13)\cdot(2^2\bmod13)\cdot(2^1\bmod13)\bmod13}\)
\({2^{387}\bmod13 = ({\class{t}3}\cdot{\class{t}9}\cdot{\class{t}4}\cdot{\class{t}2})\bmod13=216\bmod13=\class{t}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\cdot b\bmod n}\)

Wejście:

\(a,b\) : mnożone liczby; \({a,b\in\mathbb{N}}\).
\(n\) : moduł operacji mnożenia; \({n\in\mathbb{N}}\).

Wyjście:

\({w=a\cdot b\bmod n}\).

Elementy pomocnicze:

\(m\) : maska bitowa służąca do testowania ustawionych w \(b\) bitów.

Lista kroków:

K01:	\(w\leftarrow0\) ; wynik mnożenia
K02:	\(m\leftarrow1\) ; maska bitowa
K03:	Dopóki \(m\ne0,\) wykonuj kroki K04…K06
K04:	Jeśli \(b\;\&\;m\ne0,\) ; sprawdzamy ustawione bity w mnożniku to \(w\leftarrow(w+a)\bmod n\)
K05:	\(a\leftarrow(a\ll1)\bmod n\) ; przesuwamy mnożną o 1 bit w lewo
K06:	\(m\leftarrow m\ll1\) ; przesuwamy bit w masce
K07:	Pisz \(w\)
K08:	Zakończ

Algorytm obliczania a^e mod n

Wejście:

\(a\) : podstawa potęgi; \({a\in\mathbb{N}}\).
\(e\) : wykładnik dla potęgi \(a\); \({e\in\mathbb{N}}\).
\(n\) : moduł; \({n\in\mathbb{N}}\), \({n > 1}\).

Wyjście:

\(w = 2^e \bmod n\).

Elementy pomocnicze:

\(m\) : maska bitowa służąca do testowania ustawionych w \(e\) bitów.
\(p\) : reszta z kolejnych potęg \({a\bmod n}\); \({p\in\mathbb{N}}\).

Lista kroków:

K01:	\(p\leftarrow a\) ; wartość początkowa potęgi \(a^1\)
K02:	\(w\leftarrow1\) ; wynik
K03:	\(m\leftarrow1\) ; maska bitowa – ustawiony bit \(b_0\)
K04:	Dopóki \(m\ne0,\) ; obliczamy \(2^e\bmod n\) wykonuj kroki K05…K07
K05:	Jeśli \(e\;\&\; m\ne0,\) ; sprawdzamy, czy \(e\) posiada ustawiony bit na pozycji \(m\) to \(w\leftarrow w\cdot p\bmod n\) ; jeśli tak, to wynik wymnażamy przez potęgę
K06:	\(p\leftarrow p\cdot p\bmod n\) ; wyliczamy następną potęgę
K07:	\(m\leftarrow m\ll1\) ; przesuwamy w lewo bit maski
K08:	Pisz \(w\)
K09:	Zakończ

Przykładowe programy

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\({2^e \bmod 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

do podrozdziału do strony

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 \({2^p \bmod 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ą.

Przykładowe programy

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

do podrozdziału do strony

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

Problem

Wyznaczanie dużych potęg liczby 2 modulo n

Algorytm obliczania \({a\cdot b\bmod n}\)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm obliczania ae mod n

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Chiński test pierwszości

Przykładowe programy

Algorytm obliczania a^e mod n