P-1 factorer

[jjjjL]

i'm gonna skip through explaining what this is and get right to what i'm up to.

basically, i hacked up the GIMPS P-1 factoring code and made it do proth numbers. well, maybe.

the thing is, I haven't been able to do much serious testing of it because i have no way to know what it should find for which values.

it has found factors on some numbers but all of them are rather trivial factors (ie 5, 7, 11).

if you know how to test this, download it and report back when you get some results. i'd be very impressed if you found a factor for a currently unfactored number around n=4M.

program syntax is:

ecm.exe <k> <n-start> <n-quit> <B1> <B2>

so if you wanted to check 4847*2^4000000+1, you'd do

ecm.exe 4847 4000000 4000001 1000000 40000000

if you make n-quit larger by more than 1, it will step though multiple "n" as a quick way to batch things for testing.

you'll probably have to know a bit about P-1 factoring to test this correctly. if you feel you know a lot and have visual studio installed, email me and i'll send you the code for you to look though. it's a derivative of what's contained in emc.c in the GIMPS source located at http://www.mersenne.org/gimps/source23.zip

so let me know if you think this works.

http://www-personal.engin.umich.edu/...20factorer.zip

[biwema]

Hi Louie

it's a good idea to adapt the gimps p-1 code for sierpinski factoring.
Well done!

Nevertheless, I think, something does not work optimally, but I don't know what.

ecm.exe 24737 4559143 4559144 8000 250000

should find

factor: 1000225084123
(1000225084122 = 2*3*3*3*11*7523*223831)

but it does not find it.
i jusi tried to rediscover that factor for testing purposes.

biwema

[jjjjL]

thanks biwema, that's a good test point.

i'm not too surprised it's not working. i haven't been able to make it find anything larger than 17 so far.

i've verified that it is calculating the proth number right. there must be something else flawed about how it's doing the calculations.

do you know by chance what values should be getting passed to the gcd calls for your test number? if i knew some intermediate numbers, it might be easier to figure out where things are going wrong.

is there another P-1 factoring package available to compare it to (or use instead)?

-Louie

[smh]

The GMP-ECM client can also do P-1 (and P+1). On my PC it crashes when trying it on large numbers but it might help you to figure how the algorithem works.

Source can be found here

[jjjjL]

do you know of a large number expression converter so i can create files with the numbers in them?

it looks like EMCnet has no expression input. in any case i know a utility like this exists, i just can't find it. can you point me at one so i don't have to write it.

-Louie

actually, i'll probably just build a new version of emcnet that accepts k/n instead of regular numbers.

[wblipp]

Originally posted by smh
The GMP-ECM client can also do P-1 (and P+1). On my PC it crashes when trying it on large numbers but it might help you to figure how the algorithem works.

Source can be found here

The crashing on large numbers happens because the standard build uses the local memory stack, and this overflows when storing large numbers. According to Paul Zimmermann, the author of GMP-ECM, to build using other memory techniques "use configure --disable-alloca". I don't have a C compiler; I'd be thankful if someone with a C compiler would make available a version of GMP-ECM 5.0 or 5.1-beta that works on Win2K with SoB sized numbers.

Other people asked about this problem and got the diagnosis from Paul Leyland here .

[jjjjL]

Originally posted by wblipp
The crashing on large numbers happens because the standard build uses the local memory stack, and this overflows when storing large numbers. According to Paul Zimmermann, the author of GMP-ECM, to build using other memory techniques "use configure --disable-alloca". I don't have a C compiler; I'd be thankful if someone with a C compiler would make available a version of GMP-ECM 5.0 or 5.1-beta that works on Win2K with SoB sized numbers.

Other people asked about this problem and got the diagnosis from Paul Leyland here .

i'm currently playing with GMP 4.1.2 and ECM 5.0 in cygwin right now.

i just got to the crashing part. it wouldn't handle exponents much larger than 100000. having used GMP for the orginal SB, i do remember that configure line. it will take me awhile to rebuild gmp but i'll give that a try. thanks.

-Louie

[jjjjL]

ok, here's a special version of GMP-ECM that was built with the --disable-alloca.

it also accepts slightly modified files... rather than each line being a number, it pulls numbers in pairs. the first line holds the k, the second the n value. i haven't tried it with multiple values but there's no reason to think it wouldn't work.

i'm gonna add progress reporting to it now. it may not crash, but it doesn't seem very fast either.

-Louie

http://www-personal.engin.umich.edu/...win-athlon.zip

[rosebud]

ok, tried it with k:24737 n:4559143

this output seems to be right:
GMP-ECM 5.0 [powered by GMP 4.1.2] [ECM]
Input number has 1372444 digits
Using B1=8000, B2=230000, polynomial x^1, sigma=3668824256

but then very soon it's crashing...

Exception: STATUS_STACK_OVERFLOW at eip=00427603
eax=0002F8A0 ebx=007AF658 ecx=005B14A0 edx=007AF64C esi=007AF610 edi=00022C8A
ebp=007AF4C8 esp=007AF498 program=C:\EIGENE DATEIEN\ECM-PROTHNUMBER-CYGWIN-ATHLON\ECM.EXE
cs=016F ds=0177 es=0177 fs=14F7 gs=0000 ss=0177
Stack trace:
Frame Function Args
007AF4C8 00427603 (00FDC058, 00C99310, 00A6CA58, 00DAF790)
007AF4F8 0040E961 (007AF550, 007AF64C, 007AF658, 007AF610)
007AF578 00401509 (007AFBC0, 007AF5F8, 007AF5E0, 007AFBF0)
007AF688 0040321F (007AFBC0, 007AFC00, 007AFBF0, 007AFBD0)
007AFC28 0040809E (00000004, 009E0478, 009E0328, 81976C98)
007AFDB8 610073E8 (610C39E8, FFFFFFFE, 00000014, 610C390C)
007AFE08 610076CD (00000000, 00000000, BFFBB490, 007AFF68)
007AFE28 00427672 (00407A60, 037F0500, 007AFF78, BFF7B9E4)
007AFE38 0040103C (00000000, 81976C98, 005A0000, 006D6345)
007AFF78 BFF7B9E4 (819672B0, 00000008, 81976C98, 00000000)
46465 [main] ECM 514743 handle_exceptions: Exception: STATUS_ACCESS_VIOLATION
47048 [main] ECM 514743 handle_exceptions: Error while dumping state (probably corrupted stack)

[wblipp]

Originally posted by jjjjL
ok, here's a special version of GMP-ECM that was built with the --disable-alloca.

it also accepts slightly modified files... rather than each line being a number, it pulls numbers in pairs. the first line holds the k, the second the n value.

I think GMP-ECM has expression expansion already. At least the 5.1-beta that I got from the Yahoo PrimeNumbers Group would accept expressions like 4847*2^300087+1.

[jjjjL]

well, it did successfully factor 22699*2^2946070+1 after about 1.5 hours. for all i know, it spent the majority of that time printing the cofactor (stupid program printing a 1 million digit number).

B1 = 2500 B2 = 2500

produces the factor

1000809717779 = 2 x 13 x 71 x 131 x 1933 x 2141 + 1

when the P-1 factorer for GIMPS works, does anyone know how long it would take it to perform a similar sized test?

-Louie

ps - i get a seg fault when trying that other larger number too.

[Moo_the_cow]

I don't think that there should even be a P-1 factorer
existing right now, because it seems much more efficient
to simultaneously sieve >500,000 numbers than to sieve
one.

[jjjjL]

Originally posted by Moo_the_cow
I don't think that there should even be a P-1 factorer
existing right now, because it seems much more efficient
to simultaneously sieve >500,000 numbers than to sieve
one.

i thought that for awhile too.

but once the tests get assigned, it's too late for a factor. and contrary to some people's suggestions, factors NEVER come in while tests are pending. it hasn't happened yet. either the factor gets in before the test gets assigned, or it comes in after it's been finished. so that means that it is going to take someone 3-5 days to test the number if the server gets to it before it's factored.

so it makes sense to spend some portion of 3-5 days trying to factor the number with P-1 or P+1 factoring. the P-1 factoring is going to find factors that we won't find with regular sieveing for years. so if it only takes a couple hours to factor down a number before it gets assigned, that's worth it. as long as the probablity of finding a factor times the time it takes to find them is less then the time it would take to run a primality test, it's better. in fact, since a factor is even better than a proth test (no double check ever required), it may be better to factor this way when possible.

the real problem is making an efficient program to do the factoring. GMP-EMC seems a little weak. looking at the code, there are a bunch of places where things could be optimized. their implementation is so general (and in my opinion, naive) that they could be improved by even a novice programmer. BTW, no disrespect to the authors of GMP-EMC... let it be known, Paul Zimmerman is godlike. But this is the first version to have P-1/+1 factoring so it's not as well tuned as you might expect.

George Woltman has suggested that very little needs to be done to his publically available code to make it work for our purposes. i'm trying to port it and so is another group. no luck there yet. maybe someone here can do it.

