Solving a Single Congruence Equation

[Thomas Klemm]

(04-15-2014 11:31 PM)Han Wrote:  In keeping the algorithm fairly simple

Euklid's algorithm to calculate the greatest common divisor isn't that complicated. You just keep track of the multiples of A and N.
([u v] is short for: u*N + v*A)

Example:
5 * x = 3 mod 17

Calculate gcd(17, 5):
[1 0] 17
[0 1] 5
[1 -3] 2 = 17 - 3 * 5
[-2 7] 1 = 5 - 2 * 2

Thus gcd(17, 5) = 1 = -2 * 17 + 7 * 5
Therefore:
5 * 7 = 1 mod 17
5 * 7 * 3 = 3 mod 17
5 * 21 = 3 mod 17
5 * 4 = 3 mod 17

Cheers
Thomas

PS: You can ignore u. Just keep track of v.