*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 .