 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-14, 18:41 #1 mahbel   "mahfoud belhadj" Feb 2017 Kitchener, Ontario 748 Posts The new strong (extended) factoring method using the 4-square representation of an integer. We start with the well known representation of an integer N as a sum of 4 squares. It will be shown that it is possible to extract the factors of N themselves if we used the representation of N or 2N as a sum of 4 squares in a straightforward and efficient way. The following example will show how the method is implemented. We consider the representation of 2N as a sum of 4 squares (written as (x,y,z,t) without the exponent 2) and we will show below that we can in fact extract factors of 2N. We will see that we can easily find pairs or triplets of squares, which when added together, will make up numbers M(i) smaller than N ( since we gain nothing by adding the 4 squares ) that may share a factor with 2N. So when adding squares together ( pairs or triplets ), there is in theory nothing that will prevent us from running into one of those multiples of the smaller (or larger) factor. We know that there are many such numbers. If we write N=pq, we can also write N as a sum of p's q times (or q's p times) and this collection of p's can in turn form 2p,3p,4p... When we restrict ourselves at looking only at one number N=pq, we seriously restrict the chances of finding a factor. We need to consider all numbers p, 2p, 3p,...q, 2q,3q...that can help in the factoring of N=pq. There are 3 infinities and one finite set of numbers that meet exactly at N=pq. The infinity formed with multiples of q, the one formed with multiples of p and the one formed with numbers which have the same difference of factors (p-q). There is also a finite set of numbers that have the same sum (p+q) as N=pq. So by considering only N=pq, we are basically penalizing ourselves and severely limiting our ability to find a factor. We now give the 4-squares representation of 2N and we omit the exponent for simplicity. 2N=182=2*7*13=(7,9,6,4), (8,9,6,1), (8,10,3,3), (9,6,7,4), (9,6,8,1), (9,7,6,4), (9,8,6,1), (9,9,4,2), (9,10,1,0), (10,8,3,3), (10,9,1,0), (11,5,6,0), (11,6,4,3), (11,6,5,0), (12,5,3,2), (12,6,1,1), (13,3,2,0). We check one representation at a time: 182 = 7^2+9^2+6^2+4^2 = (7^2+9^2) + (6^2+4^2) = 130+52 = 2*5*13 + 4*13 But we also have: 182 = 7^2 + (9^2+6^2+4^2) = 7^2 + 133 = 7*7 + 7*19 For small numbers, we can immediately see that 130=10*13 and 52=4*13 or 7^2=7*7 so we may check 2N for divisibility by 13 and/or by 7. But for large numbers we need to use GCD (2N,130), GCD(2N,52), GCD(2N,49) and GCD(2N,133) to see that they share a factor beside the factor 2. Because we don't know which pair or triplet of squares is going to share a factor with 2N, we have to consider all the pairs of squares belonging to the same 4-square representation. So we write again: 182 = (7^2+6^2) + (9^2+4^2) = 85+7 = 5*17+97 182 = (7^2+4^2) + (9^2+6^2) = 65+117 = 5*13+9*13 = 14*13 = 2*7*13 =2N We see here that the same representation provided us with 6 numbers M=(130,52), (49,133), (65,117) that share a common factor with 2N (and N). (The elements of these 3 pairs are equidistant from N=91=7*13 and belong to the two infinities mentioned above). Once we have a factor, we can reduce N by that factor and check the new smaller N for primality. If the new N is a composite integer, we calculate its 4-squares representation and go through the same process. Out of the seventeen (17) 4-square representations of 2N, 5 provided us with a number M which shares a factor with 2N. So almost a third of the representations are good ones. They are (7,9,6,4), (8,9,6,1), (11,6,4,3), (12,5,3,2), (13,3,2,0). In the process of implementing the method, the only complex task was to find the 4- square representation of 2N without of course factoring N. The algorithm that was used to find those representations can be found here: http://www.mathcelebrity.com/foursquare.php?num=+91&pl=Show+Lagrange+Four-Square+Notation It is hard to guess how the algorithm will handle big numbers if one cannot conduct numerical experiments to find out. We were able to factor all small numbers (semi- primes) we considered with this method but since all the calculations were done by hand, that severely limits the conclusions one can draw from such a small sized sample. In principle, there is nothing to prevent us from factoring large numbers by considering their 4-square representations. The problem is that large composite integers have many 4-square representations and it will take a long time to generate them and test them for factors. We will provide ways to make the method more efficient in the comment section. Last fiddled with by mahbel on 2017-06-14 at 18:50   2017-06-14, 19:16 #2 VBCurtis   "Curtis" Feb 2005 Riverside, CA 3×1,667 Posts Choose a size of number worth factoring (say, 80 digits, or 100), and produce estimates for the number of possible a,b,c,d you would need to test for the 4-square representation. If you do this for each multiple of 20 digits from 20 to 100, you should have a pretty good idea of how your method scales with input size. There are many many factorization methods that use cute tricks for small numbers, but start to stumble for inputs as small as 10^10; by 10^20 they're intractable. So, how big is the solution-testing set for a-b-c-d if the input is 20 digits? 40? If it scales poorly, you won't need to bother with 80 or 100. Note that a 100-digit number of no special form can be factored in an hour or two on a multi-core consumer PC. Let's say 10,000 seconds of 10Ghz worth of computing (say, an older 4-core). That's 100 trillion operations, give or take a zero, to factor a 100-digit number. If you're at a trillion for a 40-digit number, that's bad.   2017-06-14, 19:41   #3
