P-1 factorer

[ceselb]

I know that some work is being done/planned, but I suspect that a new client and a functional factor submission form is top priority right now.

[jjjjL]

Originally posted by Nuri
Are there any news on fixing the P-1 bug for PIVs?

I am aware that it is not of top priority, but some feedback would be useful.

I can release a new factoring version before v 3 of the client is finished. Now is not a good time to do it because I'm not at home where I have a P4 (thanks Fritz!) to test with.

Wednesday will be the first day I get to work on it. Sometime this week should be a reasonable ETA for a new version.

Also, I think I understand the problem, but if someone could summarize what the issue is and give me examples so I can reproduce the problem, that will help me make sure the next version doesn't suffer from the same deficiency. Email me at lhelm@umich.edu with the info. Thanks.

Cheers,
Louie

[Nuri]

Thanks for the feedback, and good luck.

Simply speaking, the client exits for n>4980700 on PIVs. As far as I recall, this is valid for all versions (and under various settings/parameters).

[MikeH]

As far as I recall, this is valid for all versions

I thought it was only the Windows version that was faulty. That was certainly where I saw the problem (Win2K). Someone please correct me if I'm wrong.

[hc_grove]

Originally posted by MikeH
I thought it was only the Windows version that was faulty. That was certainly where I saw the problem (Win2K). Someone please correct me if I'm wrong.

You're absolutely right. All my p-1 factoring is done on P4's running Linux.

[Nuri]

Sorry for the misunderstanding and thanks for the clarification.

What I meant by all versions was, including the previous releases of the client for windows.

[Frodo42]

I'm having trouble finding/making the SoB.dat file to use for P-1 factoring.

When using the updated SoB.dat file (11 k's) result.txt does not remove any tests, so therefore I have made my own SoB.dat file by adding a few zeros to the line after k=5359, thereby making the tests for k=5359 totally out of range and preserving the result.txt ability. This has worked fine for some time, but now suddenly the P-1 factorer wants to do test some weird out of bounds tests for k=4847 when I start it.

I can't figure out why this happens. Anyone got a clue?

[jjjjL]

Link to SBFactor v1.2

Been tinkering with the factorer.

This version is similar to v1.1 except:
-Doesn't crash on P4s for n > 5M
-Newer gw code so probably 5-10% faster (have done validation tests but no benches)
-Bundled w/ new 11k dat file
-Bundled w/ new, smaller results.txt file (p > 25T instead of p > 3T)
-Updated run.bat so factor depth is 47 (140T) instead of 45 (35T)
-No longer reads lowresults.dat (because .dat file has those values removed)
-Minor cosmetic differences
-*EDIT* LINUX BINARY NOW INCLUDED. *EDIT*

Those are the biggies. Hopefully now that P4s can run in Windows again we can get a little more P-1 work done. It'd be nice to not abandon large ranges of number due to lack of factoring resources.

About the result.txt files... changed the ranges this morning. Should save a little bandwidth and save download time for anyone getting the results.txt file since it was creeping up to 2MB compressed. Now it's down much lower. However, there's a good chance this broke sieve stats because until MikeH downloads the new lowresults.txt, it may appear as though all results between 3T and 25T vanished. Sorry. Not to worry though, it's a temporary thing.

The important part is the new version of SBFactor is out.

Let me know how it performs:
1) On machines where v1.1 crashes (P4, Centrino, Mobile P4)
2) Relative speedwise to v1.1 (any increase?)
3) On tests for numbers where it returned false factors (like 3 or 7)
4) And in general.

Looking forward to hearing from people and seeing more factoring activity.

Cheers,
Louie

[Frodo42]

Nice, I haven't got any Windows machines so I can't say if it works, just waiting for a Linux version. If there is a speed increase, then let's have it, there is afterall more Linux boxes doing som P-1 factoring than windows boxes at present (although that probably is about to change with the new windows-version)

Anyways fixing result.txt down to 11 k's solved my problem, so thanks for that.

Maybe a link to the new factorer in the coordination thread would be a good idea.

[hc_grove]

Well, I don't have any windows machines either, so I'd like a Linux version of 1.2 too.

After the release of 1.1 there was some talk abourt manually setting B1 and B2, what happened to those plans?

[jjjjL]

Turns out building the new version of the factorer went really smoothly so I already uploaded a new zip file that has both Linux and Windows versions in it.

Cheers,
Louie

[hc_grove]

Originally posted by jjjjL

1) On machines where v1.1 crashes (P4, Centrino, Mobile P4)

1.1 didn't crash in Linux, 1.2 doesn't either.

2) Relative speedwise to v1.1 (any increase?)

Nothing noticeable.

3) On tests for numbers where it returned false factors (like 3 or 7)

Haven't had any of those myself, and haven't tested.

4) And in general.

It's nice not to need lowresults.txt anymore.

[MikeH]

Hi Louie,

Sieving and P-1 scores are now sorted.

Just one little question. Why are the following factors at the end of the LowResults.txt file?

11431293770421995731	27653	5103393	584	61	0
14500316478379213543	33661	5343552	960	9	0

These ones are 11431293T (and bigger), which isn't usually less than 25T

It's not a problem, I just removed them from the file, and now all is OK.

Many thanks for fixing the P-1, I'm now happily crunching again.

[Mystwalker]

Originally posted by jjjjL
Let me know how it performs:
1) On machines where v1.1 crashes (P4, Centrino, Mobile P4)

Works without a glitch (P4, Windows).

2) Relative speedwise to v1.1 (any increase?)

I'm not sure I remember the correct time I needed with 1.1, but I think the time hasn't changed at all.


Good to be able to do factoring again. Thanks, Louie!

[Joe O]

Total factoring Time: 640 minutes for 27653*2^5689005+1 on a PIII/500 under Win98SE.

If memory serves me right, this is about a 10% improvement. I'll try to verify this later in the week. But it definitely is an improvement.

I'll try it on a PIV this weekend.

Edit: Overnight results:

Total factoring Time: 617 minutes for 27653*2^5689041+1 on a PIII/500 under Win98SE

[jjjjL]

So I'm looking into making the client run P+1 factoring again.

I'm having a lot of trouble finding any explainations of exactly how P+1 factoring works.

MathWorld has almost nothing http://mathworld.wolfram.com/William...ionMethod.html

and most other sites I find are nearly as sparse in details. The only somewhat techincal document is the README and comments in the source code of ECMNET.

However, it's a little challenging translating the P+1 code from this program into gw code for Woltman's multiplication routines.

Anyone know of any useful documents that describe the P+1 algoritm outside of ECMNET?

Cheers,
Louie

[ceselb]

Originally posted by Frodo42
Maybe a link to the new factorer in the coordination thread would be a good idea.

Good idea, added.

[Joe O]

Have you tried Williams, H. C. "A Method of Factoring." Math. Comput. 39, 225-234, 1982?
If you still have access to the University Library it should be possible to get this in PDF format.

Or you could try "A Survey of Modern Integer Factorization Algorithms" by Peter L. Montgomery

Then there is "Prime Numbers: A Computational Perspective", by Richard Crandall
and Carl Pomerance or
"Prime Numbers and Computer Methods for Factorization (Progress in Mathematics, Vol 126) " by Hans Riesel
Both of these are available from Amazon.com

[jjjjL]

Originally posted by Joe O
Have you tried Williams, H. C. "A Method of Factoring." Math. Comput. 39, 225-234, 1982?
If you still have access to the University Library it should be possible to get this in PDF format.

Yeah, I grabed that paper from JSTOR. If anyone needs it, I can send it to you. It's dense but it may help.

BTW, I just got two new factors:
5013169446620738903 | 4847*2^5621151+1
1042382178159409 | 21181*2^5621468+1

5013169446620738903-1 = 2 x 191 x 709 x 797 x 1619 x 2273 x 6311
1042382178159409-1 = 2 ^ 4 x 3 ^ 2 x 103 x 337 x 9649 x 21613

smooth

Cheers,
Louie

[hc_grove]

Originally posted by jjjjL
Yeah, I grabed that paper from JSTOR. If anyone needs it, I can send it to you. It's dense but it may help.

