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 | |
|---|---|---|---|---|---|
| Sep 30, 2019 at 0:20 | comment | added | Charles | @VS. Suppose you have a semiprime that's 1 mod 4. (If it was 3 mod 4 you'd know it wasn't a sum of squares already.) If you learn that it's a sum of two squares, the prime factors are both 1 mod 4 (or equal). If you learn it's not the sum of two squares, the prime factors are both 3 mod 4. Either way you go from knowing their last bit to knowing their last 2 bits. | |
| Sep 30, 2019 at 0:09 | comment | added | VS. | @Charles I mean I want to know 'If it was easy, then it would give away the second-lowest bit in both prime factors of such numbers'. Also what is the blog link? | |
| Sep 29, 2019 at 23:38 | comment | added | Charles | @VS. No method is known or believed to exist. Tao has a post on his blog about this. | |
| Sep 29, 2019 at 21:17 | comment | added | VS. | @Charles How do you get second-lowest bit? | |
| Mar 13, 2011 at 3:50 | comment | added | Charles | See also Tao's answer mathoverflow.net/questions/3820/… . | |
| Mar 13, 2011 at 3:45 | comment | added | Charles | ?? You would CRT all the known residues together so that for one of the primes dividing n, p = r mod m. Then use Coppersmith to find numbers in that residue class which have a nontrivial gcd with n, recovering the factor. Isn't that a standard use of the algorithm? Of course you'd need a lot of information, but Coppersmith makes "a lot" a much smaller number than if the only available algorithm was testing numbers of the form r, r+m, r+2m, ... sequentially. (Obviously, if only a very small amount of information is known, general-purpose factorization is faster.) | |
| Mar 12, 2011 at 20:12 | comment | added | H A Helfgott | Please explain - how would you use Coppersmith's algorithm? What information would you be assuming, precisely? | |
| Mar 9, 2011 at 19:28 | history | edited | Charles | CC BY-SA 2.5 |
Coppersmith's algorithm
|
| Mar 9, 2011 at 19:20 | history | answered | Charles | CC BY-SA 2.5 |