mersenneforum.org The new strong (extended) factoring method using the 4-square representation of an integer.
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2017-06-19, 21:10   #78
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

11×461 Posts

Quote:
 Originally Posted by mahbel What right do you have to change the title of a thread started by another user?
See red color of poster's name. = supermod. If you wish to stick around here long enough to continue to reinvent your inefficient and ineffective method, you should strongly consider not picking fights with red folks.

There has been plenty of math shown in this thread for why your method (1) fails, and (2) is slower than trial division. There is nothing left for Batalov to demonstrate mathematically, so he chooses to point out that you're defending utter crap; you don't take the hint, so he's blunter than the rest of them. You should listen to him, really.

2017-06-19, 21:22   #79
CRGreathouse

Aug 2006

175B16 Posts

Quote:
 Originally Posted by mahbel You are right, 77 is a special case which is not factored by any of its 4-sq rep. However, if we use combinations of (a,b,c,d) instead of the squares (a^2,b^2,c^2,d^2), then we will be able to factor it.
OK, so here is the extended test. Where the original 'only' counted 7 cases, this one counts 18. (Someone should check that I've included all of them, and that I haven't included any twice.)

Code:
sqrtup(n)=n=ceil(n); if(issquare(n,&n),n,sqrtint(n)+1)
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";
But don't worry, if we find a number this can't factor we can just move to a double-extended test where include combinations like a + b^2 + d. I think that would require 72 tests in total. And if that doesn't work we can always use a triple-extended test which allows nonbinary coefficients, or cubes, or something.

My machine is busy with other work, but feel free to use this code to check for numbers this algorithm cannot factor.

 2017-06-19, 21:31 #80 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26×131 Posts @mahbel one thing you'll find when coding is efficiency is key. Any steps that can be decreased should be. One thing from your original post that still bugs me, is you are considering values that aren't primes multiplied by N. Is there a reason I'm not seeing because you can generate say any value that is a square times N, by multiplying by the square root all of a,b,c,d for N. You'll find a lot of them out ahead of time this works for finding at least a few of those. for example 3^2+5^2+7^2+11^2 = 204 ; 816 = 4*204 = 6^2+10^2+14^2+22^2 so some values of the multiplier you had out front don't really add much new information. Last fiddled with by science_man_88 on 2017-06-19 at 21:38
2017-06-19, 21:37   #81
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by mahbel If you have anything to say about the method, do it with math. Or is that too much to ask from you? How about you provide that counterexample yourself instead of waiting for someone else to stumble into one. Is-it because it is too complicated for you?
Serge is one of the computational heavies around here, if he's not computing it it's surely because he doesn't think it's worth his time. There's no question he could code something up (and get big iron to run it!) on if he really wanted to.

2017-06-19, 21:42   #82
Dr Sardonicus

Feb 2017
Nowhere

140D16 Posts

Quote:
 Originally Posted by mahbel If you have anything to say about the method, do it with math.
You first.

2017-06-19, 21:50   #83
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by Dr Sardonicus You first.
Actually I think you're the only one who has used real math in this thread so far, in your analysis (post #72) of the failure of the original algorithm. I just used cheap heuristics and decent algorithms.

2017-06-19, 23:44   #84
mahbel

Feb 2017
Kitchener, Ontario

22×3×5 Posts

Quote:
 Originally Posted by science_man_88 @mahbel one thing you'll find when coding is efficiency is key. Any steps that can be decreased should be. One thing from your original post that still bugs me, is you are considering values that aren't primes multiplied by N. Is there a reason I'm not seeing because you can generate say any value that is a square times N, by multiplying by the square root all of a,b,c,d for N. You'll find a lot of them out ahead of time this works for finding at least a few of those. for example 3^2+5^2+7^2+11^2 = 204 ; 816 = 4*204 = 6^2+10^2+14^2+22^2 so some values of the multiplier you had out front don't really add much new information.
You are asking about why I used a multiplier. I did some testing and found that some multipliers increase the number of good representations ( the ones that provide a factor(s)). If you use N=7*13=91, you get 2 good reps out a total of 8 reps. If you use 2N=2*7*13, you get about the same, slightly bigger 5 out of 17. If you use 3N, you get 12 good out of a total of 21 reps. Here you really see what increasing the value of the multiplier does. If you use 6N, you get 52 out of 63 or 82.5% of good reps. The problem with the multiplier is I couldn't figure out a general rule. So the same multiplier for one number N will not necessarily produce the same result for a different number M. I stuck with 2N more by habit than by anything else.

 2017-06-19, 23:49 #85 CRGreathouse     Aug 2006 3·1,993 Posts Honestly I think it's pretty hard to decide what multipliers are useful in general. The OLF paper tries to motivate the choice with some theory, I think, but ends up choosing a multiplier based on numerical experiments IIRC. Maybe some people know more -- Silverman, likely, and a number of experts we have on the forum -- but there's a lot of voodoo and trial-and-error.
2017-06-20, 00:09   #86
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by CRGreathouse Honestly I think it's pretty hard to decide what multipliers are useful in general. The OLF paper tries to motivate the choice with some theory, I think, but ends up choosing a multiplier based on numerical experiments IIRC. Maybe some people know more -- Silverman, likely, and a number of experts we have on the forum -- but there's a lot of voodoo and trial-and-error.
my main point was that if you have a representation for N you can make that into a representation for r^2 N of (ra,rb,rc,rd) and same happens to other multiplies that divide by squares at least some of their representations rely on representations of earlier multipliers.

so for example 612=12*51 and has 4 representations coming from 3*51=153 multiplying the bases by 2.

Last fiddled with by science_man_88 on 2017-06-20 at 00:10

2017-06-20, 00:12   #87
mahbel

Feb 2017
Kitchener, Ontario

1111002 Posts

Quote:
 Originally Posted by science_man_88 my main point was that if you have a representation for N you can make that into a representation for r^2 N of (ra,rb,rc,rd) and same happens to other multiplies that divide by squares at least some of their representations rely on representations of earlier multipliers. so for example 612=12*51 and has 4 representations coming from 3*51=153 multiplying the bases by 2.
I never considered square multipliers. I don't really see the point.

2017-06-20, 00:15   #88
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by mahbel I never considered square multipliers. I don't really see the point.
it doesn't just affect squares any multiplier that is not square-free is affected. also 4 in your 4p case is a square.

Last fiddled with by science_man_88 on 2017-06-20 at 00:27

 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 17:25.

Sat Dec 4 17:25:57 UTC 2021 up 134 days, 11:54, 1 user, load averages: 1.13, 1.34, 1.32