Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

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

SPIS TREŚCI
Podrozdziały

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:

Aby sprawdzić, czy liczba p  jest pierwsza, dzielimy ją próbnie przez liczby z przedziału [ 2, √p ]. Liczb tych jest:

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:

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:

Widzimy wyraźnie, iż czas obliczeń jest niewyobrażalnie duży – cały nasz Wszechświat istnieje "zaledwie" 1, 3 × 10 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:

p = 2, 2 p - 2 = 2 2 - 2 = 4 - 2 = 2 = 1 × p
p = 3, 2 p - 2 = 2 3 - 2 = 8 - 2 = 6 = 2 × p
p = 5, 2 p - 2 = 2 5 - 2 = 32 - 2 = 30 = 6 × p
p = 7, 2 p - 2 = 2 7 - 2 = 128 - 2 = 126 = 18 × p
p = 11, 2 p - 2 = 2 11 - 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 2 p  nie jest przystająca do liczby 2 modulo p, to p  jest liczbą złożoną.

Innymi słowy, jeśli 2 p  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 2 p  mod 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ą.

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

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

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:

a x + y mod n  = ( a x  mod n  ) × ( a y  mod n  ) mod n

Oznacza to, iż zamiast wyliczać resztę potęgi a x + y  mod 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 367 mod 13.

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

387 = 256 + 128 + 2 + 1

2 387 mod 13 = ( 2 256 mod 13 ) × ( 2 128 mod 13 ) × ( 2 2 mod 13 ) × ( 2 1 mod 13 ) mod 13

Teraz obliczamy reszty potęg 2:

2 1 mod 13 = 2 mod 13 = 2
2 2 mod 13 = ( 2 1 mod 13 ) × ( 2 1 mod 13 ) mod 13 = ( 2  × 2 ) mod 13 = 4 mod 13 = 4
2 4 mod 13 = ( 2 2 mod 13 ) × ( 2 2 mod 13 ) mod 13 = ( 4  × 4 ) mod 13 = 16 mod 13 = 3
2 8 mod 13 = ( 2 4 mod 13 ) × ( 2 4 mod 13 ) mod 13 = ( 3  × 3 ) mod 13 = 9 mod 13 = 9
2 16 mod 13 = ( 2 8 mod 13 ) × ( 2 8 mod 13 ) mod 13 = ( 9  × 9 ) mod 13 = 81 mod 13 = 3
2 32 mod 13 = ( 2 16 mod 13 ) × ( 2 16 mod 13 ) mod 13 = ( 3  × 3 ) mod 13 = 9 mod 13 = 9
2 64 mod 13 = ( 2 32 mod 13 ) × ( 2 32 mod 13 ) mod 13 = ( 9  × 9 ) mod 13 = 81 mod 13 = 3
2 128 mod 13 = ( 2 64 mod 13 ) × ( 2 64 mod 13 ) mod 13 = ( 3  × 3 ) mod 13 = 9 mod 13 = 9
2 256 mod 13 = ( 2 128 mod 13 ) × ( 2 128 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:

2 387 mod 13 = ( 2 256 mod 13 ) × ( 2 128 mod 13 ) × ( 2 2 mod 13 ) × ( 2 1 mod 13 ) mod 13
2 387 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.

Zmienne 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 kroki K04...K06
 
K04:     Jeśli b  and m  ≠ 0,
    to w  ← w  + 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:     m  ← m  shl 1 przesuwamy bit w masce
K07: Pisz w  
K08: Zakończ  

Algorytm obliczania a e  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  = 2 e mod n.

Zmienne 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 a 1
K02: w  ← 1 wynik
K03: m  ← 1 maska bitowa – ustawiony bit b 0
K04: Dopóki m  ≠ 0,
wykonuj kroki K05...K07
obliczamy 2 e mod n
K05:     Jeśli e  and m  ≠ 0,
    to w  ← w  × p  mod n
sprawdzamy, czy e posiada ustawiony bit na pozycji z m
; 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  

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  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
Wynik:
283125637241 551842729812
4916904288980
Na początek:  podrozdziału   strony 

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


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
Wynik:
9223372036854775783
TAK

9223372036854775787
NIE
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 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: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.