Really simple question regarding the Affine Cipher.
Can someone tell me how $3^{-1}$ is supposed to result in 9 in the following explanation below?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ 27 ≣ 1 (mod 26) and 3*9 = 27. Gotta pay attention to the modulus. $\endgroup$– ChibNov 6, 2016 at 3:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
If you want to find the multiplicative inverse of an integer a (mod n) you can use the extended Euclidean algorithm. For two integers a and b, the Extendend Euclidean Algorithm not only calculate the greatest common divisor d but also two integers x and y that satisfy the following equation:
ax + by = d = gcd(a,b) (where gcd is the greatest common divisor)
So if a and b are relatively prime (gcd(a,b)=1), x is the multiplicative inverse of a (mod y), and y is the multiplicative inverse of b (mod x).
Wikipedia seems to provide a good explanation of the algorithm
Hope I was helpful!
-
$\begingroup$ The wikipedia article regarding "Modular multiplicative inverse" helped me to bring some light into the topic - the Euclidean algorithm will be covered later in the book. Thanks anway! $\endgroup$ Mar 10, 2016 at 15:47
-
$\begingroup$ Good!! I thought you wanted to find the multiplicative inverse of an integer (mod n). Was I wrong? $\endgroup$– ssh3llMar 10, 2016 at 17:51