Results 1 to 6 of 6

Thread: Euclidean Algorithm to gind GCD in C++

  1. #1

    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?

  2. #2
    Now, RFC Compliant! Noia's Avatar
    Join Date
    Jan 2002
    Posts
    1,210
    Euclidean algorithms is fairly straight forward, theres an entery on it in wikipedia I belive....theres always google aswell.
    With all the subtlety of an artillery barrage / Follow blindly, for the true path is sketchy at best. .:Bring OS X to x86!:.
    Og ingen kan minnast dei linne drag i dronningas andlet den fagre dag Då landet her kvilte i heilag fred og alle hadde kjærleik å elske med.

  3. #3
    () \/V |\| 3 |) |3\/ |\|3G47|\/3
    Join Date
    Sep 2002
    Posts
    744
    You could write a recursive function to find your gcd.

    Go Finland!
    Deviant Gallery

  4. #4
    Now, RFC Compliant! Noia's Avatar
    Join Date
    Jan 2002
    Posts
    1,210
    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 ==
    With all the subtlety of an artillery barrage / Follow blindly, for the true path is sketchy at best. .:Bring OS X to x86!:.
    Og ingen kan minnast dei linne drag i dronningas andlet den fagre dag Då landet her kvilte i heilag fred og alle hadde kjærleik å elske med.

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

    Thanks, for all the help

  6. #6
    Now, RFC Compliant! Noia's Avatar
    Join Date
    Jan 2002
    Posts
    1,210
    No worries, its not really that hard though :P

    ^^ 30 second jobbie
    With all the subtlety of an artillery barrage / Follow blindly, for the true path is sketchy at best. .:Bring OS X to x86!:.
    Og ingen kan minnast dei linne drag i dronningas andlet den fagre dag Då landet her kvilte i heilag fred og alle hadde kjærleik å elske med.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •