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-24, 22:02   #155
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by Dr Sardonicus Here's another question: What's the theoretical justification for requiring that the four squares add up exactly to N? The reason I ask is, I thought of a way to speed up the process of using 4-tuples (a, b, c, d) to find factors of N: simply drop the requirement that a^2 + b^2 + c^2 + d^2 = N exactly. As long as a^2 + b^2 + c^2 + d^2 is close to N, go ahead and form the sums of some or all of a, b, c, d, a^2, b^2, c^2, and d^2, and take the gcd with N. (There are 127 nonempty sums.) I hypothesize that, there being so many possibilities, the chances are good that any factor of N under 100 will show up fairly quickly. I tried this idea with N = 1457 = 31*47, and the results were better than I expected. Even though a^2 + b^2 + c^2 + d^2 never hit N right on the nose, I still got at least one of the 15 sums of a, b, c, and d alone having a common factor with N in 6 of 8 tries. If anyone would care to have a go at my examples N = 77, 1457, 3901, 4661, 6557, 7597, 8549, and 9869 using this approach, have at them! I cheerfully proclaim that this approach really is nothing more than blazing away with a scattergun, in hopes that some of the buckshot will hit. The advantage over the OP's idea is, reloading is a whole lot quicker ;-)
my guess is so it's easier than the Mondrian art puzzle problem for the squares thing or that it's easier potentially than using cuboids to fill other cuboids etc. some numbers only have 2 factors so they can't be expressed as cuboids that don't have 2 side lengths of 1.
etc. I still don't see how you get 127 if you use n things for each part of the sum a sum of 4 things with n each will allow n^4 which 127 does not fit if you allow. yes I I know there's overlap I also know that some sums as squares aren't worth looking at for example for N=4 we have:

2^2+0^2+0^2+0^2
1^2+1^2+1^2+1^2

as well as these times -1 for all (a,b,c,d) (b,c,d,a) etc. some which use all negative numbers. it wasn't specified these wouldn't be used.

2017-06-24, 23:37   #156
Dr Sardonicus

Feb 2017
Nowhere

512510 Posts

Quote:
 Originally Posted by science_man_88 I still don't see how you get 127 if you use n things for each part of the sum
There are 8 terms a, b, c, d, a^2, b^2, c^2, d^2. The number of sums of these terms, each with coefficient either 1 or 0, is 2^8 or 128. The terms with coefficient 1 may be viewed as a subset of a set of 8 elements. The sum with all coefficients 0 corresponds to the empty set, and is of course 0. Similarly, there are 2^4 - 1 = 15 non-empty sums of the four roots a, b, c, and d.

Of course, not all of a, b, c, and d need be different. And even if they are, not all the sums need be different.

2017-06-25, 00:42   #157
Batalov

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

3×5×641 Posts

Quote:
 Originally Posted by Dr Sardonicus Here's another question: What's the theoretical justification for requiring that the four squares add up exactly to N? The reason I ask is, I thought of a way to speed up the process of using 4-tuples (a, b, c, d) to find factors of N: simply drop the requirement that a^2 + b^2 + c^2 + d^2 = N exactly. As long as a^2 + b^2 + c^2 + d^2 is close to N, go ahead ... I cheerfully proclaim that this approach really is nothing more than blazing away with a scattergun, in hopes that some of the buckshot will hit. The advantage over the OP's idea is, reloading is a whole lot quicker ;-)
Great thinking, Doctor!

The next beautiful enhancement is to drop the requirement that a^2 + b^2 + c^2 + d^2 is close to N. And then again, what is 'close' anyway? I think 17 and 998651 are reasonably close, at least from where I sit (which is at 150-290-digit numbers).

And yet the next enhancement (because now the a^2 + b^2 + c^2 + d^2 can be equal to anything) is to restate: "Take any random a, b, c, d of size of sqrt(N), then do gcd(N, all linear combinations of {a, b, c, d and a^2, b^2, c^2, d^2} ). Repeat N times if needed. I guarantee that you will factor N." Scout's honor! In fact you will factor N faster, because you will not be uselessly check if a^2 + b^2 + c^2 + d^2 is equal (or close) to N.

 2017-06-25, 00:50 #158 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 2×23×137 Posts Long ago in this thread it was already apparent that using a^2 + b^2 + c^2 + d^2 = N fails the sufficiency test. And now it appears that using a^2 + b^2 + c^2 + d^2 = N also fails the necessity test. Yay. So after all the posts here we can can finally ignore the big distraction about bothering to test for a^2 + b^2 + c^2 + d^2 = N and instead just use a bunch of random numbers. Conclusion at last. End of thread. Last fiddled with by retina on 2017-06-25 at 00:51
2017-06-25, 02:56   #159
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by retina Long ago in this thread it was already apparent that using a^2 + b^2 + c^2 + d^2 = N fails the sufficiency test. And now it appears that using a^2 + b^2 + c^2 + d^2 = N also fails the necessity test. Yay. So after all the posts here we can can finally ignore the big distraction about bothering to test for a^2 + b^2 + c^2 + d^2 = N and instead just use a bunch of random numbers. Conclusion at last. End of thread.
In fairness I mentioned this on page 3 and showed how much faster it was.

Quote:
 Originally Posted by Dr Sardonicus Here's another question: What's the theoretical justification for requiring that the four squares add up exactly to N? The reason I ask is, I thought of a way to speed up the process of using 4-tuples (a, b, c, d) to find factors of N: simply drop the requirement that a^2 + b^2 + c^2 + d^2 = N exactly. As long as a^2 + b^2 + c^2 + d^2 is close to N, go ahead and form the sums of some or all of a, b, c, d, a^2, b^2, c^2, and d^2, and take the gcd with N. (There are 127 nonempty sums.) I hypothesize that, there being so many possibilities, the chances are good that any factor of N under 100 will show up fairly quickly. I tried this idea with N = 1457 = 31*47, and the results were better than I expected. Even though a^2 + b^2 + c^2 + d^2 never hit N right on the nose, I still got at least one of the 15 sums of a, b, c, and d alone having a common factor with N in 6 of 8 tries. If anyone would care to have a go at my examples N = 77, 1457, 3901, 4661, 6557, 7597, 8549, and 9869 using this approach, have at them! I cheerfully proclaim that this approach really is nothing more than blazing away with a scattergun, in hopes that some of the buckshot will hit. The advantage over the OP's idea is, reloading is a whole lot quicker ;-)
Here's one implementation of your approach:
Code:
scattergun(n)=my(s=sqrtint(n),a2,b2,c2,d2,g); for(a=s\2,n, a2=a^2; for(b=a,s, b2=b^2; for(c=b,s, c2=c^2; for(d=c,s, g=gcd(n,a); if(g>1, return(g)); g=gcd(n,b); if(g>1, return(g)); g=gcd(n,c); if(g>1, return(g)); g=gcd(n,d); if(g>1, return(g)); g=gcd(n,a2+b2); if(g>1 && g<n, return(g)); g=gcd(n,a2+c2); if(g>1 && g<n, return(g)); d2=d^2; g=gcd(n,a2+d2); if(g>1 && g<n, return(g)); g=gcd(n,a+b); if(g>1 && g<n, return(g)); g=gcd(n,a+c); if(g>1 && g<n, return(g)); g=gcd(n,a+d); if(g>1 && g<n, return(g)); g=gcd(n,b+c); if(g>1 && g<n, return(g)); g=gcd(n,b+d); if(g>1 && g<n, return(g)); g=gcd(n,c+d); if(g>1 && g<n, return(g)); g=gcd(n,a+b+c); if(g>1 && g<n, return(g)); g=gcd(n,a+b+d); if(g>1 && g<n, return(g)); g=gcd(n,a+c+d); if(g>1 && g<n, return(g)); g=gcd(n,b+c+d); if(g>1 && g<n, return(g)); g=gcd(n,a+b+c+d); if(g>1 && g<n, return(g)))))); "could not factor";
For comparison, the other methods:

Code:
factorblind(n)=my(s=(sqrtint(n)-3)\2,r); while(n%(r=2*random(s)+3),); r;
sqrtup(n)=n=ceil(n); if(issquare(n,&n),n,sqrtint(n)+1);
mahbel(n)=my(a2,b2,c2,d,d2,g); for(a=sqrtup(n/4),sqrtint(n), a2=a^2; for(b=sqrtup((n-a2)/3),min(sqrtint(n-a2),a), b2=b^2; for(c=sqrtup((n-a2-b2)/2),min(sqrtint(n-a2-b2),b), c2=c^2; if(issquare(n-a2-b2-c2,&d)&&c>=d, d2=d^2; g=gcd(n,a); if(g>1 && g<n, return(g)); g=gcd(n,b); if(g>1 && g<n, return(g)); g=gcd(n,c); if(g>1 && g<n, return(g)); g=gcd(n,d); if(g>1 && g<n, return(g)); g=gcd(n,a2+b2); if(g>1 && g<n, return(g)); g=gcd(n,a2+c2); if(g>1 && g<n, return(g)); g=gcd(n,a2+d2); if(g>1 && g<n, return(g)))))); "could not factor";
mahbelExtended(n)=my(a2,b2,c2,d,d2,g); for(a=sqrtup(n/4),sqrtint(n), a2=a^2; for(b=sqrtup((n-a2)/3),min(sqrtint(n-a2),a), b2=b^2; for(c=sqrtup((n-a2-b2)/2),min(sqrtint(n-a2-b2),b), c2=c^2; if(issquare(n-a2-b2-c2,&d)&&c>=d, d2=d^2; g=gcd(n,a); if(g>1 && g<n, return(g)); g=gcd(n,b); if(g>1 && g<n, return(g)); g=gcd(n,c); if(g>1 && g<n, return(g)); g=gcd(n,d); if(g>1 && g<n, return(g)); g=gcd(n,a2+b2); if(g>1 && g<n, return(g)); g=gcd(n,a2+c2); if(g>1 && g<n, return(g)); g=gcd(n,a2+d2); if(g>1 && g<n, return(g)); g=gcd(n,a+b); if(g>1 && g<n, return(g)); g=gcd(n,a+c); if(g>1 && g<n, return(g)); g=gcd(n,a+d); if(g>1 && g<n, return(g)); g=gcd(n,b+c); if(g>1 && g<n, return(g)); g=gcd(n,b+d); if(g>1 && g<n, return(g)); g=gcd(n,c+d); if(g>1 && g<n, return(g)); g=gcd(n,a+b+c); if(g>1 && g<n, return(g)); g=gcd(n,a+b+d); if(g>1 && g<n, return(g)); g=gcd(n,a+c+d); if(g>1 && g<n, return(g)); g=gcd(n,b+c+d); if(g>1 && g<n, return(g)); g=gcd(n,a+b+c+d); if(g>1 && g<n, return(g)))))); "could not factor";
mahbelDoubleExtended(n)=my(a2,b2,c2,d,d2,g); for(a=sqrtup(n/4),sqrtint(n), a2=a^2; for(b=sqrtup((n-a2)/3),min(sqrtint(n-a2),a), b2=b^2; for(c=sqrtup((n-a2-b2)/2),min(sqrtint(n-a2-b2),b), c2=c^2; if(issquare(n-a2-b2-c2,&d)&&c>=d, d2=d^2; g=gcd(n,a); if(g>1, return(g));g=gcd(n,b); if(g>1, return(g));g=gcd(n,c); if(g>1, return(g));g=gcd(n,d); if(g>1, return(g));g=gcd(n,a2+b2); if(g>1 && g<n, return(g));g=gcd(n,a2+c2); if(g>1 && g<n, return(g));g=gcd(n,a2+d2); if(g>1 && g<n, return(g));g=gcd(n,c+d); if(g>1 && g<n, return(g));g=gcd(n,c+d2); if(g>1 && g<n, return(g));g=gcd(n,c2+d); if(g>1 && g<n, return(g));g=gcd(n,b+d); if(g>1 && g<n, return(g));g=gcd(n,b+d2); if(g>1 && g<n, return(g));g=gcd(n,b+c); if(g>1 && g<n, return(g));g=gcd(n,b+c+d); if(g>1 && g<n, return(g));g=gcd(n,b+c+d2); if(g>1 && g<n, return(g));g=gcd(n,b+c2); if(g>1 && g<n, return(g));g=gcd(n,b+c2+d); if(g>1 && g<n, return(g));g=gcd(n,a2+b2-b); if(g>1 && g<n, return(g));g=gcd(n,b2+d); if(g>1 && g<n, return(g));g=gcd(n,b2+c); if(g>1 && g<n, return(g));g=gcd(n,b2+c+d); if(g>1 && g<n, return(g));g=gcd(n,a2+c2-c); if(g>1 && g<n, return(g));g=gcd(n,a2+d2-d); if(g>1 && g<n, return(g));g=gcd(n,a+d); if(g>1 && g<n, return(g));g=gcd(n,a+d2); if(g>1 && g<n, return(g));g=gcd(n,a+c); if(g>1 && g<n, return(g));g=gcd(n,a+c+d); if(g>1 && g<n, return(g));g=gcd(n,a+c+d2); if(g>1 && g<n, return(g));g=gcd(n,a+c2); if(g>1 && g<n, return(g));g=gcd(n,a+c2+d); if(g>1 && g<n, return(g));g=gcd(n,a2-a+b2); if(g>1 && g<n, return(g));g=gcd(n,a+b); if(g>1 && g<n, return(g));g=gcd(n,a+b+d); if(g>1 && g<n, return(g));g=gcd(n,a+b+d2); if(g>1 && g<n, return(g));g=gcd(n,a+b+c); if(g>1 && g<n, return(g));g=gcd(n,a+b+c+d); if(g>1 && g<n, return(g));g=gcd(n,a+b+c+d2); if(g>1 && g<n, return(g));g=gcd(n,a+b+c2); if(g>1 && g<n, return(g));g=gcd(n,a+b+c2+d); if(g>1 && g<n, return(g));g=gcd(n,a2-a+b2-b); if(g>1 && g<n, return(g));g=gcd(n,a+b2); if(g>1 && g<n, return(g));g=gcd(n,a+b2+d); if(g>1 && g<n, return(g));g=gcd(n,a2-a+c2); if(g>1 && g<n, return(g));g=gcd(n,a+b2+c); if(g>1 && g<n, return(g));g=gcd(n,a+b2+c+d); if(g>1 && g<n, return(g));g=gcd(n,a2-a+c2-c); if(g>1 && g<n, return(g));g=gcd(n,a2-a+d2); if(g>1 && g<n, return(g));g=gcd(n,a2-a+d2-d); if(g>1 && g<n, return(g));g=gcd(n,a2-a); if(g>1 && g<n, return(g));g=gcd(n,a2+d); if(g>1 && g<n, return(g));g=gcd(n,a2+c); if(g>1 && g<n, return(g));g=gcd(n,a2+c+d); if(g>1 && g<n, return(g));g=gcd(n,b2+c2-c); if(g>1 && g<n, return(g));g=gcd(n,b2+d2-d); if(g>1 && g<n, return(g));g=gcd(n,a2+b); if(g>1 && g<n, return(g));g=gcd(n,a2+b+d); if(g>1 && g<n, return(g));g=gcd(n,b2-b+c2); if(g>1 && g<n, return(g));g=gcd(n,a2+b+c); if(g>1 && g<n, return(g));g=gcd(n,a2+b+c+d); if(g>1 && g<n, return(g));g=gcd(n,b2-b+c2-c); if(g>1 && g<n, return(g));g=gcd(n,b2-b+d2); if(g>1 && g<n, return(g));g=gcd(n,b2-b+d2-d); if(g>1 && g<n, return(g));g=gcd(n,b2-b); if(g>1 && g<n, return(g));g=gcd(n,c2+d2-d); if(g>1 && g<n, return(g));g=gcd(n,c2-c+d2); if(g>1 && g<n, return(g));g=gcd(n,c2-c+d2-d); if(g>1 && g<n, return(g));g=gcd(n,c2-c); if(g>1 && g<n, return(g));g=gcd(n,d2-d); if(g>1 && g<n, return(g)))))); "could not factor";
Now, let's write some code to compare them, along with two standard methods for comparison:
Code:
rsp(len)=my(mn=10^(len-1),mx=10^len-1,p=randomprime([sqrtup(mn/2),sqrtint(mx)]),q=randomprime([ceil(mn/p),mx\p])); p*q;
trialDivision(n)=forprime(p=2,sqrtint(n), if(n%p==0, return(p))); n;
gpf(n)=my(f=factor(n)[,1]); f[#f];
test(len,trials,methods)=my(v=vector(trials,i,rsp(len)),t); for(i=1,#methods, gettime(); print1("Method #"i" factored "sum(j=1,#v,t=methods[i](v[j]); type(t)=="t_INT" && t>1 && t<v[j] && v[j]%t==0)); print(" "len"-digit numbers in "gettime()" ms."))
test(9, 10, [gpf, trialDivision, factorblind, scattergun, mahbelDoubleExtended, mahbelExtended, mahbel])
Here are the results so far. I've substituted the names for easier reading. Note that all methods get exactly the same numbers to factor.

PARI's internal algorithms factored 10 9-digit numbers in 0 ms.
Trial division factored 10 9-digit numbers in 4 ms.
Guessing random factors (factorblind) factored 10 9-digit numbers in 52 ms.
Searching nearby squares and nonsquares (Dr Sardonicus's scattergun) factored 10 9-digit numbers in 120 ms.
Searching squares, nonsquares, and their combinations (mahbel's double extended method) factored 10 9-digit numbers in 12677 ms.
Searching squares and nonsquares (mahbel's extended method) factored 10 9-digit numbers in 94905 ms.
Searching squares (mahbel's method) factored 10 9-digit numbers in 268852 ms.

So, the takeaways:
• These numbers are really small. I wasn't able to go much higher because the methods were too slow.
• Overhead matters a lot. My stupid method is twice as fast as Dr Sardonicus's stupid method just because mine does less work and so it spends more time searching.
• Contrary to my expectations, the extensions helped a lot. I think that's because the algorithm I'm using for four-square representations is slow and the more checks you do inside of each one you find, the better (because each one is expensive to find).
• It should surprise no one that all methods were much slower than trial division, which is much slower than a real method.

2017-06-25, 06:18   #160
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

2×23×137 Posts

Quote:
 Originally Posted by CRGreathouse In fairness I mentioned this on page 3 and showed how much faster it was.
Okay, sorry. I didn't mean to ignore any particular poster. I haven't been following this thread all that closely though so it is just my inattention, not any malicious intent.

2017-06-25, 06:22   #161
CRGreathouse

Aug 2006

175B16 Posts

Quote:
 Originally Posted by retina Okay, sorry. I didn't mean to ignore any particular poster. I haven't been following this thread all that closely though so it is just my inattention, not any malicious intent.
Oh, no offense taken at all -- just a pointer if you were interested.

I freely admit, as I have each time performance was mentioned, that the comparison would look less bad if I had a faster method for finding four-square representations. But I think that even if they were already in the L1 cache the speed would be inferior to a properly-coded trial division, let alone Pollard rho.

2017-06-25, 07:04   #162
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

24·613 Posts

Quote:
 Originally Posted by Dr Sardonicus Here's another question: What's the theoretical justification for requiring that the four squares add up exactly to N? The reason I ask is, I thought of a way to speed up the process of using 4-tuples (a, b, c, d) to find factors of N: simply drop the requirement that a^2 + b^2 + c^2 + d^2 = N exactly. As long as a^2 + b^2 + c^2 + d^2 is close to N, go ahead and form the sums of some or all of a, b, c, d, a^2, b^2, c^2, and d^2, and take the gcd with N. (There are 127 nonempty sums.)
haha, brilliant! Very good posting.
I still don't understand why you say "close to N", any sum will do it

(edit whoops, Serge was faster, as usual...)

Last fiddled with by LaurV on 2017-06-25 at 07:06

2017-06-25, 13:07   #163
Dr Sardonicus

Feb 2017
Nowhere

512510 Posts

Quote:
 Originally Posted by Batalov And yet the next enhancement (because now the a^2 + b^2 + c^2 + d^2 can be equal to anything) is to restate: "Take any random a, b, c, d of size of sqrt(N), then do gcd(N, all linear combinations of {a, b, c, d and a^2, b^2, c^2, d^2} ). Repeat N times if needed. I guarantee that you will factor N." Scout's honor! In fact you will factor N faster, because you will not be uselessly check if a^2 + b^2 + c^2 + d^2 is equal (or close) to N.
I agree, this would be faster. My only real concern was that a, b, c, d not be too small, and your condition sees to that.

It might even give the checking of random numbers up to sqrt(N) a run for its money

2017-06-25, 15:58   #164
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,087 Posts

Finding a geometric solution to forming a rectangle out of any given 4 squares is possible in the classical sense of using a compass and a straight-edge.
It's algebraic equivalent its:

x = (a^2 + b^2 + c^2 + d^2) / m

x is a constructible number. However it does not have to be an integer for integers a,b,c,d,m.
So it cannot be a basis for factorization without other constraints which ensue integer-ness.

https://en.m.wikipedia.org/wiki/Constructible_number

ETA
Quote:
 Such a number is constructible if and only if the denominator of the fully reduced multiple is a power of 2 or the product of a power of 2 with the product of one or more distinct Fermat primes.
So if I'm not mistaking if m.x happens to have any factors of combinations of Fermat primes (skipping powers of 2), there should be a geometric solution. Very narrow set, however wider sets would not be impossible. However the only ones I can think of are equivalent to Factorials and GCD which are way too complicated to be practical.

Last fiddled with by a1call on 2017-06-25 at 16:34

2017-06-25, 18:02   #165
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by a1call Finding a geometric solution to forming a rectangle out of any given 4 squares is possible in the classical sense of using a compass and a straight-edge. It's algebraic equivalent its: x = (a^2 + b^2 + c^2 + d^2) / m x is a constructible number. However it does not have to be an integer for integers a,b,c,d,m. So it cannot be a basis for factorization without other constraints which ensue integer-ness.
I don't know what m is or why it is needed. But couldn't you just scale the grid by a factor of m and use smaller squares?

 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 10:26.

Wed Dec 1 10:26:46 UTC 2021 up 131 days, 4:55, 1 user, load averages: 1.00, 1.12, 1.14