c++实现模重复平方法

模重复平方法（Montgomery modular multiplication）是一种高效的计算模数下乘法的方法，它可以用于提高RSA算法等密码算法的性能。

以下是C++实现模重复平方法的代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

typedef long long ll;

ll mod;

ll mul_mod(ll a, ll b) {
    ll res = 0;
    while (b) {
        if (b & 1) res = (res + a) % mod;
        a = (a << 1) % mod;
        b >>= 1;
    }
    return res;
}

ll power_mod(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = mul_mod(res, a);
        a = mul_mod(a, a);
        b >>= 1;
    }
    return res;
}

ll get_r() {
    ll r = 1;
    while (r < mod) r <<= 1;
    return r;
}

ll get_inv(ll a) {
    return power_mod(a, mod - 2);
}

ll montgomery_mul(ll a, ll b, ll r_inv) {
    ll t = a * b;
    ll m = t * r_inv % mod;
    ll u = (t + m * mod) / mod;
    if (u >= mod) u -= mod;
    return u;
}

ll montgomery_pow(ll a, ll b) {
    ll r = get_r();
    ll r_inv = get_inv(r);
    ll t = mul_mod(a, r) % mod;
    ll ans = r % mod;
    while (b) {
        if (b & 1) ans = montgomery_mul(ans, t, r_inv);
        t = montgomery_mul(t, t, r_inv);
        b >>= 1;
    }
    ans = montgomery_mul(ans, 1, r_inv);
    return ans;
}

int main() {
    ll a, b;
    cin >> a >> b >> mod;
    cout << montgomery_pow(a, b) << endl;
    return 0;
}

其中，mul_mod函数实现了模数下的乘法，power_mod函数实现了模数下的快速幂，get_r函数用于计算r参数，get_inv函数计算a关于模数的逆元，montgomery_mul函数实现了Montgomery模乘，montgomery_pow函数实现了Montgomery模指数运算。