# How to programmatically find the inverse of a 2x2 matrix (mod 26).

I'm trying to create a hill cipher utility. One feature I want is to be able to compute the key if you have the plaintext and ciphertext.

$C$ = ciphertext matrix ($2\times 2$), $P$ = plaintext matrix $\left(2\times\frac{N}{2}\right)$, $K$ = key ($2\times 2$).

$$PK = C$$

So if I have $C$ and $P$, then $K = P^{-1}C$. How do I best find $P^{-1}$?

EDIT: It is important to note that this is all mod $26$. Sorry.

-

1
– Douglas S. Stones Oct 5 '12 at 2:16

## 1 Answer

You could use the direct formula for $2 \times 2$:

$$\pmatrix{a & b\\ c & d}^{-1} = \dfrac{1}{ad-bc}\pmatrix{d & -b\\-c & a}$$

-
The problem is that doesn't work out in with the modular. I don't know how to format this nicely, sorry. but lets say our plaintext is b,a,z,z. {{b,a}, {z,z}} = {{1,0}, {25,25}} then if we try multiplying by 1/(ad-ab) we get a fraction. That doesn't work when you are working with only discrete values. Sorry if I was not clear enough. – Alan Oct 5 '12 at 1:55

1
Yes, it would have to be the modular inverse, the extended gcd algorithm would be one way to do it. In your example, 25 is its own inverse, another example is $3^{-1} \equiv 9 (mod 26)$ since $3 \times 9 = 27 \equiv 1 (mod 26)$ – adam W Oct 5 '12 at 2:09
Okay, I think I got it. So {{1,0},{25,25}}^(-1) actually works out to {{1,0},{25,25}}, right? – Alan Oct 5 '12 at 2:15
Yes! Also, consider that $2$ and $13$ and any multiples (basically just even numbers and the number $13$) do not have modular inverses. – adam W Oct 5 '12 at 2:19
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 17, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9336446523666382, "perplexity_flag": "middle"}