 mersenneforum.org The new strong (extended) factoring method using the 4-square representation of an integer.
 Register FAQ Search Today's Posts Mark Forums Read  2017-06-23, 13:26   #122
mahbel

Feb 2017
Kitchener, Ontario

22×3×5 Posts Quote:
 Originally Posted by CRGreathouse 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 do 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.
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.

https://cs.stackexchange.com/questio...-that-sum-to-n

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.

Last fiddled with by mahbel on 2017-06-23 at 13:27 Reason: correct spelling.   2017-06-23, 13:50   #123
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 Originally Posted by mahbel 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. https://cs.stackexchange.com/questio...-that-sum-to-n 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.
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.

Last fiddled with by science_man_88 on 2017-06-23 at 13:51   2017-06-23, 14:12   #124
axn

Jun 2003

3·17·101 Posts Quote:
 Originally Posted by mahbel After all, there is no theoretical justification (I know of) that only sums of 4 squares can be used to factor integers.
Then why did you start this thread?!

Quote:
 Originally Posted by mahbel 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.
Before we proceed further, what is the theoretical justification that it has to be squares?

Quote:
 Originally Posted by mahbel 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.
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.   2017-06-23, 15:42   #125
Dr Sardonicus

Feb 2017
Nowhere

22·32·139 Posts In remarkes addressed to the OP:
Quote:
 Originally Posted by axn 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.
At least this thread is in the right part of the Forum 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.
FWIW, I decided to practice at writing Pari scripts, to produce examples of odd numbers N which have no 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...

Last fiddled with by Dr Sardonicus on 2017-06-23 at 15:55   2017-06-23, 16:14   #126
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×2,393 Posts Quote:
 Originally Posted by axn 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.
OP is simply using "decomposition into 4-squares" as a very slow but sufficiently large volume* random number generator.

______________________
*meaning that this generator will not run out of variants. So the factorization is solved by "reaching into the bingo cage" ridiculously many times.   2017-06-23, 19:33   #127
mahbel

Feb 2017
Kitchener, Ontario

22·3·5 Posts Quote:
 Originally Posted by Dr Sardonicus In remarkes addressed to the OP: At least this thread is in the right part of the Forum 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 no 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...
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.

Last fiddled with by mahbel on 2017-06-23 at 19:41 Reason: added text   2017-06-23, 19:53   #128
Dr Sardonicus

Feb 2017
Nowhere

116148 Posts Quote:
 Originally Posted by mahbel 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.
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 then 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, start 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.   2017-06-23, 20:38   #129
CRGreathouse

Aug 2006

3·1,993 Posts Quote:
 Originally Posted by Dr Sardonicus It might be interesting to see how quickly this "circular method" works -- that is, start 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.
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 A001481.)   2017-06-23, 23:38   #130
mahbel

Feb 2017
Kitchener, Ontario

22×3×5 Posts Quote:
 Originally Posted by Dr Sardonicus 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.
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.   2017-06-23, 23:42   #131
mahbel

Feb 2017
Kitchener, Ontario

22·3·5 Posts Quote:
 Originally Posted by CRGreathouse 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 A001481.)
There are algorithms that can provide the decomposition of an integer N into a sum two squares which do not require factoring N.   2017-06-24, 00:23 #132 a1call   "Rashid Naimi" Oct 2015 Remote to Here/There 23·269 Posts 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. Last fiddled with by a1call on 2017-06-24 at 00:31   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 1250 2021-10-01 12:53 3.14159 Factoring 233 2011-05-15 18:50 ET_ Miscellaneous Math 40 2010-06-06 12:55 1260 Miscellaneous Math 46 2010-05-31 17:37 kpatsak Math 4 2007-10-29 17:53

All times are UTC. The time now is 04:11.

Mon Oct 25 04:11:28 UTC 2021 up 93 days, 22:40, 0 users, load averages: 1.70, 1.59, 1.38