$p + p' = m$

$q - q' = n$

$pp' = qq'$

$(m^{2} + n^{2})\equiv1\pmod 4$ and $n^{2}\equiv0\pmod 4$.

Only $m,n$ are known in the above. Are there any known techniques to guess the values of $p$ and $q$ efficiently?

| cite | improve this question | | | | |
  • 1
    $\begingroup$ It's a finite problem, so exhaustive search ought to work. Perhaps you're looking for a certain level of efficiency? $\endgroup$ – Gerry Myerson Jul 13 '11 at 11:47
  • 3
    $\begingroup$ The mod 4 conditions amount to saying that n is even and m is odd. The system boils down to solving p(m-p)=q(q-n), which can be rewritten as p^2-pm+q^2-qn=0, which can be rewritten as (m-2p)^2 + (n-2q)^2 = m^2 + n^2, which can be rewritten as M^2 + N^2 = m^2 + n^2 with M odd and N even. So you're basically asking for different ways to write an odd number as the sum of two squares. $\endgroup$ – Barry Cipra Jul 13 '11 at 12:26
  • $\begingroup$ @Barry interesting could you elaborate how to find such representations? $\endgroup$ – user16007 Jul 13 '11 at 21:36

Since finding all possible expressions $$ M^2 + N^2 = m^2 + n^2$$ will in fact give you a complete factorization of $m^2 + n^2,$ all you need to know is how to create all $(M,N)$ pairs from a complete prime factorization of $m^2 + n^2 = p_1 p_2 p_3 \ldots p_r q_1^2 q_2^2 \ldots q_s^2,$ where the $p_i \equiv 1 \pmod 4,$ while all $q_j \equiv 3 \pmod 4,$ and the labeled primes are not necessarily distinct. Each prime $p_i$ has essentially one representation as the sum of two squares, at least when positive and ordered. Then you just use $$ (a^2 + b^2) (c^2 + d^2) = (a c + b d)^2 + ( a d - b c)^2$$ while putting in $\pm$ signs on $a,b,c,d$ and switching order. For each expression, you just multiply through by all the $q_j.$ The $q_j$ must, of course, appear as factors of $\gcd(m,n).$

The general method for any $x^2 + k y^2 = t,$ for some $k \geq 1,$ is the Hardy-Muskat-Williams algorithm, which is implemented in some CAS, sometimes correctly. Given any $p_i,$ the first task in solving $u^2 + v^2 = p_i$ is finding a square root of $-1 \pmod {p_i}.$ The rest of this is treated in Editor's Corner: The Euclidean Algorithm Strikes Again by Stan Wagon, M.A.A. Monthly,Vol. 97, No. 2 (Feb., 1990), pp. 125-129. The first page can be seen at this link. However, the way I would do it is to take the integer with $w^2 \equiv -1 \pmod {p_i},$ or $w^2 + 1 = p_i t,$ write down the positive quadratic form $\langle p_i, 2 w, t \rangle$ and keep track of each step as I reduce it to $\langle 1,0,1 \rangle,$ reversing steps to find a representation $u^2 + v^2 = p_i.$ Although, as I think of it, I actually do the whole thing by matrix multiplication anyway.

Meanwhile, there is a very nice note on using multiple expressions as the sums of two squares to factor a number, in the M. A. A. Monthly, December 2009, pages 928-931, A Note on Euler's Factoring Problem by John Brillhart.

Testing whether an integer is the sum of two squares

| cite | improve this answer | | | | |

Thanks to Noam Elkies for telling me to post my one-liner to solve this in gp (this dates from around 1993):

fermat(p) = qflll([lift(sqrt(Mod(-1,p))),p;1,0])[1,]

What this does is to use the well known construction (I think that it's in Hardy and Wright), that says that if $0 < a < (p-1)/2$ satisfies $a^2 = -1 \bmod{p}$ if you run the continued fraction algorithm for $a/p$ "half-way" to get the convergent $r/s$ then $r^2 + s^2 = p$. What the above one-liner does is to set up the lattice $$\pmatrix {a&p \cr 1 & 0 \cr}$$ The shortest vector in this lattice has $L^2$ norm of $p$.

| cite | improve this answer | | | | |
  • $\begingroup$ Victor, I edited your matrix and hope I got it right. $\endgroup$ – Gerry Myerson Jul 14 '11 at 5:03
  • $\begingroup$ @Victor what is gp? $\endgroup$ – user16007 Jul 14 '11 at 5:08
  • 1
    $\begingroup$ This doesn't look right because the determinant of the matrix should be $\pm p$. The bottom row should be $(1,0)$, not $(p,1)$. Note that gp uses the lattice generated by the columns of a matrix, not the rows. $\endgroup$ – Noam D. Elkies Jul 14 '11 at 5:09
  • $\begingroup$ @Noam: thanks. I was having problems with mathjax and matrices. Gerry fixed it for me. $\endgroup$ – Victor Miller Jul 14 '11 at 13:13
  • 1
    $\begingroup$ @unknown: gp is the computation language which comes with the Pari library for doing number theory. $\endgroup$ – Victor Miller Jul 14 '11 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.