I've some unsuccesful searches for P+1-factoring too, so I'd like a copy. As I have a master degree in mathematics I can live with it being a bit dense.

As an administrator you should be able to send me email, but else tell me, and I'll send you a PM with the address.

BTW, I just got two new factors:

Congratulations, now I just wish that I could find an interesting factor again.

[Joe O]

Originally posted by jjjjl
Yeah, I grabbed that paper from JSTOR. If anyone needs it, I can send it to you. It's dense but it may help.

Louie, I'd like a copy. Maybe I can translate it into English from Mathematics.

[jjjjL]

Originally posted by hc_grove
As an administrator you should be able to send me email, but else tell me, and I'll send you a PM with the address..

I'm actually not a free-dc administrator, I'm only a moderator of this particular board so I can't lookup your email that way... but I can look it up on SB so I'll email it to you there. PM me if you don't get it or you need me to send it to an address other than the one you registered for SB with.


Cheers,
Louie

[hc_grove]

Originally posted by jjjjL
I'm actually not a free-dc administrator, I'm only a moderator of this particular board

Well that was what I meant, and I though that was enough.

so I can't lookup your email that way... but I can look it up on SB so I'll email it to you there. PM me if you don't get it or you need me to send it to an address other than the one you registered for SB with.

It's the same address, and I have received it, and will look at it later (just have a newsserver that ran out of disc space to fix first)

[mklasson]

I just noticed something odd:
3 | 460139*2^361-1 (9 | too)
but sbfactor (v1.25 at least) is unable to find that factor in stage 1, no matter how high you go.

EDIT:
and another thing:
172599179 | 460139*2^380-1
172599179-1 = 2*86299589
b1=30, b2=100M finds it successfully
b1=86M, b2=1G does _not_ find it
b1=86M, b2=1.5G finds it
b1=86M, b2=2G does _not_ find it

I don't know whether the errors are due to something related to saving and restoring the state. I.e. I haven't tried going to 86M,1G from scratch.

[jjjjL]

Originally posted by mklasson
I just noticed something odd:
3 | 460139*2^361-1 (9 | too)
but sbfactor (v1.25 at least) is unable to find that factor in stage 1, no matter how high you go.

EDIT:
and another thing:
172599179 | 460139*2^380-1
172599179-1 = 2*86299589
b1=30, b2=100M finds it successfully
b1=86M, b2=1G does _not_ find it
b1=86M, b2=1.5G finds it
b1=86M, b2=2G does _not_ find it

I don't know whether the errors are due to something related to saving and restoring the state. I.e. I haven't tried going to 86M,1G from scratch.

That is bad. As I pointed out in the other thread, I did test several other numbers with no problems but not many test points were available (ie I had to sieve most of my own using your program ).

hc_grove is hinting that he may have fixed this but I don't really know what would have been wrong.

Cheers,
Louie

[Joe O]

Originally posted by mklasson
I just noticed something odd:
3 | 460139*2^361-1 (9 | too)
but sbfactor (v1.25 at least) is unable to find that factor in stage 1, no matter how high you go.

EDIT:
and another thing:
172599179 | 460139*2^380-1
172599179-1 = 2*86299589
b1=30, b2=100M finds it successfully
b1=86M, b2=1G does _not_ find it
b1=86M, b2=1.5G finds it
b1=86M, b2=2G does _not_ find it

I don't know whether the errors are due to something related to saving and restoring the state. I.e. I haven't tried going to 86M,1G from scratch.

Not to panic yet. This could be normal. P-1 does not find all small factors, and sometimes giving it too large of a B1 hides small factors. This comment is based on experience with P-1 in GIMPS(Prime95). I'm not sure if the theory backs that up, but at least one other implementation of the theory does. I'm up to my elbows in P-1 and P+1 theory papers now, and Ill report if they back this up.

[hc_grove]

Originally posted by jjjjL
hc_grove is hinting that he may have fixed this but I don't really know what would have been wrong.

I'm sorry to say but my version doesn't find that factor 3 (or 9) either.

And to Joe_O: As I have understood the theory, it's doesn't back your claim.

[Joe O]

