2
$\begingroup$

The method described below is different from Euler sum of two squares factorization method. The method below does not require 2 sum of two squares representations to factor a number.

This post was inspired by the post on using the sum of two squares to determine if a number is square free (see Can the sum of two squares be used to determine if a number is square free?"). We will show below that the sum of two squares can definitely be used to factor integers. However, at this point in time, it is not known if this method is fast enough to factor large numbers (hundred digits).

We start with a simple example of $N=a^2+b^2=3*5=15$. We know that this number cannot be decomposed into a sum of two squares (2sq rep). So we square $N$ to get $N^2=M=3^2*5^2=225$. We calculate the two squares representation (2sq rep) of $M$ and find $M=9^2 + 12^2$. At this point we take the GCD of $GCD(9^2,12^2)=9$. So $9$ is a common factor and this means that $M$ can be rewritten as $M=3^2*3^2 + 3^2*4^2= 3^2*(3^2+ 4^2)=3^2*5^2$. The last step is not needed. Once a common factor is found, we know that it is a factor of M and its square root is a factor of N.

To show that the method works for an arbitrary numbers we will provide few more examples. However at this point we only consider numbers of the form $N=pq$ or numbers of the form $N=pq^2$.

Example #1. $N=7*37=259$, $N^2=259^2=67081=84^2 + 245^2$. We calculate $GCD(84^2,245^2)=7^2$. So we find that $7^2$ is a factor of $N^2$ and that $7$ is a factor of $N$.

Example #2. $N=13*17=221$, $N^2=221^2=48841=21^2 + 220^2=85^2 + 204^2= 104^2 + 195^2=140^2 + 171^2$. We calculate the GCD for each 2sq rep.

$$ \begin{split} \gcd(21^2,220^2)&=1\\ \gcd(85^2,204^2)&=289=17^2\\ \gcd(104^2,195^2)&=169=13^2\\ \gcd(140^2,171^2)&=1 \end{split} $$

We that the first and last 2sq rep give no information on the factors of $N^2$ but the 2nd and 3rd 2sq rep provide the squares of the factors of N. This example shows that the sum of two squares can factor an integer provided we consider all 2sq representations of $N^2$ since we don't know which one is going to provide us with the information on the factors.

We now provide an example where the sum of two squares does not work.

Example #3. $N=19*31=589$. This number does not have a sum of two squares. We square it to get $N^2=589^2=0^2 + 589^2$. This 2sq rep provides no information on the original factors of N.

The question is this: can the sum of two squares get the factors of $N^2$ in a reasonable amount of time?

$\endgroup$
  • $\begingroup$ thanks for the edit. $\endgroup$ – user25406 Jan 8 at 18:28
  • $\begingroup$ See Euler's factorization method $\endgroup$ – Robert Israel Jan 8 at 18:49
  • $\begingroup$ Yes, I am aware of Euler method but the above method is different. It does not need 2 "sum of 2 squares representation". The first example of $N^2=7^2*37^2= 84^2 + 245^2$ has only one 2sq representation yet we were able to factor the number. Euler's method would not have been able to factor this one. $\endgroup$ – user25406 Jan 8 at 18:58
  • 1
    $\begingroup$ @user25406, I downloaded the PARI/GP source code for the tool you mentioned. When I ran it, I was able to compute the representation of 100 digit numbers as sums of squares. The only other step is to compute the gcd of each of the representations, which can be done fairly quickly (polynomial time). $\endgroup$ – coDE_RP Jan 8 at 20:01
  • 2
    $\begingroup$ A representation $N=x^2+y^2$ is called primitive if $\gcd(x,y)=1$. It is well known that $N$ has no primitive representations if it is divisible by primes $p\equiv 3 \pmod 4$. What this means is if there are primes $p\equiv 3 \pmod 4$ that divides $N$ and you can find a sum of squares representation, $d =\gcd(x,y)\neq 1$ and $d$ always gives you a product of $p^2$. So yes you can factor certain integers efficiently this way. However for products of $p\equiv 1 \pmod 4$ I believe it is always possible to form primitive representations, so that $\gcd(x,y)=1$. $\endgroup$ – Yong Hao Ng Jan 9 at 9:49

Your Answer

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

Browse other questions tagged or ask your own question.