1
$\begingroup$

We have seen that it was possible to use the sum of two squares to factor numbers (see Can the sum of two squares be used to factor large numbers? )

The main drawback is the fact that the method cannot factor numbers of the form $N=(4k_1-1)*(4k_2-1)$. Since every integer can be expressed as a sum of 4 squares, the method should be able to handle all numbers.

We start with the following example: $N=7*13=91$. We calculate its sum of 4 squares representation (4sq rep) $N=a^2+b^2+c^2+d^2$ and we get:

$$N=91=(5,5,5,4),(5,7,4,1),(5,8,1,1),(8,3,3,3),(9,3,1,0)$$

The idea is to look for the lower factor as one possible square or a combination of squares $c=(a^2+b^2+...)$ or a mixed combination $c=(a^2+b+...)$ or just $c=(a+b+...)$ that, when added together, will provide a number which shares a factor with the number $N$ we want to factor. We then take the $gcd(N,c)$ to see if we have a factor.

The second 4sq rep provides the square of the factor $7^2$ but also $5^2+4^2+1^2=42=7*6$. The third representation provides an example of factor by adding $a+b=5+8=13$. The forth representation provides an example of a mixed mode $8^2+3+3=70=7*10$. The last one provides an example of $(a+b+c)=9+3+1=13$, the larger factor.

Some of the problems are:
1-for small numbers with not many 4sq rep's, it doesn't take a lot of time to calculate them and check the different combinations to find a factor.
2-for large numbers, it takes a long time to calculate all these 4 sq rep's.
3-Checking all the combinations also can take a lot of time.
4-good representations are not always among the first to be calculated and tested. There is no known method to change the order in which useful representations appear.

One way to speed up the process is to calculate one representation at a time, test it and if no factors are found, calculate another one and test it.
Another way is to calculate just one representation and, if no factor is found, calculate the 4sq rep of the squares of the first representation. The number of combinations to check can rise quickly when we go from $4$ squares to $16$ squares. For small numbers, it's probably better to calculate the next 4sq rep than to expand the squares of the first 4sq rep.
A faster way to find a factor for small numbers is to expand the squares into sums of triangular numbers and try to find a combination that can lead to a factor. I have not tested the decomposition of squares in triangular numbers with large numbers.

There are probably other ways to speed up the process but I can't seem to find them.

The question is: Can this method be made efficient?

The other, more fundamental question, is which sum of squares is better suited to factoring large numbers, $4$, $6$, $8$...?

$\endgroup$
2
  • 1
    $\begingroup$ A representation of two squares should be more valuable, but I do not think that any method of this kind can compete with the best known integer factorization methods. To factor small numbers, such methods can however be suitable, but in this case, trial division is not bad either. However I guess, you are anyway interested in theoretical possibilities to factor a number, and it is not obvious how a representation with the sum of $4$ squares should be used for this purpose. $\endgroup$
    – Peter
    Commented Jan 27, 2019 at 16:28
  • $\begingroup$ @Peter, yes I am interested in knowing if the above method can be theoretically be justified. I know it works and I provided few examples to show that but we need more than numerical evidence to conclude that the method works for large numbers. $\endgroup$
    – user25406
    Commented Jan 27, 2019 at 20:33

2 Answers 2

Reset to default
2
$\begingroup$

So I was interested in a similar factorization algorithm, so I'll just give you my feedback.

First of all, generating all sum of four square representations (SFSRs) is extremely computationally expensive. The total number of representations for a number N is $$24\sum_{d|N, odd} d$$which grows between $\Omega (N)$ and $O(N\log\log N)$; with that many steps, you may as well do trial division.

Second, there doesn't seem to be any reason for your value $c$ to have a nontrivial $\gcd$ with $N$i.e. most of the time, $\gcd(N,c)=1$. Hoping that perhaps one such way of generating $c$ results in a nontrivial $\gcd$, the runtime is then dependent on how many positive integers have a nontrivial $\gcd$ with $N$. If $N=pq$ for distinct primes $p$ & $q$, then this number would just be $p+q$, meaning if you consider your $c$ to be randomly chosen from $1$ to $N$, you would have roughly a $1/\sqrt{N}$ chance of landing on something not coprime to $N$.

Third, this technique doesn't seem at all reminiscent to the two square factorization method you mentioned. Euler's method was to reverse the Fermat-Brahmagupta identity, which ended up being as simple as calculating a couple $\gcd$s. An analogous method for four squares would be to reverse Euler's Four-Square Identity.

The algorithm I was interested in did something similar, but it restricted how many SFSRs it generated, then the idea was to combine them to solve for the squares of the factors' SFSRs. It doesn't work for a couple of reasons, but perhaps the method was a little better.

