# Euclidean Algorithm to gind GCD in C++

• November 23rd, 2005, 07:23 AM
pi><boy
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?
• November 23rd, 2005, 03:06 PM
Noia
Euclidean algorithms is fairly straight forward, theres an entery on it in wikipedia I belive....theres always google aswell.
• November 23rd, 2005, 04:11 PM
mathgirl32
You could write a recursive function to find your gcd.
• November 23rd, 2005, 04:33 PM
Noia
Code:

```public int gcd(int a, int b) {     if b == 0 return a;     else return gcd(b, a % b); }```
Something like that?