I'm trying to decrypt the ciphertext vczkh which I know was encoded using an affine cipher with the equation 7x + 8(mod 26). This makes my decryption function p = (c – b) * a^-1 (mod 26) where b = 8, a = 7, c = number corresponding with cipher character starting from 0, and p is the same for plaintext. Since I can't have a fraction I calculated that 11 is congruent to 7 making my function p = (c - 8) * 11. Running this for all five letters gives me NMFWP but I know the answer is supposed to be NOVEL. I do not know what I'm doing wrong.
Asked
Active
Viewed 828 times
1
-
"11 is congruent to 7"??? – Gerry Myerson Jan 28 '15 at 02:06
-
Is it not? 7 * 11 = 77 and 77 % 26 = 1. That means congruence right? – Nick Gilbert Jan 28 '15 at 02:07
-
"$a$ is congruent to $b$ modulo $c$" means $a-b$ is a multiple of $c$. Is $11-7$ a multiple of 26? – Gerry Myerson Jan 28 '15 at 02:09
-
77 divided by 26 leaves a remainder 1? – Gerry Myerson Jan 28 '15 at 02:09
-
Never mind it's 15 – Nick Gilbert Jan 28 '15 at 02:16
-
I know that, but do you understand why it's 15, and how to work out that it is 15? – Gerry Myerson Jan 28 '15 at 02:17
-
7 * 15 = 104. Since 4 * 26 = 105 that means that both 15 and 7 must equal 1 mod 26. Is that right? – Nick Gilbert Jan 28 '15 at 02:20
-
$7\times15=104$? $4\times26=105$?? 15 equals 1 mod 26??? 7 equals 1 mod 26???? – Gerry Myerson Jan 28 '15 at 02:23
-
I got that backwards, 7 X 15 = 105, 4 x 26 = 104, 15 * 7 = 1 mod 26. 105/104 = 1 mod 26. Now that I know I'm stupid can you explain why this is working – Nick Gilbert Jan 28 '15 at 02:35
-
You wanted $7^{-1}\bmod{26}$, which means you wanted $q$ such that $7q\equiv1\bmod{26}$, and as you now undeerstand, $q=15$ works in that congruence. So the only question I still have for you is, do you know how to come up with that 15? – Gerry Myerson Jan 28 '15 at 03:12
1 Answers
1
We have:
$$y = ax + b \pmod {26} = 7x + 8 \pmod {26}$$
The inverse operation is given by:
$$x = \dfrac 1a (y - b) \pmod {26} = \dfrac{1}{7}(y - 8) \pmod {26} = 15(y-8) \pmod{26}$$
We are looking for a modular inverse (see the discussion on the Extended Euclidean algorithm) and you were slightly off on that. Try it using this online calculator. You get:
$$\dfrac{1}{7} \pmod{26} = 7^{-1} \pmod{26} = 15 \pmod {26}$$
I think you can take it from here.
Amzoti
- 56,093