Jak w prosty sposób policzyć odwrotność modularną?

Jak w prosty sposób policzyć odwrotność modularną?

W trakcie nauki do jutrzejszego kolokwium z kryptologii musiałem opanować sposób liczenia odwrotności modularnej liczby. Publikuję opracowany przeze mnie sposób, z nadzieją, że komuś się kiedyś przyda.

Jeśli mamy policzyć powiedzmy 7-1 mod26, to piszemy:

mam nadzieję, że nie-informatycy nie będą mieli problemu ze zrozumieniem notacji wskaźnika do wiersza tabeli. 🙂 Pozdrawiam wszystkich piszących w C/C++/asm!

*7 *26 w q
0 1 26
1 0 7 _26/7_=3 //row[1] = row[-1] – row[0]*q ;row++
-3 1 5 _7/5_=1 //row[1] = row[-1] – row[0]*q ;row++
4 -1 2 _5/2_=2 //row[1] = row[-1] – row[0]*q ;row++
-11 -3 1 _2/1_=2 //row[1] = row[-1] – row[0]*q ;row++
26 5 0 pamiętaj cholero, nie dziel przez zero!

Teraz w[-1] i w[0] rzutujemy na strukturkę:

x y z
u v w

i otrzymujemy:

x=-11 y=-3 z=1
u=26 v=5 w=0

Gdzie x jest wynikiem. Możemy jeszcze policzyć, że (-11+26 mod26) == (15 mod26) jeśli nam to jest do szczęścia potrzebne.

A do czego to się przyda na dłuższą metę? Jeśli mamy złamać szyfr affiniczny, i wiemy, że literka A jest zaszyfrowana jako U, zaś P odpowiada V, to wiemy, że mamy do czynienia odwzorowaniem: 0->20 i 15->21. I to wszystko przy mod26.

Szyfr afiniczny działa w ten sposób, że literkę mnoży przez coś, dodaje coś do niej, a wynik dzieli modulo 26. W przykładzie z którego korzystam podana została literka A, z której mogę odczytać przesunięcie: 20. Wtedy zdekodować literkę możemy przez odjęcie przesunięcia i pomnożenie przez odwrotność modulo.

Inna sprawa, że ten przykład jest banalny, bo

21=15*mul+offset

Czyli

21-offset = 15 * mul

I z tego wynika że:

1 = 15*mul

Dla tych, którzy jeszcze nie załapali: odwrotnością modularną mul jest 15, więc jak na dłoni widać:

mul * mul-1 = 1

Bez całego tego żmudnego liczenia…. Tylko wg któregoś z praw Murphy’ego przykład który będzie na najbliższym kolokwium nie będzie taki banalny.

Algorytm, który opisałem jest oparty o rozszerzony algorytm Euklidesa. Trzeba też zaznaczyć, że odwrotności modularnej nie policzymy, gdy liczba której odwrotność liczymy nie jest względnie pierwsza z tym, co stoi po mod.
Dokładniejsze, choć przystępne omówienie algorytmu liczenia odwrotności modularnej jest omówione tutaj: http://edu.i-lo.tarnow.pl/inf/alg/001_search/0008.php