mahbel

Feb 2017
Kitchener, Ontario

748 Posts Quote:
 Originally Posted by VBCurtis Choose a size of number worth factoring (say, 80 digits, or 100), and produce estimates for the number of possible a,b,c,d you would need to test for the 4-square representation. If you do this for each multiple of 20 digits from 20 to 100, you should have a pretty good idea of how your method scales with input size.
I simply cannot code. I would have done that by now and more if I could.   2017-06-14, 21:35 #4 VBCurtis   "Curtis" Feb 2005 Riverside, CA 3·1,667 Posts You don't need to code to estimate the number of candidates! Example: The link you provided starts by enumerating candidates for a, which are between sqrt{n} /2 and sqrt{n}. You can look up the number of primes in that region for input 10^20: That is, find how many primes there are between 5*10^9 and 10^10. That's the number of a's you need to check/solve for b-c-d. This page provides the data you need: http://www.trnicely.net/pi/pix_0000.htm Looks like ~180 million candidate values for a. Note that link also provides estimation formulae for the number of primes less than a number, useful for performing these estimations for larger candidates. Now, using the algorithm you linked, how many items must be tested for b *for each a*? Let's set aside the number of CPU calculations for each of these trials, as we don't need to code anything to estimate how many items need be checked. So, no more excuses- do some estimating! "I can't code" is a favorite euphemism for "I am too lazy to find out how useless this is, someone do it for me." I've done 25% of your work, your turn.   2017-06-14, 23:09   #5
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

215210 Posts Quote:
 Originally Posted by mahbel I simply cannot code. I would have done that by now and more if I could.
You might want to look into Pari GP.
It's free, has arbitrary precision which means theoretically your integers can be as large as you wish 10s of thousands of decimal digits is available by default.
The online documentation is somewhat vague but manageable.

I haven't looked at your method on detail, but square/power related factorisation are normally used along with other methods in built in factoring algorithms in Pari GP.

One issue with them is that the gap between squares /powers grows astronomically large very fast as the integer ranges go high.

Last fiddled with by a1call on 2017-06-14 at 23:10   2017-06-15, 01:02 #6 science_man_88   "Forget I exist" Jul 2009 Dumbassville 203008 Posts to be fair I'd look more towards a codification of the steps needed ( if possible more broken down than in the OP). also I know I shouldn't but have you looked over all the sections of the Lagrange four square theorem Wikipedia page that would give you the number of representations that you seem to be having difficulty with or at least a way to classify which numbers are hardest to figure out. edit: and even before that you could use modular math and the pigeonhole principle to prove at least two of the squares have the same modular remainder mod 8. Last fiddled with by science_man_88 on 2017-06-15 at 01:20   2017-06-15, 06:39   #7
Batalov

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

22·2,393 Posts Quote:
 Originally Posted by mahbel We will provide ways to make the method more efficient in the comment section.
No you won't.
Quote:
 Originally Posted by mahbel I simply cannot code. I would have done that by now and more if I could.
q e d   2017-06-15, 10:58 #8 LaurV Romulan Interpreter   "name field" Jun 2011 Thailand 9,787 Posts There is nothing new with the method. Since antique times on this forum, when RDS used to live inside of it, there was a discussion (with him the main actor) about how one can factor a number if he can write is as a sum of two squares, in two ways. You can easily factor a number if you can write it as differences of squares, or if you can write it as a sum of two squares in two ways. Now, there is nothing magical in the number two, it is just that you need two equations to solve a system with two variables. Therefore, if you are able to write a number as a sum of three squares in three ways, it is a piece of cake to factor it. Also, write it as a sum of four squares in four different ways, and here you are... and so on and so forth... (well, you don't really need to go higher, as all numbers can be written as a sum of 4 squares, but sometimes it can be easier for you to write a number as a sum of 5 squares in 5 different ways, that it should be to write it as a sum of 4 squares in 4 different ways... ) The real question is how do you efficiently write the number as a sum of n squares in n different ways. If you can do that, you be millionaire tomorrow... Last fiddled with by LaurV on 2017-06-15 at 10:59   2017-06-15, 12:30   #9
mahbel

