将素数表示为两个平方和的最快算法是什么？
我可以使用两个循环来检查两个小于 p 素数的整数的所有组合，但效率非常低。有没有更好的算法来解决这个问题？有什么想法吗？
其中p mod 4 = 1。
谢谢，
I could use two loops to check for all combinations of two integers that less than p prime, but it's very inefficient. Is there a better algorithm to approach this problem? Any idea?
Where p mod 4 = 1.
Thanks,
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您可以尝试使用 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章/5883#5883
You can try using the Hermite-Serret algorithm.
You can also find a good list of algorithms on this math.se page: https://math.stackexchange.com/questions/5877/efficiently-finding-two-squares-which-sum-to-a-prime
See especially, Robin Chapman's answer: https://math.stackexchange.com/questions/5877/efficiently-finding-two-squares-which-sum-to-a-prime/5883#5883
您无需搜索所有组合。简单朴素实现的粗略轮廓是：
这足以满足您的需求吗？它对于相对较小的 p 来说效果很好，但对于密码学中使用的那种大素数来说显然会很慢。
You don't need to search for all combinations. A rough outline of a simple naive implementation would be:
Would this suffice for your needs? It will work fine for relatively small p, but obviously would be slow for the sort of large primes used in cryptography.
好吧，我建议您重读费马 4n+1 定理。
如果软件工程师使用正确的工具来完成工作，那么您就有简单的解决方案。我的 Mathematica 函数：
示例：
查找前几个素数 p 的解，其中 p 为 1 或 2 (mod 4)。
Well I could recommended you reread Fermat's 4n+1 Theorem.
If software engineers use right tools for the job, thy have simple solutions. My Mathematica function:
Examples:
Finding solutions for first few primes p which are 1 or 2 (mod 4).