用c++实现模重复平方法和平方乘算法

发表于 | 分类于

用c++实现模重复平方法和平方乘算法

代码如下：

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

//模重复平方法

int mopin_57(int a, int b, int c)
{
    int s(1);
    bitset<16> d(b);    //将幂转换为二进制
    /* 另一种写法
    while (b)
    {
        if (b & 1)
        {
            s = (s * a) % c;
        }
        a = (a * a) % c;
        b = b >> 1;
    }
    */
    for (int i =0; i < d.size(); i++)
    {
        if (d[i] == 1)
            s = (s * a) % c;
        a = (a * a) % c;
    }
    return s;
}

​
​ //平方乘方法
​ int pingfang_57(int a,int b,int c)
​ {
​ int m(1);
​ int n(0);
​ bitset<16> d(b);
​ for (int i =d.size() - 1; i >= 0 ; i–)
​ {
​ n = 2 * n;
​ m = (m * m) % c;
​ if (d[i] == 1)
​ {
​ n++;
​ m = (m * a) % c;
​ }
​
}
return m;
}

int main()
{
    int a = 7;
    int m = 22;
    int n = 31;
    cout << "第一组测试值：a=" << a << " m=" << m << " n=" << n << endl;
    cout << "模平方重复法的到的结果：" << mopin_57(a, m, n) << endl;
    cout << "平方乘方法得到的结果：" << pingfang_57(a, m, n) << endl;

    a = 501;
    m = 13;
    n = 667;
    cout << "第一组测试值：a=" << a << " m=" << m << " n=" << n << endl;
    cout << "模平方重复法的到的结果：" << mopin_57(a, m, n) << endl;
    cout << "平方乘方法得到的结果：" << pingfang_57(a, m, n) << endl;

    a = 501;
    m = 57;
    n = 2157;
    cout << "第一组测试值：a=" << a << " m=" << m << " n=" << n << endl;
    cout << "模平方重复法的到的结果：" << mopin_57(a, m, n) << endl;
    cout << "平方乘方法得到的结果：" << pingfang_57(a, m, n) << endl;


    return 0;
}

运行结果：

alt