$\endgroup$
4
  • $\begingroup$ 1-I need more than one comment to respond to you. There are many ways to make the method more efficient. For example, instead of calculating every single SFSR, we calculate just the first one and if we don't get a useful gcd, we calculate the SFSR of say $a=x^2+y^2+z^2+t^2$ and we look for combinations of the squares of $a$ and the other 3 from the initial decomposition. Of course, the more squares the better the chances to hit on a useful gcd but the number of combinations to check grows rapidly so it takes more time. $\endgroup$
    – user25406
    Commented Sep 16, 2019 at 11:06
  • $\begingroup$ 2-From numerical experience, sometimes we miss hitting a factor by + or -1. So I thought of adding the squares $v=1+2^2+3^2+4^2+5^2+6^2+7^2+8^2+9^2$ to the decomposition of $(N-v)$. There is nothing that prevents us from using more squares than just 4. Doing so will transform any close solution by $(1,2,3,4,5,6,7,8,9)$ or by the squares themselves $(1,2^2,...,9^2)$ to a solution. $\endgroup$
    – user25406
    Commented Sep 16, 2019 at 11:13
  • $\begingroup$ 3-take the first decomposition of $N=91=5^2+5^2+5^2+4^2$. We see that $5^2+5^2=50=49+1=7^2+1$ and $5^2+4^2=41=42-1=6*7-1$. So we see that we are off by $+1$ when combining the first two squares and by $-1$ when combining the last two squares. There are many cases like this and it has to do with the fact that numbers of the form $(4k+3)$ cannot have a sum of two squares representation. If we don't get a useful gcd, we can always take the sum of 2 squares and add 1 or subtract 1 and check for a useful gcd. Again, there is nothing to prevent us from doing so. $\endgroup$
    – user25406
    Commented Sep 16, 2019 at 11:25
  • $\begingroup$ 4-In one of my posts, I showed that the 4sr are equivalent, meaning we can transform one into another with a bit of work. (I didn't provide a proof, I just showed that it can be done. But no one came up with the proof) (The only reason I didn't experiment with these ideas is because I cannot code and doing everything by hand is just too slow). I am sharing this with you hoping that it will be useful. I would really like to see your work, please provide the link. (My email is also available on my profile). $\endgroup$
    – user25406
    Commented Sep 16, 2019 at 11:25
1
$\begingroup$

I'm still not entirely sure what you're doing. There's certainly nothing preventing us from adding more squares or combining the terms with the hope of finding a factor, but I don't see any theoretical reasons why it should be any more likely to find a factor than randomly guessing, and if you look at the probability of landing on a number with nontrivial gcd with $N$, it's absurdly unlikely.

If you instead try to reverse Euler's Four-Square Identity, then it at least becomes theoretically clear why it should be more likely. Nonetheless, I've never been able to make it work

$\endgroup$
8
  • $\begingroup$ Please send me a link or a write-up of the work you did on reversing Euler's 4-sq identity (if possible or let me know if not). $\endgroup$
    – user25406
    Commented Sep 18, 2019 at 11:41
  • 1
    $\begingroup$ The goal is to generate SFSRs of a number $N$, and then to combine them in such a way that we can explicitly solve for the factors. I don't currently have the time to explain the method. It's not even fully fleshed out. $\endgroup$
    – JasonM
    Commented Sep 19, 2019 at 15:14
  • 3
    $\begingroup$ @user25406 Hello I hope you see this comment. This is an update on the method I was looking into. It turns out it was also infeasible since it relied on finding 4 SFSRs that 'corresponded' in a precise way, and it turns out this was highly unlikely to occur given a random choice. In instances where the factorization is highly unlikely for very large numbers, you should explore an alternative method. $\endgroup$
    – JasonM
    Commented May 26, 2020 at 2:08
  • 2
    $\begingroup$ @user25406 Very interesting, but I can see right away it will run into another issue for very large numbers. Namely, while you may be able to force the first square to be the same in both SFSRs, it would be highly unlikely to force it for 3 of the 4 to get the cancellation you want. The reason these methods are so unlikely to give you a nontrivial factor is because for the most difficult numbers (like RSA numbers) very few numbers are not coprime with your number. So it's almost impossible to land on a factor by chance. You should stop looking at methods which only apply for small numbers. $\endgroup$
    – JasonM
    Commented Apr 4, 2021 at 5:10
  • 2
    $\begingroup$ @user25406 Again, the pattern you are noticing is one that probably only holds for very small numbers. We would like a method that generalizes to the most difficult numbers (which seems to be RSA numbers). The vast majority of numbers can easily be factored with trial division or Fermat's method in a brief amount of time, but the handful of cases where these don't work are the types of numbers used for encryption (and therefore relevant for developing a factorization algorithm). For example, try to factor the number 5009981 by hand with your method. This is a relatively small RSA number. $\endgroup$
    – JasonM
    Commented May 10, 2021 at 22:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .