Timeline for Efficient computation of integer representation as a sum of three squares
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 17, 2019 at 7:27 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
added (sums-of-squares) and (computational-number-theory) - the question has been bumped by a new answer
|
| Jan 22, 2017 at 13:50 | history | edited | Anton | CC BY-SA 3.0 |
edited title
|
| Jan 20, 2017 at 5:45 | comment | added | D.W. | See also math.stackexchange.com/q/483101/14578 | |
| Dec 15, 2013 at 8:27 | history | edited | Anton | CC BY-SA 3.0 |
deleted 10 characters in body; edited tags
|
| Aug 30, 2013 at 23:46 | comment | added | JRN | See also mathoverflow.net/q/110239/12357 | |
| Oct 26, 2012 at 3:15 | vote | accept | Anton | ||
| Oct 21, 2012 at 23:28 | answer | added | Jeffrey Shallit | timeline score: 25 | |
| Aug 10, 2012 at 7:45 | comment | added | joro | Anton, added some experimental results in the answer. | |
| Aug 9, 2012 at 9:15 | comment | added | Dror Speiser | You are missing two things: the first is that what you said isn't exactly true, you don't know how long you'll search for a $z$ that actually works, i.e. that $n-z^2$ is a sum of two squares - sure, once it works you have $x,y$ from factorisation, but how many $z$ must you try before one works? second, subexponential factoring are probabilistic algorithms, without proofs, just like the method that has been proposed. | |
| Aug 9, 2012 at 9:12 | vote | accept | Anton | ||
| Oct 26, 2012 at 3:15 | |||||
| Aug 9, 2012 at 9:06 | comment | added | joro | @Dror factoring is subexponential, so finding a $z$ that does work will give subexponential complexity or am I missing something? This approach is far from efficient though. | |
| Aug 9, 2012 at 8:51 | comment | added | Dror Speiser | I believe there are no references in the literature to this problem, nor does the current knowledge on primes allow to prove theorems such as those above. I also have a copy of Grosswald's book, and I can assure you that it does not contain an answer to this problem. I hate to sound so pessimistic, but hey, on the bright side, if you do find anything better than exponential complexity, you'll probably be the first to do so! | |
| Aug 9, 2012 at 7:33 | comment | added | Anton | Sounds reasonable, but I have a couple of questions. First, notice that your proposition is true only for $m \equiv 1 \pmod{4}$. In that case $x$ and $z$ are odd, $y$ is even, and therefore $m - z^2 = x^2 + y^2 \equiv 1 \pmod{4}$. Is it always possible to find such a prime $p$ so that $p = x^2 + y^2$? Do you know any proof for this? Second, for $m \equiv 3 \pmod{8}$ we have $m - z^2 = x^2 + y^2 \equiv 2 \pmod{8}$. So in this case, I guess, we should look for $p$ such that $2p = x^2 + y^2$. Again, why does this $p$ always exists? Also, could you please give a link to an article about algorithm? | |
| Aug 9, 2012 at 7:24 | answer | added | joro | timeline score: 11 | |
| Aug 9, 2012 at 6:59 | comment | added | Dror Speiser | For a fast probabilistic approach, based on Cramer's conjecture, simply take small values of $z$ in the appropriate arithmetic progression, and check if $n-z^2$ is a prime number which is $1$ mod $4$. Then, to get $p=x^2+y^2$, use Lagrange's algorithm. | |
| Aug 9, 2012 at 5:50 | history | asked | Anton | CC BY-SA 3.0 |