either package would be a nice place to start. i wouldn't be surprised if someone here wrote their own that was better than both (or at least GMP-EMC).

we'll have to see who steps up to help. it certainly would be fun to have a "P-1 factor coordination" thread.

-Louie

[jjjjL]

well, this version is at least capable of doing larger numbers.

55459
4000006

produced:

$ ./ecm.exe -pm1 105 1150 < input.txt
GMP-ECM 5.0 [powered by GMP 4.1.2] [P-1]
Input number has 1204127 digits
Using B1=105, B2=1150, polynomial Dickson(4), x0=4059057736
Step 1 took 1202580ms
Step 2 took 2614118ms
********** Factor found in step 2: 18437164305601
Found probable prime factor of 14 digits: 18437164305601

that looks like a 18T factor in 1 hour. it's a lot easier when you know where they are.

this does give me hope that it may be useful for cracking a real unknown factor too. after some optimizations anyway. anyone got a speed comparison yet to gimps yet? what does that take to do the same exp to those depths? probably not an hour.

-Louie

[wblipp]

Originally posted by jjjjL
it certainly would be fun to have a "P-1 factor coordination" thread.

It's an interesting design question whether P-1 (and possibly P+1) factoring should be done separately, like sieving, or should be integrated into the SoB client to be performed automatically as part of every test.

One advantage of integration is that the testing will always be delayed until the last possible moment, so there is every opportunity for a sieving factor to arrive first.

One advantage of separate tests is that stage 2 of P-1 and P+1 tests work best with large amounts of memory, so we could dedicate big memory machines to this testing.

Another interesting design issue will be determining our optimization points. Our optimization points should be different from GIMPS because they always need a double check and we don't really know how much double checking we will be doing.

[jjjjL]

Originally posted by wblipp
It's an interesting design question whether P-1 (and possibly P+1) factoring should be done separately, like sieving, or should be integrated into the SoB client to be performed automatically as part of every test.

One advantage of integration is that the testing will always be delayed until the last possible moment, so there is every opportunity for a sieving factor to arrive first.

One advantage of separate tests is that stage 2 of P-1 and P+1 tests work best with large amounts of memory, so we could dedicate big memory machines to this testing.

Another interesting design issue will be determining our optimization points. Our optimization points should be different from GIMPS because they always need a double check and we don't really know how much double checking we will be doing.

i think it will be best to start it out kinda like sieving and then make it a server project. probably seperate but i'm not sure. we'll see.

-Louie

[smh]

this does give me hope that it may be useful for cracking a real unknown factor too. after some optimizations anyway. anyone got a speed comparison yet to gimps yet?

Don't forget that GIMPS has another advantage. Factors of Mersenne numbers are of the form 2kp+1. Only K has to be smooth, P is a factor that is already known.

[jjjjL]

Originally posted by smh
Don't forget that GIMPS has another advantage. Factors of Mersenne numbers are of the form 2kp+1. Only K has to be smooth, P is a factor that is already known.

yeah, but they have that advantage in their regular sieveing too so it's pretty much a wash when comparing sieve to P-1 advantage.

however, we shouldn't overlook the fact that while gimps factors are all smoother for P-1 factoring, our factors are more likely just as smooth for P+1 factoring. for each number, one is just as likely as the other to be smooth. that's something gimps doesn't have to think about.

-Louie

[smh]

yeah, but they have that advantage in their regular sieveing too

GIMPS doesn't sieve, they'll trailfactor each exponent seperately.

But you are right, their factors have special forms so they won't have to try each prime.

[jjjjL]

new version ready. much more better. let me know how it works for you if you test it.

http://www-personal.engin.umich.edu/...sbfactor02.zip

-Louie

[wblipp]

Originally posted by jjjjL
new version ready. much more better. let me know how it works for you if you test it.

http://www-personal.engin.umich.edu/...sbfactor02.zip

-Louie

First thing I noticed is the specifying B1 and B2 using "e" notation doesn't work, although it works fine in GMP-ECM. For example B1 as 5e4 is read as B1=5.

[smh]

I tried to factor the number you tried above, but it doesn't seem to find a factor.

