DEPARTMENT OF COMPUTER SCIENCE
|CPSC 467b: Cryptography and Computer Security||Handout #6|
|Professor M. J. Fischer||February 18, 2013|
Linear Congruence Equations
Let a,x Z* n. Recall that x is said to be an inverse of a modulo n if ax ≡ 1 (mod n). It is easily seen that the inverse, if it exists, is unique modulo n, for if ax ≡ 1 (mod n) and ay ≡ 1 (mod n), then x ≡ xay ≡ y (mod n). We denote this unique x, when it exists, by a-1 (mod n) (or simply a-1 when the modulus n is clear from context).Proof: Let a Z*n and consider the function fa(x) = ax mod n. fa is easily shown to be a one-one mapping from Z*n to Z*n. Hence, fa is also onto, so for some x Z*n, fa(x) = 1. Then ax ≡ 1 (mod n), so x = a-1 (mod n). __
We showed in class how to use the Extended Euclidian algorithm to efficiently compute a-1 (mod n) given a and n.
Here we consider the solvability of the more general linear congruence equation:
where a,b Z*n are constants, and x is a variable ranging over Z*n.
Theorem 2 Let a,b,n Z*n. Let d = gcd(a,n). If d∣b then ax ≡ b (mod n) has d solutions x0,…,xd-1, where
and = ()-1 (mod ()). If d ~ ∣ n, then ax ≡ b (mod n) has no solutions.
Now suppose d∣b. Since () and () are relatively prime, exists by Theorem 1. Multiplying both sides of (2) by a, we get
where now we are working over the integers. But = 1 + for some k by the definition of , so substituting for in (3) yields
The quantities in parentheses are both integers, so it follows immediately that axt ≡ b (mod n) and hence xt is a solution of (1).
It remains to show that the d solutions above are distinct modulo n. But this is obvious since x0 < x1 < … < xd-1 and xd-1 - x0 = (d - 1) < n. __