C++：实现模幂运算

我正在使用这个新的和改进的代码，我为了解决这个问题而进行了更正。C++：实现模幂运算

我使用模幂运算式来使用公式[a^k mod n]来得到我的答案，我必须做的工作中我需要在两个步骤中对它进行编码。

首先INTķ必须被转换成由0和1的列表的二进制表示ķ。其次，模幂必须使用a，n和K[]作为参数..

进行早些时候，我的代码是不正确的，并能纠正。

这个问题我现在面临的是，当我谷歌的在线计算器为5^3 % 13模幂，应该== 8

，我从我的代码得到的结果是5 我想了解是否有什么轻微我从代码中缺少或者我的数学错误？由于

#include <iostream> 
#include <vector> 
using namespace std; 

vector <int> BinaryK(int k); 
int ModularExpo(int a, vector <int> & k, int n); 

int main() 
{ 
    int a = 0; 
    int k = 0; 
    int n = 0; 

    cout << "a^k % n" << endl; 
    cout << "a = "; 
    cin >> a; 

    cout << "k = "; 
    cin >> k; 

    cout << "n = "; 
    cin >> n; 

    vector<int> B = BinaryK(k); 
    int result = ModularExpo(a, B, n); 
    cout << "a^k mod n == " << result << endl; 

    return 0; 
} 

// c == b^e % m 

vector<int> BinaryK(int k) 
{ 
    vector<int> K; //hint: make K a vector 
    int tmp = k; 
    while (tmp > 0) 
    { 
     K.push_back(tmp % 2); //hint: use pushback 
     tmp = tmp/2; 
    } 

    return K; 
} 

int ModularExpo(int a, vector<int> & K, int n) 
{ 
    if (n == 1) 
     return 0; 

    int b = 1; 
    if (K.size() == 0) 
     return b; 
    int A = a; 
    if (K[0] == 1) 
     b = a; 

    for (int i = 1; i < K.size() - 1; i++) 
    { 
     A = A * A % n; 
     if (K[i] == 1) 
      b = A*b % n; 
    } 
    return (b); 
}

来源

2017-03-08 Mark1247

参见[这]（http://stackoverflow.com/a/22703521/1708801） –

这里的[另一种实现方式（HTTP：//计算器.com/a/20114154/179910）你可以看看，如果你喜欢。 –

更改这一行：

for (int i = 1; i < K.size(); i++) // K.size() not K.size()-1

来源

2017-03-08 05:18:45 rcgldr

它没有改变任何东西，你能更具体吗？谢谢我不明白你的意思是改变那一行，但用“-1”导致它没有工作 – Mark1247

退出条件应该是'i rcgldr

C++：实现模幂运算

回答

相关问题