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

©2024 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):

a×x+b×y = 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 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(ab). 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):

uu-q×x
vv-q×y
ww-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, xz, 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.

Elementy pomocnicze:

u,w,x,z : współczynniki równań; u,w,x,z ∈ Z.
q : całkowity iloraz; q ∈ Z.

Lista kroków:

K01: u ← 1; wa; x ← 0; z ← b ; ustalamy wartości początkowe współczynników
K02: Dopóki w ≠ 0: ; w pętli modyfikujemy współczynniki równań
     wykonuj kroki K03…K06
K03:   Jeśli w < z, ; aby algorytm wyliczał nowe współczynniki,
       to ux; wz ; 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, ; dla z różnego od 1 nie istnieje odwrotność modulo
     to idź do kroku K11
K08: Jeśli x < 0, ; ujemne x sprowadzamy do wartości dodatnich
     to xx+b
K09: Pisz x ; x jest poszukiwaną odwrotnością modulo
     i zakończ
K11: Pisz brak rozwiązania
K12: 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)
    {
      swap(u,x);
      swap(w,z);
    }
    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 -= q*x
  w -= q*z
Wend
If z = 1 Then
  If x < 0 Then x += b
  Print x
Else
  Print "BRAK"
End If
End
Python (dodatek)
# Odwrotność modulo
# Data   : 5.02.2024
# (C)2024 mgr Jerzy Wałaszek
# ----------------------------

arr = input().split(" ")
a = int(arr[0])
b = int(arr[1])
u,w,x,z = 1,a,0,b
while w:
    if w < z:
        u,x = x,u
        w,z = z,w
    q = w//z
    u -= q*x
    w -= q*z
if z == 1:
    if x < 0: x += b
    print(x)
else:
    print("BRAK")
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
©2024 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.