0

我有一个程序使用模幂计算 7^644 mod 645, 11^644 mod 645, 3^2003 mod 99, 123^1001 mod 101。我遵循 Modular Exponentiation 的规则，然后当我编译时我的结果是错误的，输出的结果应该是 436,1,22,27，但我的输出很差。当我运行时，我的答案是 643、655、20、39

这是我的代码：

int Modulo(int b, int e, int m)
{

int remainder;//set the remainder of the procedure
int x = 1;// modular initially sets x = 1

//while loop to request the multiplication
while ( e != 0)
{

    remainder = e % 2;
    e = e/2;

    //Algorithm steps
    if(remainder == 1)//if remainder = 1 
    x = ( x * b) % m;//then x = (x · power) % m
    b = ( b * b) % m;//power = (power * power) % m

}
return x;


}
int main()
 {

  int b, e, m, modulo;//declares the variables 
  start:cout<<"Enter the base: ";//output for base
  cin>>b;

  cout<<"Enter the exponent: ";//output for exponent
  cin>>e;

  cout<<"Enter the number of modular: ";//output for mod
  cin>>m;

  modulo = b^e % m;//requesting the formula of Modular Exponentiation
  cout<<"The answer is \n"<<modulo<<endl;
  cin.get();
  // I create if statement to allow the user to restart the application 
//enter new value to see the different output
    char c;
    cout<<"Would you like to enter a new value? yes or no ";
    cin>> c;
    if(( c == 'Y') ||(c == 'y'))goto start ;//start is the label in the start of program
  return 0;
 }
4

1 回答 1

0

对于它的价值，我会编写类似这样的代码（至少对于我尝试过的值进行测试并产生正确的结果）：

unsigned Modulo(unsigned b, unsigned e, unsigned m) {
    unsigned x = 1;

    while (e > 0) {
        if (e & 1)
            x = x * b % m;
        e >>= 1;
        b = b * b % m;
    }
    return x;
}

请注意，我已尝试使用与您的代码相同的名称——尽管它们中的许多并没有让我觉得是最好的（甚至是非常好的）选择。Modulo在我看来，这是一个特别糟糕的名字。我更喜欢这样的东西pow_mod，至少暗示它在做什么（这在哪里Modulo是完全误导的）。

于 2013-02-16T07:18:53.003 回答