Algorytmy i Struktury Danych - Odwrotność modulo

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\). \({\text{NWD}(5,7) = 1}\), zatem odwrotność istnieje. Zgodnie z definicją testujemy kolejne iloczyny:

\[
\begin{array}{l}
5\cdot1\bmod7=\phantom{1}5\bmod7=5\;:\;\text{NIE} \\
5\cdot2\bmod7=10\bmod7=3\;:\;\text{NIE} \\
\class{t}{5\cdot3\bmod7=15\bmod7=1\;:\;\text{TAK}}
\end{array}
\]

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 \({\text{NWD}(a,b)}\) znajduje również dwie liczby \(x\) i \(y\) spełniające tzw. tożsamość Bezouta (ang. Bezout's identity):

\({a\cdot x+b\cdot y=\text{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\cdot u+b\cdot v = w}\)
(2) \({a\cdot x+b\cdot y = z}\)

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

(3) \({\text{NWD}(a,b)=\text{NWD}(w,z)}\)

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

\({a\cdot1=b\cdot0=a}\)
\({a\cdot0=b\cdot1=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 \(\text{NWD}(a,b)=\text{NWD}(w,z),\)
to \(\text{NWD}(a,b)=\text{NWD}(w\bmod z,z)\)

Z tej samej własności korzysta również podstawowy algorytm Euklidesa przy wyznaczaniu \({\text{NWD}(a,b)}\). Musimy zatem w równaniu (1) zastąpić \(w\) przez \({w \bmod 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\operatorname{div}z}\). Następnie równanie (1) zastępujemy różnicą: \({(1)-q\cdot(2)}\):

\({a\cdot(u-q\cdot x)+b\cdot(v-q\cdot y)=w-q\cdot z}\)

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

\[
\begin{array}{l}
u\leftarrow u-q\cdot x\\
v\leftarrow v-q\cdot y\\
w\leftarrow w-q\cdot z=w\bmod z
\end{array}
\]

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\cdot u+b\cdot v=w=0}\)
(2) \({a\cdot x+b\cdot y=z=\text{NWD}(a,b)}\)

Jeśli \(z = \text{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\cdot1+5\cdot0=2}\)
(2) \({2\cdot0+5\cdot1=5}\)

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

(1) \({2\cdot0+5\cdot1=5}\)
(2) \({2\cdot1+5\cdot0=2}\)

Obliczamy iloraz \({q=5\operatorname{div}2=2}\)

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

(1) \({2\cdot(0-2\cdot1)+5\cdot(1-2\cdot0)=5-2\cdot2}\)
(1) \({2\cdot(-2)+5\cdot1=1}\)
(2) \({2\cdot1+5\cdot0=2}\)

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

(1) \({2\cdot1+5\cdot0=2}\)
(2) \({2\cdot(-2)+5\cdot1=1}\)

Obliczamy iloraz \({q=2\operatorname{div}1=2}\).

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

(1) \({2\cdot(1-2\cdot(-2))+5\cdot(0-2\cdot1)=2-2\cdot1}\)
(1) \({2\cdot5+5\cdot(-2)=0}\)
(2) \({2\cdot(-2)+5\cdot1=1}\)

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

\[
\begin{array}{l}
u&=\phantom{-}5\\
v&=-2\\
w&=\phantom{-}0\\
x&=-2\\
y&=\phantom{-}1\\
z&=\phantom{-}1
\end{array}
\]

Ponieważ

\({z=\text{NWD}(a,b)=\text{NWD}(2,5)=1}\)

to odwrotność istnieje i jest równa \(x\), które sprowadzamy do liczb dodatnich dodając \(b\):

\({x\leftarrow x+b=-2+5=3}\)

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

\(a\cdot x\bmod b=2\cdot3\bmod5=6\bmod5=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\in\mathbb{Z}}\).
\(b\) : moduł odwrotności; \({b\in\mathbb{Z}}\).

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\in\mathbb{Z}}\).
\(q\) : całkowity iloraz; \({q\in\mathbb{Z}}\).

Lista kroków:

K01:	\(u\leftarrow1;\;w\leftarrow a;\;x\leftarrow0;\;z\leftarrow b\) ; ustalamy wartości ; początkowe współczynników
K02:	Dopóki \(w\ne0:\) ; w pętli modyfikujemy wykonuj kroki K03…K06 ; współczynniki równań
K03:	Jeśli \(w < z,\) ; aby algorytm wyliczał to \(u\leftrightarrow x;\;w\leftrightarrow z\) ; nowe współczynniki, ; \(w\) nie może być mniejsze od \(z\). Jeśli jest, ; zamieniamy ze sobą współczynniki równań
K04:	\(q\leftarrow w \operatorname{div}z\) ; obliczamy iloraz całkowity
K05:	\(u\leftarrow u-q\cdot x\) ; od równania (1) odejmujemy ; równanie (2) wymnożone przez q
K06:	\(w\leftarrow w-q\cdot z\)
K07:	Jeśli \(z\ne1,\) ; dla \(z\) różnego od \(1\) nie istnieje to idź do kroku K10 ; odwrotność modulo
K08:	Jeśli \(x < 0,\) ; ujemne \(x\) sprowadzamy to \(x\leftarrow x+b\) ; do wartości dodatnich
K09:	Pisz \(x\) ; \(x\) jest poszukiwaną odwrotnością modulo i zakończ
K10:	Pisz "brak rozwiązania"
K11:	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

JavaScript

<html>
  <head>
    <title>
      Odwrotność modulo
    </title>
  </head>
  <body>

<div style="overflow-x: auto; overflow-y: hidden;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align: center;
               background-color:
               #E7E7DA">
          <b>Odwrotność modulo</b><br/>
          &nbsp;&nbsp;(C)2026
          mgr Jerzy Wałaszek
          &nbsp;&nbsp;
          <hr>
          a = 
			<input
              type="text"
              name="inp_a"
              size="16"
              value="12767"
              style="text-align:
                     right">
          <br>
          b = 
			<input
              type="text"
              name="inp_b"
              size="16"
              value="256"
              style="text-align:
                     right">
          <hr>
          <input
          type="button"
          value="Wykonaj"
          name="B1"
          onclick="main()">
          <hr>
          <b>Wynik:</b>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>

// Odwrotność modulo
// Data   : 15.03.2008
// (C)2008 mgr Jerzy Wałaszek
//----------------------------

function main()
{
  var a, b, u, w, x, z, q, t;

  a = parseInt (document.frm
      .inp_a.value);
  b = parseInt (document.frm
      .inp_b.value);
  if(!isNaN(a) && !isNaN(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 = Math.floor (w / z);
      u -= q * x;
      w -= q * z;
    }
    if(z == 1)
    {
      if(x < 0) x += b;
      t = x;
    }
    else t = "BRAK";
  }
  else
    t = "Złe dane wejściowe!";
  document.getElementById("out")
  .innerHTML = t;
}

</script>

  </body>
</html>

do podrozdziału do strony

Odwrotność modulo – rozszerzony algorytm Euklidesa

Problem