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