Feb 2017
Kitchener, Ontario

22·3·5 Posts Quote:
 Originally Posted by science_man_88 to be fair I'd look more towards a codification of the steps needed ( if possible more broken down than in the OP). also I know I shouldn't but have you looked over all the sections of the Lagrange four square theorem Wikipedia page that would give you the number of representations that you seem to be having difficulty with or at least a way to classify which numbers are hardest to figure out. edit: and even before that you could use modular math and the pigeonhole principle to prove at least two of the squares have the same modular remainder mod 8.
The major problem with the method is that it takes time to produce the 4-square representations as the numbers get larger and there is no known method to tell if a given representation is going to provide us with a factor. This means every 4-sq representation has to be tested. Nothing is known about the distribution of the "good 4-sq representations" (by good is meant the one which leads to a factor) within the set of the 4-sq representations of a given composite integer N.
The algorithm to calculate the 4-sq representation given in the original post:

http://www.mathcelebrity.com/foursqu...quare+Notation

was discussed on Stack Overflow and elsewhere

https://stackoverflow.com/questions/...uared-sum-to-n

Unfortunately, no efficient algorithm was found. So, if we still want to use a sum of squares factoring method, we need to find ways to make the method more efficient.

To answer your question, yes I read just about everything I could find about Lagrange 4-square theorem but it does not help with the implementation. Knowing the number of 4-sq representations of a number N does not help because we don't know which representation is going to provide a factor.   2017-06-15, 12:42   #10
mahbel

Feb 2017
Kitchener, Ontario

22·3·5 Posts Quote:
 Originally Posted by LaurV There is nothing new with the method. Since antique times on this forum, when RDS used to live inside of it, there was a discussion (with him the main actor) about how one can factor a number if he can write is as a sum of two squares, in two ways. ... The real question is how do you efficiently write the number as a sum of n squares in n different ways. If you can do that, you be millionaire tomorrow...
I think you are generalizing a known result for writing a number as a sum of 2 squares in 2 ways to sums of 3,4,...n squares without proof. I haven't seen a proof of your statement.

https://en.wikipedia.org/wiki/Euler%...ization_method

If it were true or that simple, someone would have done that a while ago, that is generalize the result valid for sum of 2 squares to sums of n squares.   2017-06-15, 13:04   #11
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts Quote:
 Originally Posted by mahbel I think you are generalizing a known result for writing a number as a sum of 2 squares in 2 ways to sums of 3,4,...n squares without proof. I haven't seen a proof of your statement. https://en.wikipedia.org/wiki/Euler%...ization_method If it were true or that simple, someone would have done that a while ago, that is generalize the result valid for sum of 2 squares to sums of n squares.
pythagorean triples could help in that in theory but it still won't find all of them I'd bet:

5^2+5^2+5^2 =5^2+5^2+3^2+4^2=5^2+3^2+4^2+3^2+4^2=3^2+4^2+3^2+4^2+3^2+4^2 each of those 4^2 can be broken down into 2^2+2^2+2^2+2^2 etc.

Quote:
 Originally Posted by mahbel To answer your question, yes I read just about everything I could find about Lagrange 4-square theorem but it does not help with the implementation. Knowing the number of 4-sq representations of a number N does not help because we don't know which representation is going to provide a factor.
I would argue it does in that if you were randomly generating them somehow you'd need a number to check when you have generated them all. the real useless part is you need the divisors first, that's the real problem with it. edit2: my point with the look at mod 8 was to limit the forms possible because for example squares can only be 0,1 or 4 mod 8 since 0 and 4 are even to get the odd values mod 8 we need a certain number of 1 mod 8 values etc.

1=1+0+0+0
3=1+1+1+0
5=1+4+0+0
7=1+1+1+4

so to add up to 7 mod 8 we need things like 3 squares that are 1 mod 8 and 1 that is 4 mod 8 etc.

Last fiddled with by science_man_88 on 2017-06-15 at 13:32   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:56.

Mon Oct 25 04:56:28 UTC 2021 up 93 days, 23:25, 0 users, load averages: 0.86, 0.95, 1.01 