c++实现Tonelli–Shanks算法

Tonelli-Shanks算法是一种用于因式分解大整数的高效算法，主要用于寻找一个合数的非平凡小素因子。该算法基于威尔逊定理和二次剩余理论，对于形如\( x^2 \equiv -d \pmod{p}\)（其中\( p \)是质数，\( d \)是小于\( p \)的一半且互质于\( p\)的正整数）的同余方程，可以有效地找到解。

以下是C++实现Tonelli-Shanks算法的基本步骤：

1. **检验质数**：
首先需要确认输入的数字是质数，并且不是\( 2 \)或\( 3 \)，因为\( 2 \)和\( 3 \)有特殊处理方法。

2. **选择初始\( a \)和\( s \)**：
从\( a = 2 \)开始，设\( s = 0 \)，同时计算\( a^{(p-1)/2} \mod p\)。如果结果为1，则\( p-1 \)是\( 2 \times q \)的形式（\( q \)也是质数），直接返回\( q \)。

3. **循环查找**：
如果不是上述情况，继续循环，将\( a \leftarrow a^2 \mod p \)，同时递增\( s \)直到\( a \not\equiv 1 \mod p \)或\( s \geq (p-1)/4 \)。这时\( a \)会形成一个周期循环，寻找这个循环中的最小指数\( r \)满足\( a^{r+1} \equiv a^r \mod p \)。

4. **检查是否成功**：
计算\( y = a^((p-1)/q) \mod p \)。如果\( y \neq 1 \)且\( y \neq p-1 \)，则\( p-y \)就是我们需要的一个非平凡小素因子。

下面是伪代码形式的示例：

int TonelliShanks(int n) {
    if (isPrime(n) && n != 2 && n != 3) {
        int a = 2;
        int s = 0;
        while (a * a % n == 1) {
            a *= a;
            ++s;
        }
        int q = n - 1 >> s;
        int y = pow(a, q, n);
        if (y != 1 && y != n - 1) {
            return n - y;
        } else {
            return -1; // 没有找到素因子
        }
    } else {
        return -1; // 输入不是一个有效的质数
    }
}