mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-06-14, 18:41   #1
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

748 Posts
Default 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
mahbel is offline   Reply With Quote
Old 2017-06-14, 19:16   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

3×1,667 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2017-06-14, 19:41   #3
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

748 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.
mahbel is offline   Reply With Quote
Old 2017-06-14, 21:35   #4
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

3·1,667 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2017-06-14, 23:09   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

215210 Posts
Default

Quote:
Originally Posted by mahbel View Post
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
a1call is offline   Reply With Quote
Old 2017-06-15, 01:02   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

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
science_man_88 is offline   Reply With Quote
Old 2017-06-15, 06:39   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·2,393 Posts
Default

Quote:
Originally Posted by mahbel View Post
We will provide ways to make the method more efficient in the comment section.
No you won't.
Quote:
Originally Posted by mahbel View Post
I simply cannot code. I would have done that by now and more if I could.
q e d
Batalov is offline   Reply With Quote
Old 2017-06-15, 10:58   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

9,787 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2017-06-15, 12:30   #9
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

22·3·5 Posts
Default

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

22·3·5 Posts
Default

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

203008 Posts
Default

Quote:
Originally Posted by mahbel View Post
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 View Post
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
science_man_88 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:56.


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

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.