Serwis Edukacyjny w I-LO w Tarnowie 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 |
ProblemDla 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. |
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.
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.
Odwrotność modulo b z liczby a lub informacja, iż odwrotność taka nie istnieje.
K01: u ← 1; w ← a; 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 u ↔ x; w ↔ z ; 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, ; 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 x ← x + b K09: Pisz x ; x jest poszukiwaną odwrotnością modulo i zakończ K11: Pisz brak rozwiązania K12: Zakończ
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. |
// 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 |
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: 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 print(x) else: print("BRAK") |
Wynik: |
12767 256 31 12768 256 BRAK |
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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.