pointers

[codetojoy]

need to write 3 functions: 1)main 2)int mod_test(int a, int e, int n)
3)void mod_test(int a, int x, int b, int y, int n, int *out1, int *out2)*out1 here means output, so there are 2 outputs; these functions simply attempt to solve the issue of overflow; not sure how to implement 3) which declares 2 pointers as parameters: should I use nested while loops; just not sure!! Below is the code for 2):

int mod_test(int a, int e, int n) //a to the e mod n: a^e mod n
{
     int i = 0;
     int result = 1;
     while(i < e)
     {
         result = result * (a % n);
         i++;
      }
         return  result;
}
  

[Naughty Albatross]

Hi,
According to the algorithm a^e, what you are doing to calculate (result) is wrong.

You forgot to do mod operation before your function returns.

However, it is unclear what test your mod_test() func actually conducts just by looking at your quick description.

int mod_test(int a, int e, int n) // a to the e mod n: a^e mod n 
{
     int i = 1;
     int result = a; 
     while(i < e)
     {
         result *= a;
         i++;
      }
      return (result % n);
}

[Naughty Albatross]

Better yet, you can also solve this with only a single line (remember to include math.h)

int mod_test(int a, int e, int n)
{
  return ((int)std:: pow(a, e) % n);
}

[Naughty Albatross]

Does this help you? :)

[cire]

If the idea is to find a^e mod n without overflow affecting the results, the implementation of (2) should look something like this:

int mod_test(int a, int e, int n) //a to the e mod n: a^e mod n
{
    int result = a;
 
   for (int i=1; i<e; ++i) 
        result = (result * a) % n;    // prevent overflow
    
   return result;
}

Note that neither the code in the OP nor that by the poorly named person above is correct with regard to preventing overflow.

You didn't provide the requirements for the function (3) you were unsure how to write, and it isn't immediately obvious what it should do, so it's difficult to give you cogent advice.

[Naughty Albatross]

@cire
Well spotted. Thanks for pointing my mistake out.

@codetojoy
Is your equation a^e mod n something like this : 6⁴ mod 5?

Even better yet, change your integer variables to long long or __int64 to make your program more resistant against overflow-based attacks.

long long mod_test(long long a, long long e, long long n) 
{
     long long i = 1;
     long long result = a; 
     while(i < e)
     {
         result *= a;
         i++;
      }
      return (result % n);
}

[48T7M4Gy]

http://www.cplusplus.com/forum/general/194026/