Odwrotność modulo – rozszerzony algorytm Euklidesa


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

Dla danych liczb naturalnych a i b znaleźć taką liczbę naturalną x, aby a × x mod b = 1 lub stwierdzić, iż liczba x nie istnieje.

 

 

Liczbę x nazywamy odwrotnością modulo b (ang. modular multiplicative inverse) liczby a – przez analogię do zwykłej odwrotności liczby. Wbrew pozorom problem wcale nie należy do łatwych i może się zdarzyć, iż liczba x nie istnieje (b istnieje na pewno, jeśli liczby a i b są względnie pierwsze). Odwrotność modulo jest szeroko stosowana we współczesnej kryptografii.

 

Przykład

Znajdźmy odwrotność modulo 7 liczby 5. NWD(5,7) = 1, zatem odwrotność istnieje. Zgodnie z definicją testujemy kolejne iloczyny:

 

5 × 1 mod 7 = 5 mod 7 = 5 – NIE
5 × 2 mod 7 = 10 mod 7 = 3 – NIE
5 × 3 mod 7 = 15 mod 7 = 1 – TAK

 

Zatem odwrotnością modulo 7 liczby 5 jest liczba 3.

 

Rozszerzony algorytm Euklidesa

Odwrotność modulo znajdujemy przy pomocy rozszerzonego algorytmu Euklidesa (ang. extended Euclidean algorithm), który oprócz znajdowania NWD(a,b) znajduje również dwie liczby x i y spełniające tzw. tożsamość Bezouta (ang. Bezout's identity):

 

ax + by = NWD(a,b)

 

Jeśli liczby a i b są względnie pierwsze, to liczba x jest odwrotnością modulo b liczby a.

Zadanie rozwiązujemy pracując z parą równań zapisanych następująco:

 

(1)      a × u + b × v = w
(2)      a × x + b × y = z

 

Zażądajmy, aby zawsze spełniony był warunek:

 

(3)      NWD(a,b) = NWD(w,z)

 

Na początku zapiszmy te dwa równania w poniższej postaci:

 

a × 1 + b × 0 = a
a × 0 + b × 1 = b

 

Wynika z tego, iż współczynniki u, v, w, x, y, i z przyjmują odpowiednio wartości:

 

u = 1, v = 0, w = a
x = 0, y = 1, z = b

 

Zwróć uwagę, iż dla tak określonych współczynników są spełnione równania (1) i (2) oraz tożsamościowo warunek (3).

Teraz będziemy powtarzać transformacje równań (1) i (2) w pętli, aż otrzymamy wynik w = 0.

Najpierw sprawdzamy, czy w < z. Jeśli tak, to zamieniamy miejscami równania (1) z (2), tzn. wymieniamy ze sobą współczynniki x z u, v z y i w z z. Po tej operacji w jest równe lub większe od z. Korzystamy z następującej własności NWD:

 

Jeśli NWD(a,b) = NWD(w,z), to NWD(a,b) = NWD(w mod z, z)

 

Z tej samej własności korzysta również podstawowy algorytm Euklidesa przy wyznaczaniu NWD(a,b). Musimy zatem w równaniu (1) zastąpić w przez w mod z. Aby jednak równanie (1) było wciąż spełnione, pozostałe współczynniki u i v również należy odpowiednio zmienić. Wyznaczamy zatem całkowity iloraz q = w div z. Następnie równanie (1) zastępujemy różnicą: (1)  - q(2):

 

a × (u - q × x) + b × (v - q × y) = w - q × z

 

Otrzymujemy zatem modyfikację współczynników w równaniu (1):

 

u  ←  u - q × x
v  ← v - q × y
w  ← w - q × z = w mod z

 

Po wykonaniu powyższych podstawień wracamy do początku pętli i kontynuujemy ją aż do otrzymania w = 0. Ponieważ w i z są modyfikowane tak samo jak w podstawowym algorytmie Euklidesa, to gdy w przybierze wartość 0 otrzymamy następującą parę równań:

 

(1)     a × u + b × v = w = 0
(2)     a × x + b × y = z = NWD(a,b)

 

Jeśli z = NWD(a,b) = 1, to istnieje odwrotność modulo b z liczby a i jest ona równa x. Jednakże x może przyjąć wartość ujemną. Wtedy sprowadzamy je do wartości dodatniej dodając b.

 

Przykład

Obliczyć odwrotność modulo 5 z 2. Czyli a = 2, b = 5

Tworzymy parę równań:

 

(1)     2 × 1 + 5 × 0 = 2
(2)     2 × 0 + 5 × 1 = 5

 

Ponieważ 2 < 5, równania zamieniamy miejscami:

 

(1)     2 × 0 + 5 × 1 = 5
(2)     2 × 1 + 5 × 0 = 2

 

Obliczamy iloraz q = 5 div 2 = 2

Od równania (1) odejmujemy (2) pomnożone przez q:

 

(1)     2 × (0 - 2 × 1) + 5 × (1 - 2 × 0) = 5 - 2 × 2
(1)     2 × (-2) + 5 × 1 = 1
(2)     2 × 1 + 5 × 0 = 2

 

Ponieważ 1 < 2, równania (1) i (2) zamieniamy miejscami:

 

(1)     2 × 1 + 5 × 0 = 2
(2)     2 × (-2) + 5 × 1 = 1

 

Obliczamy iloraz q = 2 div 1 = 2

Od równania (1) odejmujemy (2) pomnożone przez q:

 

(1)     2 × (1 - 2 × (-2)) + 5 × (0 - 2 × 1) = 2 - 2 × 1
(1)     2 × 5 + 5 × (- 2) = 0
(2)     2 × (-2) + 5 × 1 = 1

 

Otrzymaliśmy w = 0, kończymy modyfikowanie równań. Wyniki są następujące:

 

u = 5,  v = -2,  w = 0
x = -2, y = 1,  z = 1

 

Ponieważ z = NWD(a,b) = NWD(2,5) = 1, to odwrotność istnieje i jest równa x, które sprowadzamy do liczb dodatnich dodając b:

 

xx + b = -2 + 5 = 3

 

Sprawdzamy, czy otrzymany wynik spełnia definicję odwrotności modulo:

 

a × x mod b = 2 × 3 mod 5 = 6 mod 5 = 1 - zgadza się!

 

Prosta analiza powyższych obliczeń pokazuje, iż możemy z czystym sumieniem pominąć wyznaczanie współczynników v oraz y – nie są one wykorzystywane do wyliczania u, w, x i z, które jedynie się tutaj liczą. Pozwala to uprościć algorytm wyznaczania odwrotności modulo.

 

Algorytm wyznaczania odwrotności modulo

Wejście
a     liczba, której odwrotność modulo obliczamy, a N
b  – moduł odwrotności, b N
Wyjście:

odwrotność modulo b z liczby a lub informacja, iż odwrotność taka nie istnieje

Zmienne pomocnicze
u,w,x,z  –  współczynniki równań. u,v,w,x,y,z Z
q     całkowity iloraz. q Z
Lista kroków:
K01: u ← 1;  wa;
x ← 0; zb
; ustalamy wartości początkowe współczynników
K02: Dopóki w ≠ 0 wykonuj kroki K03...K06 ; w pętli modyfikujemy współczynniki równań
K03:     Jeśli w < z, to  u x;   w z ; aby algorytm wyliczał nowe współczynniki, w nie może być mniejsze od z
; jeśli jest, zamieniamy ze sobą współczynniki równań
K04:     qw div z ; obliczamy iloraz całkowity
K05:     uu - q × x ; od równania (1) odejmujemy równanie (2) wymnożone przez q
K06:     ww - q × z  
K07: Jeśli z ≠ 1, to idź do K10 ; dla z różnego od 1 nie istnieje odwrotność modulo
K08: Jeśli x < 0, to xx + b ; ujemne x sprowadzamy do wartości dodatnich
K09: Pisz x i zakończ ; x jest poszukiwaną odwrotnością modulo
K10: Pisz brak rozwiązania i 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 liczbę a oraz moduł b. W następnym wierszu wypisuje odwrotność modulo b liczby a lub pojedyncze słowo "BRAK".

 

Lazarus Code::Blocks Free Basic
// Odwrotność modulo
// Data   : 15.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

var a,b,u,w,x,z,q : longint;

begin
  readln(a,b);
  u := 1; w := a;
  x := 0; z := b;
  while w <> 0 do
  begin
    if w < z then
    begin
      q := u; u := x; x := q;
      q := w; w := z; z := q;
    end;
    q := w div z;
    u := u - q * x;
    w := w - q * z;
  end;
  if z = 1 then
  begin
    if x < 0 then inc(x,b);
    writeln(x);
  end
  else writeln('BRAK');
end.
// Odwrotność modulo
// Data   : 15.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

int main()
{
  int a,b,u,w,x,z,q;

  cin >> a >> b;
  u = 1; w = a;
  x = 0; z = b;
  while(w)
  {
    if(w < z)
    {
      q = u; u = x; x = q;
      q = w; w = z; z = q;
    }
    q = w / z;
    u -= q * x;
    w -= q * z;
  }
  if(z == 1)
  {
    if(x < 0) x += b;
    cout << x << endl;
  }
  else cout << "BRAK\n";
  return 0;
}
' Odwrotność modulo
' Data   : 15.03.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

Dim As Integer a,b,u,w,x,z,q

Input a,b
u = 1: w = a
x = 0: z = b
While w <> 0
  If w < z Then
    q = u: u = x: x = q
    q = w: w = z: z = q
  End If
  q = w \ z
  u = u - q * x
  w = w - q * z
Wend
If z = 1 Then
  If x < 0 Then x += b
  Print x
Else
  Print "BRAK"
End If
End
Wynik
  12767 256
31

12768 256
BRAK

 
 

Odwrotność modulo
(C)2012 mgr Jerzy Wałaszek

a = , b =


...

 



List do administratora Serwisu Edukacyjnego 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

(C)2014 mgr Jerzy Wałaszek

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