I need to find the inverse for 491 mod 784?

Question

these questions come up often in my cryptography module an eam in which i have to take soon. I know that its inverse is that number raised to the power of the number of integers less than 784 coprime with 784 minus 1. However this invloves factorising large numbers, 784 is easy as its a square but is there an easier (quicker) method as time is a factor

Answer 1

All you have to do is use the Euclidean algorithm on 784 and 491, with the reason being you want to solve y such that

784x + 491y = 1

784 = (1)(491) + 293
491 = (1)(293) + 198
293 = (1)(198) + 95
198 = (2)(95) + 8
95 = (11)(8) + 7
8 = (1)(7) + 1

Now that you've reached 1, you work backwards from the Euclidean algorithm.

1 = 8 + (-1)7

Substitute in what you get for 7 (from the second last equation),

1 = 8 + (-1)[95 + (-11)(8)]

Distributing the (-1) while preserving the 8,
1 = 8 + (-1)(5) + (11)(8)

And now we can group together like terms; 8 + (11)8 is like adding x + 11x.

1 = (-1)(95) + (12)(8)

We essentially repeat this process with repeated substitutions.

1 = (-1)(95) + 12[198 + (-2)95]
1 = (-1)(95) + 12(198) + (-24)(95)
1 = 12(198) + (-25)(95)
1 = 12(198) + (-25)[293 + (-1)(198)]
1 = 12(198) + (-25)(293) + (25)(198)
1 = (-25)(293) + (37)(198)
1 = (-25)(293) + (37)[491 + (-1)(293)]
1 = (-25)(293) + (37)(491) + (-37)(293)
1 = (37)(491) + (-62)(293)
1 = (37)(491) + (-62) [784 + (-1)(491)]
1 = (37)(491) + (-62)(784) + (62)(491)
1 = 99(491) + (-62)(784)

Remember how we originally wanted to solve y here:
784x + 491y = 1

Now that we have 99(491) + (-62)(784) = 1, we can rearrange that to

784(-62) + 99(491) = 1

Now that if we compare the two equations, we can pair the x with (-62) and the y to 99. It then follows that the inverse of 491 (mod 784) is equal to 99 (mod 784).

Let's check:

491 * 99 = 48609 (mod 784), and
48609/784 is 62 remainder 1, therefore we are correct (as we want the remainder when doing modulo arithmetic).