Euclidean Algorithm to gind GCD in C++

We are being taught RSA encryption in our school. The teacher told us to write a lame program in C++. It need not be ultra-strong 1024-bit encryption, just to make us familiar.

So, we need that GCD{ Φ(n), e} = 1

We were suggested to use the Euclidean algorithm by making the ratio of the two nos small and small until it can't be reduced further and at this stage, the least of the two becomes the GCD.

So, anyone has any idea how to convert it into C++ code?

Euclidean algorithms is fairly straight forward, theres an entery on it in wikipedia I belive....theres always google aswell.

You could write a recursive function to find your gcd.

Code:

---

public int gcd(int a, int b) {
    if b == 0 return a;
    else return gcd(b, a % b);
}

---

Something like that?

EDIT: Woops, had = instead of ==

Hey!! you got it
I was unable to figure out how to apply the modulo to a,b.

Thanks, for all the help :)

No worries, its not really that hard though :P

^^ 30 second jobbie