用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