Originally posted by hc_grove
As I have understood the theory, it's doesn't back your claim.

Not a claim, just an observation that certain implementations fail to find small factors. While looking for a discussion where this behaviour was observed, I came across this excellent description of P-1 and ECM that was posted by Phil Moore. It's too long to quote here, so this is the link. It is followed by additional insights from E W Mayer and again by Phil Moore.

Addendum: Please check the last paragraph of section 6.3 on page 346 (10th page of the PDF) in "A Survey of Modern Integer Factorization Methods" by Peter L. Montgomery. The point is made that only factors of a certain form are found by P-1.

[jjjjL]

Originally posted by cedricvonck
sbfactor 6000100 6000110 47 .... (ram) 128

Ahh, even without the whole command I think I see what happened. Must have dropped an argument and sent the program into single number test mode instead of testing the range. 47 is probably the B1 you used there....

and as it turns out, that factor you found is actually correct:

6000110 * 2^6000150+1 is divisible by 9 (I checked). In fact, that number is divisible by 3... but you happened to find that it was divisible by 3^2.

If you post the full command line you used, we could probably set you straight. Be aware v1.25 for Riesel sieve takes an extra argument of " + " before the mem size to signify that you use the +1 transforms instead of -1 (for Riesel). Most people on the forum here are still using v1.20 which doesn't have this. It's just unfortuante that the commands are very similar (yet different) and the program accepts the command with one less argument but just runs in a mode other than the one you wanted.

If you want to use run.bat, either use it w/ v1.20 or edit run.bat to include a " + " between 1.5 and 128 like " ... 1.5 + 128".

Cheers,
Louie

[jjjjL]

Originally posted by Citrix
I am looking for all the P-1 factors (not the factors by sieve) found by SOB. where can I find these numbers. Please let me know.

Thanks,
Citrix

There is no file for just P-1 factors. A list of all factors from sieving and P-1 and any other method is in http://www.seventeenorbust.com/sieve/results.txt.bz2 . Uncompress it and look at the end for the large factors which were most likely found by P-1. By comparing it to the sieve list, you can probably determine which factors were found in which way.

Also, in the future, don't post general questions in the coordination thread. This thread is meant only for reserving and checking in completion data for ranges of numbers. A more appropriate thread for discussion is the P-1 factorer thread. I'm going to delete your original message and leave only this response so as to minimize the cluter in the thead before I remove this message in a few days. Nobody's mad, but just a kind reminder for next time.


Cheers,
Louie

[cedricvonck]

I used the following cmd:

sbfactor.exe %1 %2 47 1.5 + 128

name of zip file: sbfactor12.zip

[MJX]

The point is made that only factors of a certain form are found by P-1.

the only point I see is related to the smoothness : to find a factor p with parameters B1 (for stage 1) and B2 (for stage 2), p-1 must be "B1-B2 semismooth" : all its factors must be below B1 exept one that can be between B1 and B2 (if it is below B1, factor is found in stage 1, if p-1 is not semismooth, the factor, even if it is small, is not found).

I just noticed something odd:
3 | 460139*2^361-1 (9 | too)
but sbfactor (v1.25 at least) is unable to find that factor in stage 1, no matter how high you go.

concerning ECM, I remember that P. Zimmermann said that gmp-ecm didn't work well if the number to factorize was divisible by 2 or 3... fact that can be avoided by simple trial division... (maybe this can happen with p-1 too, since p-1 (in that case 3-1=2)and the base number "a" that you exponentiate (surely a=2, because 2^(p-1) is easy to compute) should be pairwise prime, if I am right about Fermat theorem...)

[mklasson]

Ah, you're right! sbfactor uses a=3, so a^b-1 will never be a multiple of 3.

And the 172599179 issue turns out to be a non-issue as well. It wasn't found because I probably ran up to 86M,100M first and found the factor, and then just raised the B2 bound causing sbfactor to do B2 from 100M upwards, skipping the already passed 86299589... Don't know why 86M,1.5G found it again though. Perhaps Brent-Suyama kicked in?

Ho hum. Sorry about all the confusion. Must learn to think farther.

[MJX]