D:\factor\p_1\sobp_1>sbfactor 55459 4000006 105 1150
SBFactor v0.2
P-1 factoring for number of the form k*2^n+1.
Adapted from GIMPS v23.4 by George Woltman and Louis Helm
P-1 on 55459*2^4000006+1 with B1=105, B2=1150
initializing test
sieve finished
exp is: 718766754945489455304472257065075294400
55459*2^4000006+1 stage 1 is 71.613 complete.
55459*2^4000006+1 stage 1 complete. 312 transforms. Time: 11 seconds
Starting stage 1 GCD - please be patient.
v: 1
retval: 1
v is one: 1
N is v: 1
55459*2^4000006+1 stage 2 is 8.995 complete.
55459*2^4000006+1 stage 2 is 73.876 complete.
55459*2^4000006+1 stage 2 complete. 480 transforms. Time: 95 seconds
Starting stage 2 GCD - please be patient.
v: 1
retval: 1
v is one: 1
N is v: 1
finished.
Total factoring Time: 2 minutes

I'll do some more testing.

edit

And it misses this one too:

D:\factor\p_1\sobp_1>sbfactor 22699 2946070 2000 2500
SBFactor v0.2
P-1 factoring for number of the form k*2^n+1.
Adapted from GIMPS v23.4 by George Woltman and Louis Helm
P-1 on 22699*2^2946070+1 with B1=2000, B2=2500
initializing test
sieve finished
exp is: 151117794877444315307536308337572822173736308853579339903227904473000476
32234723465512216086666894694199395101427093351203019495722137195682884352156808
21737862512423331578304504356232116643085003168444786178091011582206721088950535
08829266120497031742749376045929890296052805527212315382805219353316270742572401
96203546487823570375946479680607513105652007983695577041502131850827298210373665
86333904113477590005632712260621823459641841673469182252438563487940133554184046
95826256911622054015423611375261945905974225257659010379414787547681984112941581
32519839663468565921786120877140032250738816196751371916636683989421404078773347
12878456298339938854134622252945487855816418046204172565636852805865113019183990
10451347815776570842790738545306707750937624267501103840324470083425714138183905
657667736579430274197734179172691637931540695631396056193786415805463680000
22699*2^2946070+1 stage 1 is 3.476 complete.
22699*2^2946070+1 stage 1 is 6.952 complete.
22699*2^2946070+1 stage 1 is 10.428 complete.
22699*2^2946070+1 stage 1 is 13.903 complete.
22699*2^2946070+1 stage 1 is 17.379 complete.
22699*2^2946070+1 stage 1 is 20.855 complete.
22699*2^2946070+1 stage 1 is 24.331 complete.
22699*2^2946070+1 stage 1 is 27.807 complete.
22699*2^2946070+1 stage 1 is 31.283 complete.
22699*2^2946070+1 stage 1 is 34.758 complete.
22699*2^2946070+1 stage 1 is 38.234 complete.
22699*2^2946070+1 stage 1 is 41.710 complete.
22699*2^2946070+1 stage 1 is 45.186 complete.
22699*2^2946070+1 stage 1 is 48.662 complete.
22699*2^2946070+1 stage 1 is 52.138 complete.
22699*2^2946070+1 stage 1 is 55.613 complete.
22699*2^2946070+1 stage 1 is 59.089 complete.
22699*2^2946070+1 stage 1 is 62.565 complete.
22699*2^2946070+1 stage 1 is 66.041 complete.
22699*2^2946070+1 stage 1 is 69.517 complete.
22699*2^2946070+1 stage 1 is 72.993 complete.
22699*2^2946070+1 stage 1 is 76.469 complete.
22699*2^2946070+1 stage 1 is 79.944 complete.
22699*2^2946070+1 stage 1 is 83.420 complete.
22699*2^2946070+1 stage 1 is 86.896 complete.
22699*2^2946070+1 stage 1 is 90.372 complete.
22699*2^2946070+1 stage 1 is 93.848 complete.
22699*2^2946070+1 stage 1 is 97.324 complete.
22699*2^2946070+1 stage 1 complete. 5754 transforms. Time: 144 seconds
Starting stage 1 GCD - please be patient.
v: 1
retval: 1
v is one: 1
N is v: 1
22699*2^2946070+1 stage 2 is 0.600 complete.
22699*2^2946070+1 stage 2 complete. 354 transforms. Time: 175 seconds
Starting stage 2 GCD - please be patient.
v: 1
retval: 1
v is one: 1
N is v: 1
finished.
Total factoring Time: 3 minutes

It does find a factor is stage one though:

