algorithm - 将素数表示为两个平方和的最快算法是什么？

Question

我可以使用两个循环来检查两个小于p素数的整数的所有组合，但这非常低效。有没有更好的算法来解决这个问题？任何的想法？

哪里p mod 4 = 1。

谢谢，

Answer 1

您可以尝试使用Hermite-Serret算法。

您还可以在此 math.se 页面上找到一个很好的算法列表：https ://math.stackexchange.com/questions/5877/efficiently-finding-two-squares-which-sum-to-a-prime

特别参见 Robin Chapman 的回答：https ://math.stackexchange.com/questions/5877/efficiently-finding-two-squares-which-sum-to-a-prime/5883#5883

Answer 2

您不需要搜索所有组合。一个简单的幼稚实现的粗略轮廓是：

• 考虑 [1..trunc(sqrt(p))] 范围内的每个整数 i。
• 计算 sqrt(pi^2) 并检查它是否为整数。如果是这样，你就完成了。
• 如果没有继续下一个i。

这足以满足您的需求吗？它适用于相对较小的 p，但显然对于密码学中使用的那种大素数来说会很慢。

Answer 3

好吧，我可以建议您重读费马的 4n+1 定理。

如果软件工程师使用正确的工具来完成这项工作，那么您就有简单的解决方案。我的数学函数：

P[p_] := Reduce[-p + x^2 + y^2 == 0, {x, y}, Integers]

例子：

寻找前几个素数 p 的解，它们是 1 或 2 (mod 4)。

P /@ {2, 5, 13, 17, 29, 37, 41, 53, 61}