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

Odwrotność modulo – rozszerzony algorytm Euklidesa

SPIS TREŚCI

Problem

Dla danych liczb naturalnych a  i b  należy znaleźć taką liczbę naturalną x, aby była spełniona równość a × x  mod b  = 1, lub stwierdzić, iż liczba naturalna x  nie spełnia tej równości.

Rozwiązanie

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 ( x  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:

x  ← x  + 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, aN.
b  – moduł odwrotności, bN.

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, zZ.
q  –   całkowity iloraz. qZ.

Lista kroków:

K01: u  ← 1;  w  ← a;
x  ← 0; z  ← b
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:     q  ← w  div z obliczamy iloraz całkowity
K05:     u  ← u  - q  × x od równania ( 1 ) odejmujemy równanie ( 2 ) wymnożone przez q
K06:     w  ← w  - q  × z  
K07: Jeśli z  ≠ 1,
to idź do kroku K10
dla z różnego od 1 nie istnieje odwrotność modulo
K08: Jeśli x  < 0,
to x  ← x  + 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  

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 liczbę a oraz moduł b. W następnym wierszu wypisuje odwrotność modulo b  liczby a  lub pojedyncze słowo "BRAK".
Pascal
// Odwrotność modulo
// Data   : 15.03.2008
// (C)2020 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.
   C++
// Odwrotność modulo
// Data   : 15.03.2008
// (C)2020 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;
}
   Basic
' Odwrotność modulo
' Data   : 15.03.2008
' (C)2020 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
  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)2020 mgr Jerzy Wałaszek

a =
b =


...

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.