Hope you can help me; I have the following code:

#include <iostream>
#include <math.h>

using namespace std;

long int
cifra (long int b, long int e, long int n)
{
  /* Calcula a tal que (b^e)=a MOD n. Algoritmo 3.1 de Allenby & Redfern,1989. */
  long int a, i, q, r;

  a = 1;
  q = b / n;
  r = b - q * n;
  for (i = 1; i <= e; i  )
    {
      a = a * r;
      q = a / n;
      a = a - q * n;        /* ou, de forma equivalente, a=mod(a,n) */
    }
  return a;
}

int
main ()
{

  long int a, b, e, n;

  b = 116104101;
  e = 19661;
  n = 383768051;

  a = cifra (b, e, n);

  cout << "a=" << a << endl;

  return 0;
}

and this should output

a=199324862

as it does when I used the online C Compiler (https://www.onlinegdb.com/online_c _compiler, which uses g ).

However: if I run it on Code::Blocks with MinGW64 (on Windows 10), I get the wrong result:

a=298405922

Any ideas? Am I doing anything wrong?

CodePudding user response：

It seems that you're assuming that long int is a 64-bit (or larger) integer type, but it's actually a 32-bit type in that particular environment. If you need a certain size type you should use something more explicit like int64_t or uint64_t. Also, you might want to use the remainder operator % to avoid the q variable altogether, e.g. r = b % n or just b %= n:

#include <iostream>
#include <cstdint>

int64_t cifra(int64_t b, int64_t e, int64_t n) {
    /* Calcula a tal que (b^e)=a MOD n. Algoritmo 3.1 de Allenby & Redfern,1989. */
    int64_t a, i;

    a = 1;
    b %= n;
    for (i = 1; i <= e; i  ) {
        a = (a * b) % n;  /* ou, de forma equivalente, a=mod(a,n) */
    }
    return a;
}

int main() {

    int64_t a, b, e, n;

    b = 116104101;
    e = 19661;
    n = 383768051;

    a = cifra(b, e, n);

    std::cout << "a=" << a << std::endl;
    return 0;
}

CodePudding user response：

Overflow

q * n, a * r, q * n risk overflow.

The width of long is at least 32-bit, yet a full range multiplication obliges 2x long width for the product.

Either:

1. Use a wider type for intermediate results. long long would suffice for OP's test case of b = 116104101; e = 19661; n = 383768051;

or

2. Perform the math more carefully. Example: Modular exponentiation without range restriction.

int64_t cifra(int64_t b, int64_t e, int64_t n) incorrect with some small corner cases. cifra(b, 0, 1) returns 1 when it should return 0.

// a = 1;
a = n ? 1 : 0;
// or 
a = !!n;
// or 
a = 1%n;
// or ...