Extended Euclidean Algorithm

If you like a challenge, try to find an equivalent algorithm yourself instead of simply using this one. That is essentially Problem 7.31 in the textbook. The recursive form is easier to find and can be flattened out'' into an iterative form quite easily.

Input: positive integers and .

Output: integers and such that .

This algorithm is often used to compute the inverse of number modulo number (i.e., computes such that ). This works if and only if , otherwise does not have an inverse modulo . For more hints, see book Problem 7.31 or Prof. Paar's script.


ext_euclid(int a, int b)
x:=1; v:=1; y:=0; u:=0;
do
q := a div b; // integer division
r := a mod b;
a := b; b := r; // this is the standard Euclid
x_tmp := x; y_tmp :=y;
x := u; y := v;
u := x_tmp-q*u; v := y_tmp - q*v;
while (b>0);
return x,y


Example:

which means:

Hint: For RSA, represents the component in , therefore it must be positive to be used as an exponent in decryption. If the algorithm produces a negative number for , as in this example, just add , since everything is modulo . In this example, the returned is which modulo 60 is equivalent to .

So in arithmetics modulo 60 (for RSA, that could be , so ), if you choose as your public key, the private key is . is the only number less than that, multiplied with modulo , is 1. Convince yourself that this is true. Therefore, by our theorems, for all , so and .