mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-06-23, 13:26   #122
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

22×3×5 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
mahbel is offline   Reply With Quote
Old 2017-06-23, 13:50   #123
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by mahbel View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-06-23, 14:12   #124
axn
 
axn's Avatar
 
Jun 2003

3·17·101 Posts
Default

Quote:
Originally Posted by mahbel View Post
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 View Post
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 View Post
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.
axn is online now   Reply With Quote
Old 2017-06-23, 15:42   #125
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·32·139 Posts
Default

In remarkes addressed to the OP:
Quote:
Originally Posted by axn View Post
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
Dr Sardonicus is offline   Reply With Quote
Old 2017-06-23, 16:14   #126
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×2,393 Posts
Default

Quote:
Originally Posted by axn View Post
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.
Batalov is offline   Reply With Quote
Old 2017-06-23, 19:33   #127
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

22·3·5 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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
mahbel is offline   Reply With Quote
Old 2017-06-23, 19:53   #128
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

116148 Posts
Default

Quote:
Originally Posted by mahbel View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2017-06-23, 20:38   #129
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.)
CRGreathouse is offline   Reply With Quote
Old 2017-06-23, 23:38   #130
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

22×3×5 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
mahbel is offline   Reply With Quote
Old 2017-06-23, 23:42   #131
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

22·3·5 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
mahbel is offline   Reply With Quote
Old 2017-06-24, 00:23   #132
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

23·269 Posts
Default

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
a1call is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A Sierpinski/Riesel-like problem sweety439 sweety439 1250 2021-10-01 12:53
Another factoring method rides the bus 3.14159 Factoring 233 2011-05-15 18:50
Square numbers and binary representation ET_ Miscellaneous Math 40 2010-06-06 12:55
Is this a feasible factoring method? 1260 Miscellaneous Math 46 2010-05-31 17:37
Representation of integer as sum of squares 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.