D:\factor\p_1\sobp_1>sbfactor 22699 2946070 2500 2500
SBFactor v0.2
P-1 factoring for number of the form k*2^n+1.
Adapted from GIMPS v23.4 by George Woltman and Louis Helm
P-1 on 22699*2^2946070+1 with B1=2500, B2=2500
initializing test
sieve finished
exp is: 106510494520812546426453164388604465285999854308692495682249271089807213
06428206240809505196704302195900220417077765787838448094951793623103176400361198
53473905102295359692079190995380381915412795803937490383602897354051010076575820
40036957623725894088347226025318922894165891041644695093217476255406976946625514
76865848264516186199644592963431936652632231100205244377467834576480916368826217
22033661955258524263306986748419129559530383605063848393796452258387378142362943
35094270131993616702817768239494210813296081888048626028788194625898235424628090
05231685890147798598832045271706506989408597963506302051910937812755233786298809
36380967043746733383246311147580217120504801391362222374380949660215311106601648
94745482137497219769183873441603140255708836274160814471913611742603571743637111
25657042853121002635877156167341476244071806861681527119271280458611022559610530
70145984309206300197750913103095033255960222812276013878589321622761614625953862
90938157830391434752960869263535148732460023317694364498806454958781925302998074
980866120862904826561098689492823559877964496277760000
22699*2^2946070+1 stage 1 is 2.775 complete.
22699*2^2946070+1 stage 1 is 5.549 complete.
22699*2^2946070+1 stage 1 is 8.324 complete.
22699*2^2946070+1 stage 1 is 11.099 complete.
22699*2^2946070+1 stage 1 is 13.873 complete.
22699*2^2946070+1 stage 1 is 16.648 complete.
22699*2^2946070+1 stage 1 is 19.423 complete.
22699*2^2946070+1 stage 1 is 22.198 complete.
22699*2^2946070+1 stage 1 is 24.972 complete.
22699*2^2946070+1 stage 1 is 27.747 complete.
22699*2^2946070+1 stage 1 is 30.522 complete.
22699*2^2946070+1 stage 1 is 33.296 complete.
22699*2^2946070+1 stage 1 is 36.071 complete.
22699*2^2946070+1 stage 1 is 38.846 complete.
22699*2^2946070+1 stage 1 is 41.620 complete.
22699*2^2946070+1 stage 1 is 44.395 complete.
22699*2^2946070+1 stage 1 is 47.170 complete.
22699*2^2946070+1 stage 1 is 49.945 complete.
22699*2^2946070+1 stage 1 is 52.719 complete.
22699*2^2946070+1 stage 1 is 55.494 complete.
22699*2^2946070+1 stage 1 is 58.269 complete.
22699*2^2946070+1 stage 1 is 61.043 complete.
22699*2^2946070+1 stage 1 is 63.818 complete.
22699*2^2946070+1 stage 1 is 66.593 complete.
22699*2^2946070+1 stage 1 is 69.367 complete.
22699*2^2946070+1 stage 1 is 72.142 complete.
22699*2^2946070+1 stage 1 is 74.917 complete.
22699*2^2946070+1 stage 1 is 77.691 complete.
22699*2^2946070+1 stage 1 is 80.466 complete.
22699*2^2946070+1 stage 1 is 83.241 complete.
22699*2^2946070+1 stage 1 is 86.016 complete.
22699*2^2946070+1 stage 1 is 88.790 complete.
22699*2^2946070+1 stage 1 is 91.565 complete.
22699*2^2946070+1 stage 1 is 94.340 complete.
22699*2^2946070+1 stage 1 is 97.114 complete.
22699*2^2946070+1 stage 1 is 99.889 complete.
22699*2^2946070+1 stage 1 complete. 7208 transforms. Time: 188 seconds
Starting stage 1 GCD - please be patient.
v: 1000809717779
retval: 1
v is one: 0
N is v: 1
1000809717779 | 22699*2^2946070+1
Total factoring Time: 3 minutes

[jjjjL]

I'm seeing inconsistent results too. Better than before when it didn't work at all, but there's still something broke.

For some reason, that first example you tried works if I use B1=105 B2=1300. it however does not work with other values as well.

George Woltman has helped me fix one bug in this version already and is helping me locate the others.

Right now, I'm working on integrating a modified version of the B1/B2 auto-bound setter.

-Louie

[jjjjL]

nothing incredible but I did find a new factor using P-1

22283121920233 | 4847*2^302511+1

22283121920233 = 2 ^ 3 x 3 x 2161 x 3877 x 110819 + 1

I found it with B1=25000 B2=2500000

This was my batch file I've run for a couple hours