I use a low suboptimal B1=10000 B2=97500 to get the ability of testing more numbers (is it better to test a maximum of numbers with low bounds or keep large gaps of untested numbers between optimally tested ones??)

(removed reservation /ceselb )

[garo]

MJX,
Given the fact that a large number of "numbers" are not getting any P-1 I think you are on the right track. It is more efficient to do a little P-1 on all the numbers than to do a lot on only some numbers. Of course, ideally one would want to do a lot of all the numbers but since that is not possible....

[Frodo42]

I think there is a problem with either the Linux-version of the factorer or the result.txt file.

For some time I have had the problem that when i download a new result.txt file and start the factorer
- I get the output: "Removed 0 numbers using the factor file"
- The last estimated number is "Estimating for k=4847 n=13338904" no matter which range i set it to do. From there of there is no more output but it keeps using CPU-power, I haven't tried letting it run for long enought too see if it generates files but have instead used the result.txt coming with the sbfactor12.zip file that does not give any problems.

This problem was also present ind the last factorer, so I think it is a problem with the result.txt file after the last prime.
Damned be those primes they only cause problems

[hc_grove]

Originally posted by Frodo42
I think there is a problem with either the Linux-version of the factorer or the result.txt file.

For some time I have had the problem that when i download a new result.txt file and start the factorer
- I get the output: "Removed 0 numbers using the factor file"
- The last estimated number is "Estimating for k=4847 n=13338904" no matter which range i set it to do. From there of there is no more output but it keeps using CPU-power, I haven't tried letting it run for long enought too see if it generates files but have instead used the result.txt coming with the sbfactor12.zip file that does not give any problems.

This problem was also present ind the last factorer, so I think it is a problem with the result.txt file after the last prime.

I don't think results.txt changed because of the prime. (There are still factors for k=5359 in it).

I can't see why this would happen. Can I get you to try out my version (see the source code thread)?

Damned be those primes they only cause problems

[Frodo42]

I can't see why this would happen. Can I get you to try out my version (see the source code thread)?

I just tried it out and it does the same thing.

used the range 5600000 5620000 as I know there should be some factors to remove with result.txt
...
Removed 0 numbers using the factor file
...
Estimating for k=10223 n=5619929
Estimating for k=4847 n=8654994
Estimating for k=4847 n=1930939537
from here it just freezes.

Another thing Henrik, in your latest of the tar.gz version in the sbfactor.cnf file type = ECM it took me a while to figure out that I had to change it to P-1 as there is no other possibilities than ECM listed in the comments

[hc_grove]

Originally posted by Frodo42
I just tried it out and it does the same thing.

used the range 5600000 5620000 as I know there should be some factors to remove with result.txt
...
Removed 0 numbers using the factor file
...
Estimating for k=10223 n=5619929
Estimating for k=4847 n=8654994
Estimating for k=4847 n=1930939537

That n is strange. I can't figure out where that should come from.

Could you make the "good" and one of the "bad" results.txt's and the sbfactor.log from my version available or mail them to me (I'll PM you my email)?

Another thing Henrik, in your latest of the tar.gz version in the sbfactor.cnf file type = ECM it took me a while to figure out that I had to change it to P-1 as there is no other possibilities than ECM listed in the comments

Ooops! That wasn't even the only option that was set to some strange value. It's fixed now. (And I'll try to remember to put a normal configuration in future releases.

[Frodo42]

I have come to miss a little program that tells me how big a range I should reserve if I for example want to do 6 test with P-1 factorer with given parameters.

When I'm having classes with a P4 computer put in front of me I can't resist the temptation of doing a few test's, but when my class finishes before the test's it's a little anoying.

I don't think it would be all that hard to make that kind of code from the current prediction part of the current factorer. Actually the option just to run the prediction part without starting the factoring part would probably be good enough.

If it's not to diffucult it could be cool to be able to tell the factorer that I have app. x hours of CPU-time available please factor an apropriate range starting from y

Btw. hc_grove thanks for teaching me a lesson on unpacking files, which was the reason for my previos problemt with result.txt. Insted of unpacking result.txt.bz2 I packed an extra time and renamed it to result.txt