[QUOTE=CRGreathouse;461802]I'm not concerned by the number of examples -- a dozen randomly-selected examples would be plenty to convince me, a million is overkill. I'm concerned about the size of the examples. 121, 91, and 77 are really, really small. You don't need to use huge numbers, but 10 or 20 digits would be much better in terms of convincing me that the method has sufficient generality and utility.



I doubt it fails for any small number. If you implemented it the way I did, though, it would take roughly time n^(3/2) to go through all sums of four squares, which is considerably worse than trial division. So even if it did work for all numbers, and not just for all small numbers, it's not clear that it could be made practical.

If you [I]do[/I] want to make it practical, we're going to need not just a faster way of generating sums of four squares, but a way to limit the number of sums we use.[/QUOTE]

I share the conclusions you drew in the last paragraph.

I don't know if a faster way to generate sums of 4 squares can be found. The online calculator I used is very slow when fed large numbers. There is this link on another way to calculate the sum of squares but I couldn't find an online calculator based on the algorithm described in the link. I have no idea if it is a faster algorithm than the one we are using.

[URL]https://cs.stackexchange.com/questions/2988/how-fast-can-we-find-all-four-square-combinations-that-sum-to-n[/URL]

In looking for ways to improve the method, one should maybe consider dropping the requirement that 4-sq reps be used. After all, there is no theoretical justification (I know of) that only sums of 4 squares can be used to factor integers. One may consider using sums of 5, 6 or more squares to factor. And here again, there is no theoretical justification that says sums of 5, 6,,,squares cannot factor integers.

If the requirement to use a sum of 4 squares is dropped, then it is possible to quickly find a representation with a variable number of squares by reducing the number N with the square root function with a, the first square calculated as before.

Once we have a representation of a sum of n squares, we test it as usual by calculating the gcd's. If no factor is found, then instead of calculating another representation, we take one square from the previous sum, say b, and expand it into a sum of m squares. The b square will be replaced by m squares in the original sum. The obvious drawback is that the number of combinations to test will grow rapidly if no factor is found quickly.

I have not had a chance to test these ideas thoroughly like it was done with the sum of 4 squares method so at this point nothing can be said.

The other way to improve the method is to do a serious mathematical analysis of what is involved in factoring when using a sum of 4 squares. One can try to understand why some 4-sq reps lead to a factor and some don't. There is also the need to understand the distribution of the good representations (the ones that give a factor) within the set of a 4-sq sum of a given integer but also the order in which they appear. A major improvement will be to find a way to make the good representations appear at the beginning of the sum of 4 squares. Sadly, all this is beyond what I can do.

[QUOTE=mahbel;461850]I share the conclusions you drew in the last paragraph.

I don't know if a faster way to generate sums of 4 squares can be found. The online calculator I used is very slow when fed large numbers. There is this link on another way to calculate the sum of squares but I couldn't find an online calculator based on the algorithm described in the link. I have no idea if it is a faster algorithm than the one we are using.

[URL]https://cs.stackexchange.com/questions/2988/how-fast-can-we-find-all-four-square-combinations-that-sum-to-n[/URL]

In looking for ways to improve the method, one should maybe consider dropping the requirement that 4-sq reps be used. After all, there is no theoretical justification (I know of) that only sums of 4 squares can be used to factor integers. One may consider using sums of 5, 6 or more squares to factor. And here again, there is no theoretical justification that says sums of 5, 6,,,squares cannot factor integers.

If the requirement to use a sum of 4 squares is dropped, then it is possible to quickly find a representation with a variable number of squares by reducing the number N with the square root function with a, the first square calculated as before.

Once we have a representation of a sum of n squares, we test it as usual by calculating the gcd's. If no factor is found, then instead of calculating another representation, we take one square from the previous sum, say b, and expand it into a sum of m squares. The b square will be replaced by m squares in the original sum. The obvious drawback is that the number of combinations to test will grow rapidly if no factor is found quickly.

I have not had a chance to test these ideas thoroughly like it was done with the sum of 4 squares method so at this point nothing can be said.

The other way to improve the method is to do a serious mathematical analysis of what is involved in factoring when using a sum of 4 squares. One can try to understand why some 4-sq reps lead to a factor and some don't. There is also the need to understand the distribution of the good representations (the ones that give a factor) within the set of a 4-sq sum of a given integer but also the order in which they appear. A major improvement will be to find a way to make the good representations appear at the beginning of the sum of 4 squares. Sadly, all this is beyond what I can do.[/QUOTE]

well my thought about all this is maybe learn more about modular arithmetic. I'll admit I may have made some errors in my modular arithmetic previously as well. modular arithmetic can help reduce cases usually though.

[QUOTE=mahbel;461850]After all, there is no theoretical justification (I know of) that only sums of 4 squares can be used to factor integers. [/quote]
Then why did you start this thread?!

[QUOTE=mahbel;461850]One may consider using sums of 5, 6 or more squares to factor. And here again, there is no theoretical justification that says sums of 5, 6,,,squares cannot factor integers.[/quote]
Before we proceed further, what is the theoretical justification that it has to be squares?

[QUOTE=mahbel;461850]I have not had a chance to test these ideas thoroughly like it was done with the sum of 4 squares method so at this point nothing can be said.[/quote]
You haven't tested _any_ of your ideas thoroughly. You have neither the mathematical ability to theoretically evaluate your methods, nor the computational know-how to empirically evaluate them. People have given hints about how to fix the latter, but you're hell bent on ignoring it.

In remarkes addressed to the OP:
[QUOTE=axn;461853]You haven't tested _any_ of your ideas thoroughly. You have neither the mathematical ability to theoretically evaluate your methods, nor the computational know-how to empirically evaluate them. People have given hints about how to fix the latter, but you're hell bent on ignoring it.[/QUOTE]
At least this thread is in the right part of the Forum
:missingteeth:

From the web site listed under the "Miscellaneous" heading, I offer

[quote]10 points for expecting others to disprove your result(s) rather than providing the proof yourself.
30 points for not knowing how or where to submit their major discovery for publication.
30 points for confusing examples and/or heuristics with mathematical proof.
50 points for failing to respond to appropriate corrections, questions and challenges.[/quote]

FWIW, I decided to practice at writing Pari scripts, to produce examples of odd numbers N which have [i]no[/i] representations as a sum of four squares which can be partitioned into two parts whose gcd is a proper factor of N. Such examples are quite easy to produce. Under the limit 10,000 the values

N = 77, 1457, 3901, 4661, 6557, 7597, 8549, and 9869

fill the bill. Let the OP try to use his "method" to factor any of these which are larger than 77...

[QUOTE=axn;461853]Then why did you start this thread?!

Before we proceed further, what is the theoretical justification that it has to be squares?

You haven't tested _any_ of your ideas thoroughly. You have neither the mathematical ability to theoretically evaluate your methods, nor the computational know-how to empirically evaluate them. People have given hints about how to fix the latter, but you're hell bent on ignoring it.[/QUOTE]
OP is simply using "decomposition into 4-squares" as a [B]very slow but sufficiently large volume* random number generator[/B].

______________________
*meaning that this generator will not run out of variants. So the factorization is solved by "reaching into the bingo cage" ridiculously many times.

[QUOTE=Dr Sardonicus;461869]In remarkes addressed to the OP:

At least this thread is in the right part of the Forum
:missingteeth:

From the web site listed under the "Miscellaneous" heading, I offer



FWIW, I decided to practice at writing Pari scripts, to produce examples of odd numbers N which have [I]no[/I] representations as a sum of four squares which can be partitioned into two parts whose gcd is a proper factor of N. Such examples are quite easy to produce. Under the limit 10,000 the values

N = 77, 1457, 3901, 4661, 6557, 7597, 8549, and 9869

fill the bill. Let the OP try to use his "method" to factor any of these which are larger than 77...[/QUOTE]

1457 = 31*47 = 36^2 + 11^2 + 6^2 + 2^2

factor: 36+11=47

1457 = 31*47 = 27^2 + 20^2 +18^2 +2^2

factor: 27+20=47

1457 = 31*47 = 30^2 + 21^2 + 10^2 + 4^2

factor: 21+10=31

I don't know if you need to see more ways to get a factor by combining non-squares (a,b,c,d). There may be a lot more. In fact, I quickly checked that there are more (30,20,11,6). I did not check if no combinations of squares could provide a factor. I also did not check if any mixed combinations ( squares + non squares) could provide a factor.

If you can give us a rational justification for why the above calculated factors must be rejected, then we will be very grateful.

[QUOTE=mahbel;461896]1457 = 31*47 = 36^2 + 11^2 + 6^2 + 2^2

factor: 36+11=47

1457 = 31*47 = 27^2 + 20^2 +18^2 +2^2

factor: 27+20=47

1457 = 31*47 = 30^2 + 21^2 + 10^2 + 4^2

factor: 21+10=31
[....]
If you can give us a rational justification for why the above calculated factors must be rejected, then we will be very grateful.[/QUOTE]
It's not the factors that are in question -- but rather, how you found them. You have given no indication that you actually found the factors using your method. For all anyone knows, you might have factored the numbers first by trial division, or looking them up in a factor table, and [i]then[/i] set about finding representations for which two of the square roots added up to one of the factors.

It might be interesting to see how quickly this "circular method" works -- that is, [i]start[/i] with a factor p, and see how long it takes to find a and b with

a + b = p, and N - a^2 - b^2 = c^2 + d^2.

[QUOTE=Dr Sardonicus;461898]It might be interesting to see how quickly this "circular method" works -- that is, [i]start[/i] with a factor p, and see how long it takes to find a and b with

a + b = p, and N - a^2 - b^2 = c^2 + d^2.[/QUOTE]

It's often impossible, but when possible it takes at most p factorization steps to find it by brute force. (For anyone else following along: you can check if a number is the sum of two squares by factoring it and seeing if it has any prime factors that are 3 mod 4 raised to an odd power, see [url=https://oeis.org/A001481]A001481[/url].)

[QUOTE=Dr Sardonicus;461898]It's not the factors that are in question --but rather, how you found them.

You have given no indication that you actually found the factors using your method.[/QUOTE]

How I found them was described before in one of my post. You take a 4-sq rep (a,b,c,d) and you combine the elements a,b,c,d, in this case the non-squares.
a+b, a+c, a+d, b+c, b+d, a+b+c, a+b+d, b+c+d and you calculate the gcd of these combinations.

There is a really simple way to see if I somehow cheated and invented these combinations that sum up to a factor. You just do it yourself. I can tell you that I used the online 4-sq reps calculator for which I provided the link before.

Now, if you want to impose limitations on how one can go about combining 4 different numbers in different ways, then please post your do's and dont's.

[QUOTE=CRGreathouse;461902]It's often impossible, but when possible it takes at most p factorization steps to find it by brute force. (For anyone else following along: you can check if a number is the sum of two squares by factoring it and seeing if it has any prime factors that are 3 mod 4 raised to an odd power, see [URL="https://oeis.org/A001481"]A001481[/URL].)[/QUOTE]

There are algorithms that can provide the decomposition of an integer N into a sum two squares which do not require factoring N.

Expanding Fermat's factorization method:

a+b | a^n + b^n
For all positive odd integers n.

Similarly, all positive even integers n, yield imaginary integer factors.

However, while true it has little practical value for large semi primes, due to "exponential" growth of powers.