Come calcolare la matrice della chiave inversa nell'algoritmo Hill Cipher?

Question

Sto trovando molto difficile capire il modo in cui l'inversa della matrice viene calcolata nell'algoritmo Hill Cipher. Ho l'impressione che tutto sia fatto in modulo aritmetico, ma in qualche modo le cose non si sommano. Gradirei davvero una semplice spiegazione!

Si consideri il seguente Hill Cipher matrice chiave:

5 8 
17 3 

Si prega di utilizzare la matrice di cui sopra per l'illustrazione.

Answer 1

dovete studiare la Linear congruence theorem e la extended GCD algorithm, che appartengono alla Number Theory, al fine di comprendere la matematica dietro modulo arithmetic.

L'inverso di matrice K per esempio è (1/det (K)) * adjoint (K), in cui det (K) <> 0.

presumo che non si capisce come calcolare il 1/det(K) in aritmetica modulo e qui è dove le congruenze lineari e GCD vengono a giocare.

K ha det (K) = -121. Diciamo che il modulo m è 26. Vogliamo x * (- 121) = 1 (mod 26).
[a = b (mod m) significa che ab = N * m]

Possiamo facilmente trovare che per x = 3 quanto sopra congruenza è vero perché 26 divide (3 * (- 121) - 1) esattamente. Ovviamente, il modo corretto è utilizzare GCD al contrario per calcolare la x, ma non ho tempo per spiegare come farlo. Controllare l'algoritmo GCD esteso :)

Ora, inv (K) = 3 * ([3 -8], [-17 5]) (mod 26) = ([9 -24], [-51 15 ]) (mod 26) = ([9 2], [1 15]).

Aggiornamento: check out Basics of Computational Number Theory per vedere come calcolare inverse modulari con l'algoritmo di Euclide esteso. Si noti che -121 mod 26 = 9, quindi per gcd(9, 26) = 1 otteniamo (-1, 3).