# Congruences and All That

The goal of this handout is to show you how to solve congruences of the form ax mod n = 1. You can use this to compute the private key during the initialization of an RSA cryptosystem.

### Solving ax mod n = 1 when gcd(a, n) = 1.

Use Euclid's extended GCD algorithm to compute x. The algorithm, in Pascal, is:

begin		(* compute x such that ax mod n = 1, where 0 < a < n *)
g[0] := n; g[1]:= a; u[0] := 1; v[0] := 0; u[1] := 0; v[1] := 1; i := 1;
while g[i] <> 0  do begin
(* loop invariant: g[i] = u[i] * n + v[i] * a *)
y[i] := g[i-1] div g[i];
g[i+1] := g[i-1] - y[i] * g[i];
u[i+1] := u[i-1] - y[i] * u[i];
v[i+1] := v[i-1] - y[i] * v[i];
i := i + 1;
end;
x := v[i-1];
if x < 0 then
x := x + n;
end.
For example, to solve 3x mod 7 = 1, calculate as follows:
ig[i]u[i]v[i]yu[i]*n+v[i]*a
07101*7+0*3=7
130120*7+1*3=3
211-231*7+(-2)*3=1
30(-3)*7+7*3=0
Hence, x = -2 + 7 = 5.

### First Congruence

In the first example of an RSA cipher, we chose p = 5 and q = 7. This means n = pq = 35, and PHI(n) = (5-1)(7-1) = 24. We must find d and e such that de mod PHI(n) = 1. We chose d = 11 and need to determine e. As gcd(11, 24) = 1, we can use the above algorithm to solve 11e mod 24 = 1:
ig[i]u[i]v[i]yu[i]*n+v[i]*a
024101*24+0*11=24
1110120*24+1*11=11
221-251*24+(-2)*11=2
31-5112(-5)*24+11*11=1
40
Hence, e = 11.

### Second Congruence

In the second example, we chose p = 53 and q = 61. This means n = pq = 3233, and PHI(n) = (53-1)(61-1) = 3120. We must find d and e such that de mod PHI(n) = 1. We chose d = 791 and need to determine e. As gcd(791, 3120) = 1, we can use the above algorithm to solve 791e mod 3120 = 1:
ig[i]u[i]v[i]yu[i]*n+v[i]*a
03120101*3120+0*791=3120
17910130*3120+1*791=791
27471-311*3120+(-3)*791=747
344-1416(-1)*3120+4*791=44
44317-67117*3120+(-67)*791=43
51-187143(-18)*3120+71*791=1
60
Hence, e = 71.

You can also see this document in its native format, in Postscript, in PDF, or in ASCII text.
Send email to cs153@csif.cs.ucdavis.edu.

Department of Computer Science
University of California at Davis
Davis, CA 95616-8562