0
$\begingroup$

$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?

$\endgroup$
3
  • 1
    $\begingroup$ It's a finite problem, so exhaustive search ought to work. Perhaps you're looking for a certain level of efficiency? $\endgroup$ Jul 13, 2011 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$ Jul 13, 2011 at 12:26
  • $\begingroup$ @Barry interesting could you elaborate how to find such representations? $\endgroup$
    – user16007
    Jul 13, 2011 at 21:36

2 Answers 2

5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ @Victor what is gp? $\endgroup$
    – user16007
    Jul 14, 2011 at 5:08
  • 2
    $\begingroup$ @unknown: gp is the computation language which comes with the Pari library for doing number theory. $\endgroup$ Jul 14, 2011 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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