sbfactor.exe 4847 300207 25000 0
sbfactor.exe 4847 300831 25000 0
sbfactor.exe 4847 301143 25000 0
sbfactor.exe 4847 301191 25000 0
sbfactor.exe 4847 301263 25000 0
sbfactor.exe 4847 301503 25000 0
sbfactor.exe 4847 301863 25000 0
sbfactor.exe 4847 302223 25000 0
sbfactor.exe 4847 302511 25000 0
sbfactor.exe 4847 302847 25000 0
sbfactor.exe 4847 302943 25000 0
sbfactor.exe 4847 303087 25000 0
sbfactor.exe 4847 303423 25000 0
sbfactor.exe 4847 303687 25000 0
sbfactor.exe 4847 303711 25000 0
sbfactor.exe 4847 303831 25000 0
sbfactor.exe 4847 303903 25000 0

(B2=0 --> B2=100*B1 by default)

-Louie

[rosebud]

The program produces one file for each run. Does it reduce the time needed for another run with the same n and k but with different values for b1 and b2? Or can i just delete it?

[biwema]

Are the new factors writeen into a file or are they only displayed in the screen output?
In that case it is quite difficult not to lose any factor as it is scrolling quite quickly.

biwema

[rosebud]

The factors are written to the file fact.txt so that you won't lose anything...

[smh]

22283121920233 = 2 ^ 3 x 3 x 2161 x 3877 x 110819

Of course, 22283121920233 is prime.

P-1 = 2 ^ 3 x 3 x 2161 x 3877 x 110819

Any news on a version that doesn't miss factors on stage two?

[jjjjL]

Originally posted by rosebud
The program produces one file for each run. Does it reduce the time needed for another run with the same n and k but with different values for b1 and b2? Or can i just delete it?

The file it produces will help with higher values of B1/B2. You should probably delete them when we finish testing the program and it actually works better.

I've fixed a small bug that would have made the client produce incorrect results if there were roundoff errors. The bug that makes the exponent slightly wrong at low values is also fixed. However, neither of those are what is causing it to miss factors. I'll let you know when there's a better version. For now, if you want to test it, try and see if you can find factors to save a secret/supersecret test. Numbers between 510k - 600k shouldn't be as hard to factor. We are about to finish the secret test of k=55459 @ n=540k so maybe you factor some of those and prevent 2 tests around there. You could find numbers by going though SoB.dat and the results.txt file but I'll post some below for those who want them.

-Louie

[jjjjL]

