C++ 中的 Solovay Strassen 素性检验法

Solovay-Strassen 素性测试 是一种概率算法，用于确定给定数字是素数还是合数。与确定性方法（如埃拉托斯特尼筛法）不同，埃拉托斯特尼筛法可以保证素性，但对于大数来说计算成本很高。Solovay-Strassen 在效率和准确性之间取得了平衡。

该算法的核心是利用欧拉判别准则和雅可比符号来评估给定整数 n 是否为素数。欧拉判别准则指出，对于一个奇素数 p 和一个整数 a，a 是模 p 的二次剩余当且仅当 a^((p-1)/2) ≡1(mod p)。雅可比符号是勒让德符号的扩展，有助于确定一个整数是否是模奇素数的二次剩余。

在 Solovay-Strassen 方法中，对于给定的奇整数 n，该算法选择随机整数 a 并计算两个值：雅可比符号 x=(a/n) 和 y= a^((n-1)/2) mod n。如果 n 是素数，那么对于许多随机 a，x 和 y 将相等。但是，如果 n 是合数，那么 x 不等于 y 的可能性很高。

通过以预定次数重复此过程并每次选择不同的随机数，Solovay-Strassen 测试 提供了素性的概率评估。迭代次数直接影响测试的准确性，迭代次数越多，素性判断的信心就越大。

用 C++ 实现的 Solovay-Strassen 算法 提供了一个多功能的素性测试工具，尤其适用于概率方法可接受且计算效率至关重要的场景。虽然它偶尔会将合数错误分类为素数（假阳性），但它高效处理大数的能力使其成为素性测试算法库中宝贵的补充。

程序

输出

5 is prime
19 is prime

说明

模函数： 模函数使用二进制幂运算高效计算模幂运算。它计算 (base^exponent) % mod 以防止溢出。

雅可比符号计算： calculateJacobian 函数 计算数字 a 关于 n 的雅可比符号，这表示 a 是否是模 n 的二次剩余。

Solovay-Strassen 素性测试： solovoyStrassen 函数执行实际的素性测试。它将 p 和迭代次数作为输入。在每次迭代中，它选择一个介于 1 和 p-1 之间的随机数 a。然后它计算 a 关于 p 的雅可比符号以及 a 的 (p-1)/2 次方模 p 的模幂运算。如果雅可比符号为零或模幂运算不等于雅可比符号，则 p 被认为是合数。如果所有迭代都满足此条件，则 p 可能是素数。

主函数： 在主函数中，代码使用 Solovay-Strassen 测试对两个数字 num1 和 num2 进行测试，并指定了预定的迭代次数。根据测试结果，它会打印每个数字是素数还是合数。

最后，Solovay-Strassen 算法利用雅可比符号和模幂运算的属性来提供素性的概率确定。虽然它能以高概率识别合数，但它偶尔会将素数误分类为合数，因此适用于可接受概率结果的应用。调整迭代次数会影响测试的准确性，迭代次数越多，结果的置信度越高，但计算时间也越长。

复杂度分析

时间复杂度

影响时间复杂度的主要因素是 Solovay-Strassen 测试中的迭代次数 (k)。该算法在每次迭代中执行模幂运算，其时间复杂度为 O(log n)，其中 n 是模数。

因此，总体时间复杂度为 O(k * log n)。

空间复杂度

空间复杂度主要取决于输入数字的存储以及计算中使用的临时变量所需的空间。

对于存储输入数字 a 和 n，以及像幂运算结果和雅可比符号这样的临时变量，空间复杂度为 O(1) 或常数，因为所需空间不随输入大小增加。

但是，如果输入数字由于其大小较大而使用任意精度算术表示，则空间复杂度将取决于此类算术运算的实现，通常范围从 O(log n) 到 O(n)，其中 n 是输入中的位数。