密码学c++实现最大公约数算法和快速模幂算法

### C++ 中的最大公约数算法

在C++标准库中，求最大公约数的函数是 `__gcd(a, b)`，可以用于计算两个整数的最大公约数[^2]。

除了使用内置函数外，也可以通过辗转相除法（也称为欧几里得算法）来手动实现最大公约数的计算：

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

这段代码利用了递归来不断减少较大的数值直到找到两者的公共因子为止。当`b`等于零时返回`a`作为结果，这是因为任何非零整数与零之间的最大公因数就是该非零整数本身。

### 快速模幂算法及其密码学应用

快速模幂算法广泛应用于现代密码体系之中，比如RSA加密算法就依赖于这一技术来进行加解密操作。以下是基于二进制指数平方乘方法的一种高效实现方式：

long long mod_exp(long long base, long long exp, long long modulus) {
    long long result = 1;
    while (exp > 0) {
        if (exp & 1) { // 如果当前位为1，则累乘base并取模
            result = (result * base) % modulus;
        }
        exp >>= 1;     // 右移一位相当于除以2
        base = (base * base) % modulus; // 平方基数并取模
    }
    return result;
}

此版本实现了对给定底数`base`、指数`exp`以及模数`modulus`三者之间执行快速模幂运算的功能。它采用了迭代而非递归的方式，在每次循环体内判断最低有效位是否为1，并据此决定是否更新临时变量`result`；接着无论条件成立与否都会继续处理剩下的高位直至完成整个过程。

上述两种算法均适用于各种场景下的密码学需求，特别是涉及到大量数据的安全传输保护方面表现尤为突出。