在 C++ 中使用 Shanks Tonelli 算法在模 p 下查找平方根

引言

在数论和模算术领域中，在模素数下寻找平方根的问题非常重要，尤其是在密码学和数论应用中。Shanks Tonelli 算法提供了一种高效的方法来计算模素数的平方根。

语法

它具有以下语法：

参数

• a：它是需要找到模 p 下平方根的基值。
• p：素数模。

示例 1

让我们举一个例子来说明如何在 C++ 中找到模 p 下的平方根。

输出

Enter the value of a (base): 3
Enter the value of p (prime modulo): 17
Square root of 3 modulo 17 is: 6

说明

• 在这个例子中，a 模 p 的勒让德符号是使用 legendreSymbol 函数计算的。模幂运算用于将 a 模 p 提升到 (p - 1) / 2 的幂。如果结果是 -1，它返回 -1 值；否则，它提供计算出的勒让德符号。
• 模幂运算函数计算基数提高到指数模 mod 的幂的模幂运算。它通过迭代指数的二进制形式并应用模算术来快速计算结果。
• shanksTonelli 函数：它是 Shanks Tonelli 算法的实现。首先，它确定 q 和 s 的值，使得 p - 1 = q * (2^s)。之后，它检查 s 是否等于 1。如果是，它直接使用模幂运算计算模 p 的平方根。否则，它找到一个非二次剩余 z 模 p，然后继续执行算法的主要步骤以计算模 p 的平方根。
• main 函数：此函数从用户读取输入值 a（基数）和 p（素数模）。之后，它检查 a 模 p 的勒让德符号是否等于 1。如果不是，它会打印一条消息，指示模 p 的平方根不存在。否则，它使用 shanksTonelli 函数计算模 p 的平方根并打印结果。

示例 2

让我们再举一个例子来说明 C++ 中的模算术。

输出

Square root of 5 modulo 11 is: 4

说明

1. 勒让德符号计算：在此示例中，评估勒让德符号以检查模素数 p 是否存在平方根。
2. 模幂运算：有效地实现模幂运算以在幂运算期间处理大数。
3. 算法初始化：确定 s 的值并找到合适的二次非剩余 z。
4. 初始计算：根据给定输入值和先前确定的参数计算 c、r 和 t。
5. 迭代：通过循环迭代以调整值并找到模 p 的平方根。
6. 结果检索：在完成迭代过程后获取模 p 的平方根。如果存在平方根，则返回结果；否则，指示其不存在。

实际应用

模算术的几个实际应用如下：

• 密码学：密码学使用模算术作为各种加密和解密方法的主要操作。模运算是 RSA 编码和签名方案中的主要数值变量之一。Shanks Tonelli 算法在密码协议中的实现有助于提高其高效率和安全通信，使数据免受任何其他偏差的影响。
• 错误检测和纠正：错误检测和纠正码经常使用有限域的特性，这些有限域是使用模算术创建的数字表示。如果在模素数下取平方根，算法可以验证接收到的数据没有错误并确保其正确传输，这在通信系统和存储设备中尤其如此。
• 数字信号处理：模运算算法（DSP）需要使用整数重新编码。在 DSP 算法中将平方根用作素数的模，这样可以减少处理时间，因此可以应用于改进各种音频和图像处理技术。
• 有限元分析：有限元分析 (FEA) 通常用于工程和科学模拟中，通过结合复杂的磷灰石成功分析各种系统。FEA 倾向于涉及求解大型线性方程组的操作；因此，在此阶段可以执行模算术。在素数模中高效的平方根运算会带来更精确和更快的 FEA，从而改进工程决策和优化。
• 数论研究：Shank-Tonelli 算法被认为是最近数论技术发展的基础，用于有效解决模算术问题。二次剩余、丢番图方程和椭圆曲线研究的参与者使用 Shanks Tonelli 等算法来探索更深层次的数学问题并揭示创新的密码方法。

结论

Shanks Tonelli 算法提供了一种计算模素数平方根的高效方法。该算法在模算术发挥关键作用的密码学应用中特别有用。通过利用勒让德符号和模幂运算，我们可以以合理的计算复杂度找到模 p 的平方根。所提供的 C++ 实现可以进一步优化并集成到需要模算术计算的各种应用程序中。