0

Modular Exponentiation を使用して 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 に答える