Pierwszość liczby naturalnej – test Millera-Rabina


Tematy pokrewne
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

 

Problem

Sprawdzić, czy liczba naturalna p jest pierwsza.

 

 

Opisany w tym rozdziale algorytm testowania pierwszości (ang. primality testing algorithm) liczby naturalnej p został opracowany w roku 1975 przez Michaela O. Rabina na podstawie prac Gary'ego L. Millera. Udostępnia on szybką metodę sprawdzania pierwszości liczby z możliwością kontrolowania poziomu prawdopodobieństwa popełnienia błędu – jest to zatem metoda probabilistyczna, zwana testem Millera-Rabina (ang. the Rabin-Miller Probabilistic Primalty Algorithm).

Test Millera-Rabina oparty jest na następującym twierdzeniu:

 

Niech p będzie nieparzystą liczbą pierwszą zapisaną jako p = 1 + 2sd, gdzie d jest nieparzyste. Wtedy dla dowolnej liczby naturalnej a ∈ <2, p - 2> ciąg Millera-Rabina:

 

a d , a 2d , a 4d , ..., a 2s-1d , a 2sd  (mod p)
         

 

kończy się liczbą 1. Co więcej, jeśli ad nie przystaje modulo p do 1, to wyraz ciągu Millera-Rabina bezpośrednio poprzedzający 1 jest równy p - 1.

 

Jeśli liczba p przejdzie test, to jest albo pierwsza, albo silnie pseudopierwsza przy podstawie a. Test Millera-Rabina daje złe wyniki (p złożona) dla co najwyżej 1/4 baz a < p. Zatem dla jednego przebiegu prawdopodobieństwo błędu wynosi 1/4. Dla n przebiegów przy różnych podstawach a prawdopodobieństwo błędu spada do (1/4)n. Już dwadzieścia testów daje szansę 1 do 1099511627776, iż liczba złożona p zostanie potraktowana jako pierwsza. Widzimy zatem wyraźnie, iż liczbę p możemy sprawdzić na pierwszość z bardzo dużym prawdopodobieństwem wykonując odpowiednią liczbę testów Millera-Rabina.

W algorytmie testu Millera-Rabina wykorzystujemy procedury mnożenia i potęgowania modulo, które opisaliśmy w rozdziale o chińskim teście pierwszości. Test ten wykorzystują obecnie prawie wszystkie systemy kryptografii publicznej do testowania pierwszości dużych liczb potrzebnych przy generacji kluczy szyfrujących/deszyfrujących.

 

Algorytm sprawdzania pierwszości nieparzystej liczby naturalnej testem Millera-Rabina

Wejście
p     liczba badana na pierwszość, p N, p > 2, p jest nieparzyste
n  – ilość powtórzeń testu Millera-Rabina, n N
Wyjście:

TAK, jeśli p jest pierwsze lub silnie pseudopierwsze z prawdopodobieństwem (1/4)n.
NIE , jeśli p jest liczbą złożoną

Elementy pomocnicze:
s    wykładnik potęgi 2 w dzielniku p - 1. s N
d  – mnożnik potęgi 2 w dzielniku p - 1. d N
i  – zlicza wykonane testy Millera-Rabina, i N
a  – baza. a N, a <2,p-2>
x  – wyraz ciągu Millera-Rabina, x N
j  – zlicza wyrazy ciągu Millera-Rabina, j N
Lista kroków:
K01: dp - 1 ; obliczamy s i d
K02: s ← 0  
K03: Dopóki d mod 2 = 0, wykonuj K04...K05 ; usuwamy z p - 1 dzielniki 2 zliczając je w s
K04:     ss + 1  
K05:     dd div 2  
K06: Dla i = 1,2,...,n, wykonuj K07...K15 ; wykonujemy n testów Millera-Rabina
K07:     a ← Losuj(2,p-2) ; losujemy bazę a
K08:     xad mod p ; wyliczamy pierwszy wyraz ciągu Millera-Rabina
K09:     Jeśli (x = 1) ∨ (x = p - 1), to następny obieg K06 ; jeśli x nie spełnia warunku, wybieramy inne a
K10:     j ← 1  
K11:     Dopóki (j < s) ∧ (xp - 1), wykonuj K12...K14 ; rozpoczynamy generację kolejnych wyrazów ciągu Millera-Rabina
K12:         xx2 mod p ; obliczamy kolejny wyraz
K13:         Jeśli x = 1, to idź do K17 ; tylko ostatni wyraz ciągu Millera-Rabina może mieć wartość 1!
K14:         jj + 1  
K15:     Jeśli xp - 1, to idź do K17 ; przedostatni wyraz ciągu Millera-Rabina musi być równy p - 1
K16: Pisz "TAK" i zakończ ; pętla wykonała n testów i zakończyła się naturalnie.
K17: Pisz "NIE" i zakończ ; liczba p nie przeszła testów Millera-Rabina

 

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 liczbę p oraz ilość testów Millera-Rabina n, a w drugim wierszu wypisuje:

TAK – jeśli liczba p jest pierwsza z prawdopodobieństwem 1 - (1/4)n

NIE – jeśli liczba p jest liczbą złożoną

 

Lazarus
// Test Millera-Rabina
// Data   : 6.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

// 64 bitowy generator pseudolosowy
//---------------------------------
function Losuj(a,b : qword) : qword;

var w : qword;
    i : integer;
begin
  for i := 1 to 8 do
  begin
    w := w shl 8;
    w := w or random(256);
  end;
  Losuj := a + (w mod (b - a));
end;

// 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 a^e mod n
//--------------------------
function PotegujModulo(a,e,n : qword) : qword;

var m,p,w : qword;

begin
  p := a; 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 a,d,p,x : qword;
    i,j,s,n : integer;
    t : boolean;

begin
  randomize;
  readln(p,n);
  d := p - 1;
  s := 0;
  while d mod 2 = 0 do
  begin
    inc(s); d := d div 2;
  end;
  t := true;
  for i := 1 to n do
  begin
    a := Losuj(2,p-2);
    x := PotegujModulo(a,d,p);
    if (x = 1) or (x = p - 1) then continue;
    j := 1;
    while (j < s) and (x <> p - 1) do
    begin
      x := MnozModulo(x,x,p);
      if x = 1 then
      begin
        t := false; break;
      end;
      inc(j);
    end;
    if not t then break;
    if x <> p - 1 then
    begin
      t := false; break;
    end;
  end;
  if t then writeln('TAK')
  else      writeln('NIE');
end.
Code::Blocks
// Test Millera-Rabina
// Data   : 6.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

typedef unsigned long long ulong;

// 64 bitowy generator pseudolosowy
//---------------------------------
ulong Losuj(ulong a,ulong b)
{
  ulong w;
  int i;

  for(i = 1; i <= 8; i++)
  {
    w <<= 8;
    w |= rand() % 256;
  }
  return a + (w % (b - a));
}

// Funkcja mnoży a i b mod n
//--------------------------
ulong MnozModulo(ulong a, ulong b, ulong n)
{
  ulong m,w;

  w = 0;
  for(m = 1; m; m <<= 1)
  {
    if(b & m) w = (w + a) % n;
    a = (a << 1) % n;
  }
  return w;
}

// Funkcja oblicza a^e mod n
//--------------------------
ulong PotegujModulo(ulong a, ulong e, ulong n)
{
  ulong m,p,w;

  p = a; w = 1;
  for(m = 1; m; m <<= 1)
  {
    if(e & m) w = MnozModulo(w,p,n);
    p = MnozModulo(p,p,n);
  }
  return w;
}

int main()
{
  ulong a,d,p,x;
  int i,j,s,n;
  bool t;

  srand((unsigned)time(NULL));
  cin >> p >> n;
  s = 0;
  for(d = p - 1; d % 2 == 0; s++) d /= 2;
  t = true;
  for(i = 1; i <= n; i++)
  {
    a = Losuj(2,p-2);
    x = PotegujModulo(a,d,p);
    if((x == 1) || (x == p - 1)) continue;
    for(j = 1; (j < s) && (x != p - 1); j++)
    {
      x = MnozModulo(x,x,p);
      if(x == 1)
      {
        t = false; break;
      }
    }
    if(!t) break;
    if(x != p - 1)
    {
      t = false; break;
    }
  }
  cout << (t ? "TAK" : "NIE") << endl;
  return 0;
}
Free Basic
' Test Millera-Rabina
' Data   : 6.04.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

' 64 bitowy generator pseudolosowy
'---------------------------------
Function Losuj(Byval a As Ulongint, Byval b As Ulongint) As Ulongint

  Dim w As Ulongint, i As Integer

  For i = 1 To 8
    w = w Shl 8
    w = w Or Culngint(Rnd(1)* 256)
  Next
  Losuj = a + (w Mod (b - a))
End Function

' 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 a^e mod n
'--------------------------
Function PotegujModulo(Byval a As Ulongint, Byval e As Ulongint, Byval n As Ulongint) As Ulongint

  Dim As Ulongint m,p,w

  p = a: 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 As Ulongint a,d,p,x
Dim As Integer i,j,s,n
Dim t As Byte

Randomize
Input p,n
d = p - 1
s = 0
While d Mod 2 = 0
  s += 1: d \= 2
Wend
t = 1
For i = 1 To n
  a = Losuj(2,p-2)
  x = PotegujModulo(a,d,p)
  If (x = 1) Or (x = p - 1) Then Continue For
  j = 1
  While (j < s) And (x <> p - 1)
    x = MnozModulo(x,x,p)
    If x = 1 Then
      t = 0: Exit While
    End If
    j += 1
  Wend
  If t = 0 Then Exit For
  If x <> p - 1 Then
    t = 0: Exit For
  End If
Next
If t = 1 Then Print "TAK": Else Print "NIE"
End
Wynik
9223372036854775783 20
TAK

9223372036854775787 1
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.