How can u explain this. With the Euclidean algorithm we finally have an efficient algorithm for finding the multiplicative inverse in Zm that is much better than exhaustive search. Find the inverses in Zm of the following elements a modulo m: a = 7, m = 26 (affine cipher) Thanx
Here's an easier way. Take 11/26 and write out the continued fraction representation, = [2, 2, 1, 3]. Underneath write the convergents = [1/2, 2/5, 2/7, 11/26]. From the rightmost denominator (26), subtract the denominator to the left (7), giving 19, the answer. This rule applies to an even number of partial quotients (we have 4). For an odd number, we just record the denominator to the left of the rightmost denominator. Say we want the multiplicative inverse of 5 mod 21. We get [4, 4, 1] and underneath our convergents are [1/4, 4/17, 5/21]. Denominator to the left of the 21 is 17, the answer since 5 * 17 = 85 = 1 mod 21; (correct).
when mapping a number to the english alphabet there are 26 possibilities and the reason we use mod 26 is to get the specific position of the corresponding letter no matter how many times it loops. So -7 is basically just going backwards seven letters from "z". Since we can't have negative numbers we make it 19 which will be equal to the same letter as -7.
if you add 26 to -7 you'll get 19. For smaller numbers, it is easy to reduce via the mod because you can add or subtract until you're within the range of 1 to 26
