表示质数为两个平方数之和的最快算法是什么？

Question

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

其中 p mod 4 = 1。

谢谢。

- roxrook

---

请尝试在http://cstheory.stackexchange.com/上提问。 - sinelaw

您好，我不认为这种类型的问题适合在那个网站上提问，因为据我理解，cstheory 是用于研究级别的。如果我错了，请纠正我。 - roxrook

可能会有用：http://mathoverflow.net/questions/29644/enumerating-ways-to-decompose-an-integer-into-the-sum-of-two-squares - Jim Mischel

@Chan：如果我没记错的话，在我的大学里我们写成 p == 1 (mod 4)，这样对于非数学专业的人来说可能更容易理解。其中 == 是我们实际写的最好的ASCII表示，当需要严谨时，我们会用一个 ≡ 字符，或者如果显而易见并且你懒得写的话，直接用 = 就可以了。当然，如果你正式声明你完全在模4的整数环中工作，那么这将不会导致非常有趣的两个平方和分解... - Steve Jessop

p=1 (mod 4) 对我来说非常清晰。 - ypercubeᵀᴹ

Answer 1

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

你还可以在这个数学网站上找到一个好的算法列表：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

- Aryabhatta

Answer 2

您不需要搜索所有的组合。一个简单而朴素的实现草图如下：

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

这对于相对较小的p来说是足够的，但显然对于在加密中使用的大质数来说速度会比较慢。

- David Heffernan

---

p-i^2将始终为整数。我认为你想要sqrt(p-i^2)。 - Jim Mischel

Answer 3

我可以建议你重新阅读Fermat's 4n+1 Theorem。

如果软件工程师使用正确的工具来完成工作，他们就会有简单的解决方案。我的Mathematica函数：

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

例子：

查找满足条件为 1 或 2（mod 4）的前几个质数 p 的解。

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

- Margus

---

那是一种获取答案的方式，但它不是一个算法。 - Steve Jessop

@Steve Jessop 算法是一组指令，它们结合在一起完成一个任务。你可以说，我以自下而上的方式定义了我的算法，假设 Reduce 函数存在 - 实际上，我不需要其他任何东西（这是构建查询的艺术）。Reduce[expr, vars, dom] 函数通过解方程或不等式来减少语句 expr，并消除域 dom 上的量词。 - Margus

@Margus：那不是“算法”的正确定义，而且算法不仅仅是任何一组指令。你的指令依赖于已经解决问题的工具（Mathematica）的存在。也许可以通过提问者已经提到的蛮力方法，也许是通过更聪明的方法。无论哪种方式，“只需使用Mathematica”可能是一个好建议，但它不会产生算法。如果你打开Mathematica并解释它实际上如何解决这个问题，那么就会得出一个算法。 - Steve Jessop

换句话说，"抄袭你班上最聪明的人的答案"。这是算法吗？不是，因为将班上最聪明的人列入此任务可以假定的工具集是不合理的。对于Mathematica也是如此，因为问题显然很基础，而Mathematica却用一个不透明的步骤解决了它。如果问题是 "两个4位数相乘的最佳算法是什么"，那么同样地，我们会将C的乘法运算符排除在可用的算法步骤之外。 - Steve Jessop

@Margus：这仍然可能是提问者获得所需内容最快的方式，这取决于他提问的原因。 - Steve Jessop