将素数表示为四个平方整数的总和 [英] Represent a prime number as a sum of four squared integers

问题描述

给定质数p，找到四个整数，使得p等于这些整数的平方和。

Given a prime number p, find a four integers such that p is equal to sum of square of those integers.

1< p ＜ 10 ^ 12。

1 < p < 10^12.

如果p的形式为8n +1或8n + 5，则p可以写成两个平方之和。这可以用O（sqrt（p）* log（sqrt（p））来解决。但是对于其他情况，即当p不能写成两个平方之和时，效率非常低，因此，如果有人可以提供一些我可以阅读以解决问题的资源。

If p is of form 8n + 1 or 8n + 5, then p can be written as sum of two squares. This can be solved in O(sqrt(p)*log(sqrt(p)). But for other cases,i.e. when p cannot be written as sum of two squares, than is very inefficient. So, it would be great if anyone can give some resource material which i can read to solve the problem.

推荐答案

鉴于您的约束，我认为您可以

Given your constraints, I think that you can do a smart brute force.

首先，请注意，如果p = a ^ 2 + b ^ 2 + c ^ 2 + d ^ 2，则a，b，c， d必须小于10 ^ 6。因此，只需将a从0循环到sqrt（p）。考虑q = p-a ^ 2。可以很容易地检查q是否可以写为使用<一个href = https://en.wikipedia.org/wiki/Legendre%27s_three-square_theorem rel = nofollow noreferrer> Legendre的三平方定理。一旦找到有效的q值，

First, note that if p = a^2 + b^2 + c^2 + d^2, each of a, b, c, d have to be less than 10^6. So just loop over a from 0 to sqrt(p). Consider q = p - a^2. It is easy to check whether q can be written as the sum of three squares using Legendre's three-square theorem. Once you find a value of q that works, a is fixed and you can just worry about q.

以相同的方式处理q，将b从0循环到sqrt（q），并考虑r = q-b ^ 2。费马二平方定理告诉您如何检查r是否可以写成两个平方之和。尽管此检查再次需要O（sqrt（r））时间，但实际上您应该能够快速找到有效的b值。

Deal with q the same way. Loop over b from 0 to sqrt(q), and consider r = q - b^2. Fermat's two-square theorem tells you how to check whether r can be written as the sum of two squares. Though this check requires O(sqrt(r)) time again, in practice you should be able to quickly find a value of b that works.

在此之后，它应该

因为找到a和b和（c，d）的循环不是嵌套的，但是来了，所以很容易找到适合r的（c，d）对。一个接一个，复杂度应该足够低以解决您的问题。

Since the loops for finding a and b and (c,d) are not nested but come one after the other, the complexity should be low enough to work in your problem.

这篇关于将素数表示为四个平方整数的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！