Timeline for Testing whether an integer is the sum of two squares
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 7, 2019 at 0:50 | comment | added | user25406 | There is a simple method using triangular numbers that can find the representation of a number N as a sum of two squares without having to factor N but the timing is not known. The details can be found here: math.stackexchange.com/questions/1972771/… | |
| Oct 23, 2018 at 16:35 | history | edited | Martin Sleziak |
added the (sums-of-squares) tag; the question has been bumped anyway
|
|
| Oct 23, 2018 at 16:32 | history | edited | H A Helfgott | CC BY-SA 4.0 |
added 1 character in body
|
| S Oct 18, 2014 at 14:47 | history | suggested | lennon310 | CC BY-SA 3.0 |
math formatting
|
| Oct 18, 2014 at 14:02 | review | Suggested edits | |||
| S Oct 18, 2014 at 14:47 | |||||
| Jun 26, 2011 at 2:16 | answer | added | Kevin O'Bryant | timeline score: 12 | |
| Mar 19, 2011 at 14:22 | history | bounty ended | H A Helfgott | ||
| Mar 12, 2011 at 13:58 | history | bounty started | H A Helfgott | ||
| Mar 9, 2011 at 19:51 | answer | added | Max Alekseyev | timeline score: 8 | |
| Mar 9, 2011 at 19:39 | comment | added | Chris Wuthrich | An idea that does not help : It is equivalent to ask to check if the conic $x^2+y^2 = n$ has a rational solution. But unless I factor $n$, I would not know at which finitely many primes $p$ I have to check locally solubility. | |
| Mar 9, 2011 at 19:24 | comment | added | GH from MO | @Emil: If a prime p is 1 mod 4 then a representation p=a^2+b^2 can be found in deterministic polynomial time. First use Schoof's algorithm (Math. Comp. 44 (1985), 483-494) to find a solution of x^2 = -1 mod p in polynomial time, then use the Euclidean algorithm in Gaussian integers to find a+bi=gcd(p,x+i) in polynomial time. | |
| Mar 9, 2011 at 19:20 | answer | added | Charles | timeline score: 13 | |
| Mar 9, 2011 at 19:18 | comment | added | J.C. Ottem | @David: Yes, I realized this just after posting, besides it wasn't meant as a serious comment... :) | |
| Mar 9, 2011 at 19:16 | comment | added | David E Speyer | "It would be odd if this turned out to be harder than detecting primality, since prime numbers are rarer." This intuition seems completely false to me. I can test whether $n$ is a power of $3$ is $O((\log n)^2)$, and that's a very rare condition! | |
| Mar 9, 2011 at 19:15 | comment | added | David Loeffler | @J.C. Ottem: "Polynomial time" in this context generally means "polynomial in the number of bits needed to represent the input", i.e. polynomial in $log(n)$. Harald makes this completely clear in the question. | |
| Mar 9, 2011 at 19:07 | comment | added | Emil Jeřábek | I wouldn't expect detecting representable numbers to be substantially easier than computing such a representation. There is a probabilistic polynomial-time algorithm for finding these representations by Rabin and Shallit (dx.doi.org/10.1002/cpa.3160390713), but it only works for primes, which is the case you are not interested in (detecting whether a prime can be represented is trivial). | |
| Mar 9, 2011 at 18:56 | history | asked | H A Helfgott | CC BY-SA 2.5 |