2.2 Extended Euclidean Algorithm

The Extended Euclidean Algorithm determines, if present, the inverse of b modulo n:

1.	b0 = b
2.	n0 = n
3.	t0 = 0
4.	t = 1
5.	q = n0 / b0 (rounded off)
6.	r = n0 - q * b0
7.	while r > 0 do
8.		temp = t0 - q * t
9.		if temp >= 0 then temp = temp mod n
10.		if temp < 0 then temp = n - (( -temp) mod n)
11.		t0 = t
12.		t = temp
13.		n0 = b0
14.		b0 = r
15.		q = n0 / b0 (abgerundet)
16.		r = n0 - q * b0
17.	if b0 != 1 then
		b has no inverse modulo n
	else
		b-1 = t mod n

source

2.3 Large Primes