k
n
primality
status
55459
510250
Unknown
Untested
55459
510934
Unknown
Untested
55459
510958
Unknown
Untested
55459
511186
Unknown
Untested
55459
511246
Unknown
Untested
55459
511606
Unknown
Untested
55459
511678
Unknown
Untested
55459
511690
Unknown
Untested
55459
511834
Unknown
Untested
55459
512014
Unknown
Untested
55459
512074
Unknown
Untested
55459
512218
Unknown
Untested
55459
512866
Unknown
Untested
55459
513310
Unknown
Untested
55459
513418
Unknown
Untested
55459
513514
Unknown
Untested
55459
513586
Unknown
Untested
55459
513766
Unknown
Untested
55459
513850
Unknown
Untested
55459
513994
Unknown
Untested
55459
514174
Unknown
Untested
55459
514498
Unknown
Untested
55459
514570
Unknown
Untested
55459
514678
Unknown
Untested
55459
515134
Unknown
Untested
55459
515290
Unknown
Untested
55459
515470
Unknown
Untested
55459
515494
Unknown
Untested
55459
515638
Unknown
Untested
55459
515746
Unknown
Untested
55459
516694
Unknown
Untested
55459
517114
Unknown
Untested
55459
517234
Unknown
Untested
55459
517306
Unknown
Untested
55459
517366
Unknown
Untested
55459
517618
Unknown
Untested
55459
517774
Unknown
Untested
55459
518314
Unknown
Untested
55459
518566
Unknown
Untested
55459
518914
Unknown
Untested
55459
518998
Unknown
Untested
55459
519070
Unknown
Untested
55459
519646
Unknown
Untested
55459
519886
Unknown
Untested
55459
519994
Unknown
Untested
55459
520066
Unknown
Untested
55459
520246
Unknown
Untested
55459
520258
Unknown
Untested
55459
520426
Unknown
Untested
55459
520474
Unknown
Untested
55459
520534
Unknown
Untested
55459
520678
Unknown
Untested
55459
521218
Unknown
Untested
55459
522046
Unknown
Untested
55459
522130
Unknown
Untested
55459
522298
Unknown
Untested
55459
522310
Unknown
Untested
55459
522418
Unknown
Untested
55459
522694
Unknown
Untested
55459
522766
Unknown
Untested
55459
523138
Unknown
Untested
55459
523306
Unknown
Untested
55459
523354
Unknown
Untested
55459
523534
Unknown
Untested
55459
523846
Unknown
Untested
55459
523930
Unknown
Untested
55459
524098
Unknown
Untested
55459
524686
Unknown
Untested
55459
524818
Unknown
Untested
55459
524854
Unknown
Untested
55459
525118
Unknown
Untested
55459
525178
Unknown
Untested
55459
525334
Unknown
Untested
55459
525370
Unknown
Untested
55459
525514
Unknown
Untested
55459
525658
Unknown
Untested
55459
526558
Unknown
Untested
55459
526618
Unknown
Untested
55459
526798
Unknown
Untested
55459
526810
Unknown
Untested
55459
526846
Unknown
Untested
55459
526954
Unknown
Untested
55459
527170
Unknown
Untested
55459
527314
Unknown
Untested
55459
527350
Unknown
Untested
55459
527890
Unknown
Untested
55459
528238
Unknown
Untested
55459
528346
Unknown
Untested
55459
528634
Unknown
Untested
55459
528814
Unknown
Untested
55459
529114
Unknown
Untested
55459
529150
Unknown
Untested
55459
529438
Unknown
Untested
55459
529798
Unknown
Untested
55459
530194
Unknown
Untested
55459
530338
Unknown
Untested
55459
530578
Unknown
Untested
55459
530590
Unknown
Untested
55459
530866
Unknown
Untested
55459
531154
Unknown
Untested
55459
531634
Unknown
Untested
55459
531658
Unknown
Untested
55459
531766
Unknown
Untested
55459
531874
Unknown
Untested
55459
532054
Unknown
Untested
55459
532210
Unknown
Untested
55459
532234
Unknown
Untested
55459
532414
Unknown
Untested
55459
532486
Unknown
Untested
55459
532774
Unknown
Untested
55459
532918
Unknown
Untested
55459
533578
Unknown
Untested
55459
533650
Unknown
Untested
55459
534010
Unknown
Untested
55459
534154
Unknown
Untested
55459
534226
Unknown
Untested
55459
534334
Unknown
Untested
55459
534358
Unknown
Untested
55459
534394
Unknown
Untested
55459
534898
Unknown
Untested
55459
535018
Unknown
Untested
55459
535414
Unknown
Untested
55459
535438
Unknown
Untested
55459
535918
Unknown
Untested
55459
536206
Unknown
Untested
55459
536374
Unknown
Untested
55459
536446
Unknown
Untested
55459
536518
Unknown
Untested
55459
536530
Unknown
Untested
55459
537094
Unknown
Untested
55459
537274
Unknown
Untested
55459
538138
Unknown
Untested
55459
538426
Unknown
Untested
55459
538438
Unknown
Untested
55459
538606
Unknown
Untested
55459
538726
Unknown
Untested
55459
539014
Unknown
Untested
55459
539050
Unknown
Untested
55459
539146
Unknown
Untested
55459
539158
Unknown
Untested
55459
539410
Unknown
Untested
55459
539878
Unknown
Untested

[jjjjL]

Just got an email from George. He found the major bug and emailed me a fix. A new version is posted below that should find all factors correctly. Test it out and post results. You shouldn't be able to make it miss known factors now. Incidently, George also noticed that I hadn't yet enabled CPU specific optimizations. So this version not only works, it works a lot faster.

http://www-personal.engin.umich.edu/...sbfactor05.zip

-Louie

[jjjjL]

1590402916048273 | 33661*2^510216+1

1.5 peta-digit-factor! nice This factor is almost too large to submit. I may have to allow >2^64 factors soon. If it had one more large factor, I would have had to already.

1590402916048273 = 2 ^ 4 x 3 x 23 x 43 x 197 x 1381 x 123143 + 1

I found this with B1=50000 B2=5000000 (both a little overkill).

This is about as smooth of factor as you get. 2^4!? That's beging to be uncovered with P-1.

Lets compare to my last factor:

22283121920233 | 4847*2^302511+1

Other than for testing the code, the last batch of P-1 tests I ran around n=300k were hardly worth it. It only saved us one super secret test that would have taken 20 minutes and to do that, I ran factoring for about 4 hours. BUT the new factor was found for a completely untested number that was bound to get tested twice (by secret/supersecret). That number would have taken closer to 1-2hours to test and I found it with a batch file that ran for around 30 minutes.

Now that it works and it's fast, P-1 factoring makes sense. It's not a replacement for sieving but it makes a good complement to it. When a number can't be sieved out and is about to be tested, it pays off to spend a little time trying to factor it.

