Czym jest odwrotność?

Przypomnijmy, że liczba pomnożona przez swoją odwrotność jest równa 1. Z podstaw arytmetyki wiemy, że:
  • Odwrotnością liczby A jest 1/A, ponieważ A * 1/A = 1 (np. odwrotnością 5 jest 1/5)
  • Wszystkie liczby rzeczywiste różne od 0 mają liczby odwrotne
  • Pomnożenie liczby przez odwrotność A jest równoważne podzieleniu jej przez A (np. 10/5 to to samo, co 10* 1/5)

Czym jest odwrotność modulo?

W arytmetyce modularnej nie mamy operacji dzielenia. Jednak dysponujemy odwrotnością modularną.
  • Odwrotnością modularną A (mod C) jest A^-1
  • (A * A^-1) ≡ 1 (mod C) ub równoważnie (A * A^-1) mod C = 1
  • Tylko liczby względnie pierwsze z C (liczby nie posiadające wspólnych czynników pierwszych z C) posiadają odwrotność modularną (mod C)

Jak znaleźć odwrotność modularną

Metoda naiwna znajdowania odwrotności modularnej do A (mod C) to:
krok 1. Oblicz A * B mod C, dla wartości B od 0 do C-1
krok 2. Odwrotnością modularną A mod C jest takie B, że A * B mod C = 1
Zauważ, że B mod C może przyjmować wartości całkowite wyłącznie od 0 do C-1, więc testowanie dla większych wartości  B jest zbyteczne.

Przykład: A=3, C=7

Krok 1. Obliczmy A * B mod C dla B z przedziału 0 do C-1

3 * 0 ≡ 0 (mod 7)
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7)   <--- ZNALEZIONO ODWROTNOŚĆ!
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)

Krok 2. Odwrotnością modularną A mod C jest takie B, że A * B mod C = 1

5 jest odwrotnością modularną 3 mod 7 ponieważ 5*3 mod 7 = 1
Proste!
Policzmy jeszcze jeden przykład, w którym nie znajdujemy odwrotności.

Przykład: A=2 C=6

Krok 1. Obliczmy A * B mod C dla B z przedziału 0 do C-1

2 * 0 ≡ 0 (mod 6)
2 * 1 ≡ 2 (mod 6)
2 * 2 ≡ 4 (mod 6)
2 * 3 ≡ 6 ≡ 0 (mod 6)
2 * 4 ≡ 8 ≡ 2 (mod 6)
2 * 5 ≡ 10 ≡ 4 (mod 6)

Krok 2. Odwrotnością modularną A mod C jest takie B, że A * B mod C = 1

Warunek A * B mod C = 1, nie jest spełniony dla żadnego B. Tak więc, A nie posiada odwrotności modularnej (mod 6).
Dzieje się tak dlatego, że 2 nie jest względnie pierwsze z 6 (mają wspólny czynnik pierwszy 2).

Ta metoda wydaje się powolna...

Istnieje dużo szybszy sposób znajdowania odwrotności A (mod C). Przedyskutujemy ją w kolejnych artykułach dotyczących Rozszerzonego Algorytmu Euklidesa.
Ładowanie