Timeline for Testing whether an integer is the sum of two squares
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 12 at 19:27 | comment | added | gnasher729 | I looked at the problem “are there a, b >= 0 such that a^5+b^5=s” and inspired by this thread, it turns out that a+b divides a^5+b^5. Which may help finding solutions. | |
| Oct 23, 2014 at 18:28 | comment | added | Max Alekseyev | Well, at least for Blum integers mentioned above, there are no square factors, and no cancelling is required. | |
| Oct 23, 2014 at 15:15 | comment | added | ndkrempel | But "cancel all possible square factors" is not known to be polynomial time, so you have not demonstrated the equivalence. | |
| Oct 21, 2014 at 16:48 | comment | added | Max Alekseyev | @ndkrempel: Strictly speaking, equivalence here is with being the sum of two coprime squares. For non-coprime squares, we can try to cancel all possible square factors of $n$ and then test if it becomes the sum of coprime squares. In particular, for $n=45$, we have that -1 is a square modulo $45/3^2=5$. | |
| Oct 20, 2014 at 21:22 | comment | added | ndkrempel | Can you explain your equivalence? It is not directly equivalent as, for example, 45 is a sum of two squares but -1 is not a square modulo 45. | |
| Jul 19, 2011 at 15:45 | comment | added | Max Alekseyev | Why "quadratic residuosity problem is supposed to be hard when n is a Blum integer"? It is formulated for a generic composite number. A Blum integer would be a particular case of the problem. | |
| Mar 10, 2011 at 11:02 | comment | added | Emil Jeřábek | To expand on Peter’s comment, the quadratic residuosity problem is supposed to be hard when $n$ is a Blum integer, in which case we know a priori that $-1$ is not a square. | |
| Mar 9, 2011 at 23:32 | comment | added | Peter Shor | But is testing whether -1 is a square as hard as testing whether an arbitrary residue (with Jacobi symbol 1) is a square? Testing whether an arbitrary residue is a square is the supposedly hard quadratic residuosity problem. | |
| Mar 9, 2011 at 19:51 | history | answered | Max Alekseyev | CC BY-SA 2.5 |