Timeline for Efficient computation of integer representation as a sum of three squares
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 10, 2012 at 7:44 | history | edited | joro | CC BY-SA 3.0 |
Added experimental results
|
| Aug 10, 2012 at 7:06 | comment | added | Anton | Another example: $n = 276907\cdot 456811\equiv 1\pmod{4}$ is a 37 bit number. We have $r_3(n)=12h(-4n)$, and $h(-4n)=152884$. Again, if we take $z>y>x>0$ and iterate over $z$, we have $150320$ possible values of $z$ (even or odd) and $38221$ representations. If we suppose that the values of $z$ for which representation exists are evenly distributed on the set $\left[ \lceil \sqrt{n/3} \rceil ; \lfloor \sqrt{n} \rfloor \right]$, then we should find $z$ in about 4th try. | |
| Aug 10, 2012 at 6:57 | comment | added | Anton | It seems to be polynomial... I tried on couple of examples. If we take a 40 bit number $n=701473\cdot 1067987\equiv 3\pmod{8}$, then $h(−n)=467120$ (20 bits), and $r_3(n)=24h(−n)$. Lets take only $x,y,z>0$ without permutations (with $z>y>x>0$). We have $h(−n)/2=233560$ possible representations. We can also show that $\lceil\sqrt{n/3}\rceil\leq z\leq\lfloor\sqrt{n}\rfloor$. In that case we have $182910$ possible odd values of $z$. Note that both number of possible values of $z$ which is $182910$ and number of representations $233560$ are 18 bit numbers! | |
| Aug 9, 2012 at 22:07 | comment | added | Marty | Here's some heuristics for predicting how many values of $z$ are needed: the solutions to $x^2 + y^2 + z^2 = n$ are roughly equidistributed on the sphere, and the number of solutions is proportional to the class number $h(-4n)$, which grows like $\sqrt{n}$. So consider $C \cdot \sqrt{n}$ points equidistributed on the sphere of area $4 \pi n$. What is the statistical expectation of the smallest (positive) $z$-coordinate among these points? | |
| Aug 9, 2012 at 16:24 | history | edited | joro | CC BY-SA 3.0 |
typo
|
| Aug 9, 2012 at 9:33 | comment | added | joro | Anton you may be right, I thought of this too. Check for yourself the timings. pari/gp is open source, so you can reuse most of the code. | |
| Aug 9, 2012 at 9:14 | comment | added | Anton | That sounds like a pretty good result. Ok, I'll do some more research on how fast this works and how many $z$ should be checked and write about it later. By the way, I think that it is more efficient to start not with $z=0$, but with $z= \lfloor n / \sqrt{3} \rfloor$. Then we'll get the smallest value of $n−z^2$ and it would be more probable for this number to be prime. | |
| Aug 9, 2012 at 9:12 | vote | accept | Anton | ||
| Oct 26, 2012 at 3:15 | |||||
| Aug 9, 2012 at 9:00 | comment | added | joro | The algorithm is probabilistic and I don't know how many values of z are needed. You can check the program for your data (probably lowering 10^8 to 10^6, check for yourself). As the program showed 1332 bit integer was solved in about a minute. | |
| Aug 9, 2012 at 8:57 | comment | added | Anton | By the way, here's the online tool for solving the two squares problem: numbertheory.org/php/main_pell.html. Also, I found a book that contains an algorithm by Serret that solves the two squares problem in $O(\log^4{p})$ (based on ERH): plouffe.fr/simon/math/…. | |
| Aug 9, 2012 at 8:52 | comment | added | Anton | OK, this works. The question is, does this work in a polynomial time? There exist two algorithms (by Serret and by Schoof) that compute $x$, $y$ for a given $p=x^2+y^2$ in a polynomial time. But how many values of z will we check before finding a proper one? I need this for cryptographic purposes, so efficiency is crucial. | |
| Aug 9, 2012 at 8:03 | history | edited | joro | CC BY-SA 3.0 |
Added pari program
|
| Aug 9, 2012 at 7:24 | history | answered | joro | CC BY-SA 3.0 |