Affine Cipher: what to do if the number isnt invertible over mod n? I am currently solving a simple cryptanalysis problem where I need to decrypt a text file using frequency analysis. The text has been encrypted using an affine cipher over a 68 character alphabet which includes lower and upper case English letters, digits from 0 to 1, as well as those characters: &quot;. , ; : _ \n&quot; where _ denotes space.
Going over the frequency histogram of the text, the most frequent character is &quot;,&quot; followed by &quot;z&quot;. According to what I know, the most frequent character for the 68 character alphabet is space followed by &quot;e&quot;.
Thus I end up with those two equations:
$$66a + b = 63 \bmod 68$$
$$4a + b = 25 \bmod 68$$
Which gives me:
$$62a = 38 \bmod 68$$
$a = 38 \cdot 62^{-1}  \bmod 68$
However, 62 isn't invertible mod 68. I am quite new to cryptography so I am quite unsure if there is some method to solve this issue.
If you divide the whole equation throughly 2 you get
$$31a\equiv 19\pmod {34}$$
which you can solve to get $a\equiv 5\pmod{34}$. This then gives two possibilities for $a\pmod {68}$: either 5 or 39. For these two possibilities you can then find the corresponding $b$ (it turns out to be 5 in both cases) and check which solution works.