As I see it, there are two immediate areas that should be factored. n=510,000 and n=4,000,000.

The lower one is good because we're about to test n=510k numbers with secret AND supersecret very soon. You can save two tests by finding a factor now. It doesn't take too long run P-1 factoring at those levels either. I'd say that's a good area to experiment with the new version of the program until we come up with a good strategy for using this program.

n=4M is good too. I'm going to try around there soon too. Those numbers are just as likely to have factors and only take a little more time to factor. But instead of saving a few minutes of secret/supersecret doublechecking, you save 3-5days of testing.

I can think of three things I'd like to see people do:

1) Help me figure out a good allocation strategy for P-1 factoring. (wblipp, I'm looking at you )

2) Someone should make a script/webpage/something that reconciles the SoB.dat and results.txt file to make a list of unfactored numbers. (MikeH, I'm looking at you )

3) Test the new SBFactor. It works now and is fast. All the low hanging P-1 fruit is still in the orchard for those who want to pick it. (smh/biwema/rosebud, I'm looking at you )

-Louie

[ceselb]

I'd love to try this at n=4,000,000, if someone could generate a file. Is the code optimized for the P4?

[smh]

As I see it, there are two immediate areas that should be factored. n=510,000 and n=4,000,000.

Numbers around N=500K already had a lot of sieving done in comparision to the time it takes to prp them. If you spend the optimal time sieving these low numbers you only have the time to sieve with low bounds, which makes the chances of finding a factor above the current sieve depth low.

For numbers around N=4M this is completely different. The optimal time to prp should be something like the time it takes to prp a number twice (and add a little bit of time for faulty tests which need a tripple check) divided by the chance to find a factor with P-1 using the optimal bounds. (this doesn't take into account the sieving time on each number.

This makes me wonder, does anyone have an idea of how many giga hertz days/weeks have been put into sieving? I wonder how much time this is per exponent.

3) Test the new SBFactor. It works now and is fast. All the low hanging P-1 fruit is still in the orchard for those who want to pick it. (smh/biwema/rosebud, I'm looking at you )

At least it finds the two factors it missed with the old version.

I'll plan more p-1 when there is a lists with numbers available.

1590402916048273 = 2 ^ 4 x 3 x 23 x 43 x 197 x 1381 x 123143 + 1

I found this with B1=50000 B2=5000000 (both a little overkill).

This is about as smooth of factor as you get. 2^4!? That's beging to be uncovered with P-1.

2^4 is only 16, so it hardly makes any difference. A few above 1000 and a large one in the second stage is what gives you the large factors.

[Moo_the_cow]

One major concern about P-1 factoring:

- Mike H's sieve stats could be thrown off A LOT by P-1 factoring.
Example: I've sieved about 235 G so far, and my score is about
5,000. A 1GHZ PIII would need at least 12 days of computing
time (provided that the PC is on 24 hrs a day) to get to that
score. However, it would take the same computer only a few
hours to get to that score (by finding a 5 peta-digit factor for
just 1 number). This would encourage almost all sievers to
switch to P-1 factoring, and that is bad since candidates can
be eliminated twice as fast by regular sieving than by P-1
factoring.

Until someone resolves that problem,

P-1 factoring

or I'll in protest.

[Mystwalker]

Hm, a stats munchkin.

Well, I'd as say the approach factoring vs. sieving is quite different, there should be a seperate statistic.
I don't know the effort-relating factors (pun not intended) for the factoring, but they are different from those of sieving. So the effort estimation shouldn't be done on the basis of the factors.

Ok, that's basically the same as Moo said... <-- *selfslap*

Well, I thing this is something to be discussed on the way, but it should be no obstacle for factoring.
At least as long as it doesn't stop me from climbing the stats ladder.

[mklasson]

Let's say I tried to factor a k/n pair I was just assigned and actually found a factor. What would be a good thing to do next? Report the factor and delete SB's z* file to force it to fetch a new pair?

Mikael

[eatmadustch]

i think deleting the z file won't work, you'll just start the block from the beginning again. Change your Username, then change it back again (clicking on "yes" if you want to clear the cache). That way you'll get a new test. Or I suppose you can click on expire on the "pending test managment" page!

[mklasson]

Originally posted by eatmadustch
Or I suppose you can click on expire on the "pending test managment" page!

Doh! That's right, we've got that fancy feature nowadays...

[Mystwalker]

Or I suppose you can click on expire on the "pending test managment" page!

But AFAIK this won't stop the client until it tries to report a new block. I suggest clearing the cache, too.