Mersenne: P-1, N-1 tests
Hi! Recently, I've been playing with some number theoretical problems (just for fun). I've met two similar approches mentioned in the subject: a) P-1 method of factorization and b) N-1 primality test. It seems (if I understand well) that a) we assume that a prime factor p of a given (composite) number n is such that p-1 is smooth; then we can try to determine p itself; b) we _know_ factorization of n-1 and there are some primality tests (see, e.g., Chris Caldwell pages) for n My question is: Is there any method/algorithm to determine _factors_ of n if the factorization of n-1 is known? I understand that there is no _exact_ formula for factors, but maybe there are some strong conditions, which restrict factors to a specific form (like k2^r+1 for Fermat numbers) The second question I should send directly to Chris Caldwell. In his Prime Pages the N-1 test of primality needs such a that a^(N-1)=1 mod N and a^(N-1)/q is not 1 mod N (q is a factor of N-1). Methods for determining the number a are not presented. Are there any such methods? Regards Wojciech Florek (WsF) Adam Mickiewicz University, Institute of Physics ul. Umultowska 85, 61-614 Poznan, Poland phone: (++48-61) 8295033 fax: (++48-61) 8295167 email: [EMAIL PROTECTED] _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 on PIII or P4?
At 07:47 AM 3/11/2003 -0500, Richard Woods wrote: However, any difference in FFT size between a P4 and other CPU, because of SSE support/nonsupport, could make a difference to the algorithm because it _does_ take FFT size into account. There was a bug in calculating the the FFT size (bytes of memory consumed) for the P4. This bug caused the P-1 bounds selecting code to produce different results than the x86 code. This is a fairly benign bug and will be fixed in version 23.3 In case you care, the details are: There is a global variable called FFTLEN that is used in many places and is initialized by the FFT init routine. The routine to select the P-1 bounds is called before the FFT code is initialized. Thus, the routine to calculate the number of bytes consumed by an FFT cannot use the global variable FFTLEN. In fact, that routine is passed an argument - fftlen in lower case. Well, you guessed it, in the P4 section of the routine I referenced FFTLEN rather than fftlen. The routine worked fine once the FFT code was initialized - only the P-1 bounds selecting code was affected. BTW, the FFT size is more than FFT length * sizeof (double). There are various paddings thrown in for better cache usage. Sadly, if I had just used FFT length * sizeof (double) as an estimate for the size in selecting the P-1 bounds this bug never would have happened and the size estimate is more than accurate enough for the purposes of selecting bounds. --- Checked by AVG anti-virus system (http://www.grisoft.com). Version: 6.0.459 / Virus Database: 258 - Release Date: 2/25/2003
Re: Mersenne: P-1 on PIII or P4?
At 13:05:41, Monday, 3/10/03, Brian J. Beesley wrote: I just tried Test=8907359,64,0 on two systems - an Athlon XP 1700+ and a P4-2533, both running mprime v23.2 with 384 MB memory configured (out of 512 MB total in the system). These were fresh installations, I did nothing apart from adding SelfTest448Passed=1 to local.ini to save running the selftest. The Athlon system picked B1=105000, B2=1995000 whilst the P4 picked B1=105000, B2=2126250. So it seems that P4 is picking a significantly but not grossly higher B2 value. Yes, I checked, both systems are using 448K run length for this exponent (though it's only just under the P4 crossover). Maybe the P-1 bounds calculation accounts for the slightly slower than normal iteration time that 8907359 would have on a P4 because of the roundoff checking (since it is very close to the P4 512K FFT limit). -- Nick Glover [EMAIL PROTECTED] It's good to be open-minded, but not so open that your brains fall out. - Jacob Needleman _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 on PIII or P4?
Daran wrote: I'd appreciate it if you or someone else could try starting a P-1 on the same exponent (not in one of the ranges where it would get a different FFT length) on two different machines, with the same memory allowed. P4: M8769809 completed P-1, B1=45000, B2=72, E=12, WY2: E2F4FF67 Memory allowed: 896MB (Machine has 1GB) PIII: M8769809 completed P-1, B1=45000, B2=72, E=12, WY2: E2F4FF67 Memory allowed: 990MB (Machine has 1 1/8GB) -- [EMAIL PROTECTED] - HMC UNIX Systems Manager _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 on PIII or P4?
On Mon, Mar 10, 2003 at 09:05:41PM +, Brian J. Beesley wrote: On Monday 10 March 2003 07:49, Daran wrote: I just tried Test=8907359,64,0 on two systems - an Athlon XP 1700+ and a P4-2533, both running mprime v23.2 with 384 MB memory configured (out of 512 MB total in the system). These were fresh installations, I did nothing apart from adding SelfTest448Passed=1 to local.ini to save running the selftest. The Athlon system picked B1=105000, B2=1995000 whilst the P4 picked B1=105000, B2=2126250. So it seems that P4 is picking a significantly but not grossly higher B2 value. My Duron 800 picks values identical to your Athlon with 384MB allowed. No change at 400MB At 420MB B2 goes up to 2021250, still lower than your B2 value. At 504MB B2 remains at 2021250. I don't think George's '1 or 2 extra temporaries' theory stands up. Regards Brian Beesley Daran G. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 on PIII or P4?
At 01:16 AM 3/11/2003 +, Daran wrote: I don't think George's '1 or 2 extra temporaries' theory stands up. Sure it does. I fired up the debugger and the P4 has 5541 temporaries and the x86 has 89 temporaries. Hmmm, maybe I'd better look into it a little bit further --- Checked by AVG anti-virus system (http://www.grisoft.com). Version: 6.0.459 / Virus Database: 258 - Release Date: 2/25/2003
Re: Mersenne: P-1 on PIII or P4?
On Fri, Mar 07, 2003 at 09:51:33PM -0800, Chris Marble wrote: Daran wrote: On Thu, Mar 06, 2003 at 08:12:31PM -0800, Chris Marble wrote: Daran wrote: I like my stats but I could certainly devote 1 machine out of 20 to this. If you're going to use one machine to feed the others, then it won't harm your stats at all. Quite the contrary. Assume I've got 1GB of RAM. Do the higher B2s mean I should use a P4 rather than a P3 for this task? I don't know, because I don't know why it gets a higher B2. B1 and B2 are supposed to be chosen by the client so that the cost/benefit ratio is optimal. Does this mean that P4s is choose B2 values which are too high? Or does everything else choose values too low? Or is there some reason I can't think of, why higher values might be appropriate for a P4? In fact, I'm not even sure it does get a higher B2 - the apparent difference could be, as Brian suggested, due to differences between versions. I don't have access to a P4, so I can do any testing, But I'd appreciate it if you or someone else could try starting a P-1 on the same exponent (not in one of the ranges where it would get a different FFT length) on two different machines, with the same memory allowed. You would not need to complete the runs. You could abort the tests as soon as they've reported their chosen limits. Would I unreserve all the exponents that are already P-1 complete? If I don't change the DoubleCheck into Pfactor then couldn't I just let the exponent run and then sometime after P-1 is done move the entry and the 2 tmp files over to another machine to finish it off? If you're going to feed your other machines from this one, then obviously you won't need to unreserve the exponents they need. But there's an easier way to do this. Put SequentialWorkToDo=0 in prime.ini, then, so long as it never runs out of P-1 work to do, it will never start a first-time or doublecheck LL, and there will be no temporary files to move. I also suggest putting SkipTrialFactoring=1 in prime.ini. That sounds like more work than I care to do... I agree that with 20 boxes, the work would be onerous. ...I can see having 1 machine do P-1 on lots of double-checks. That would be well worth it. Since one box will *easily* feed the other twenty or so, you will have to decide whether to unreserve the exponents you P-1 beyond your needs, or occasionally let that box test (or start testing) one. You may find a better match between your rate of production of P-1 complete exponents, and your rate of consumption, if you do first-time testing. [...] As an mprime user I edit the local.ini file all the time. Per your notes I upped *Memory to 466. That will certainly help exponents below 9071000 on a P3, or 8908000 on a P4. The current DC level is now over 917, so I doubt this will help much, (though of course, it won't harm, either). I haven't tried. I'm still getting enough sub 9071000 expiries. -- [EMAIL PROTECTED] - HMC UNIX Systems Manager Daran G. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 on PIII or P4?
On Thu, Mar 06, 2003 at 08:12:31PM -0800, Chris Marble wrote: Daran wrote: Whichever machine you choose for P-1, always give it absolutely as much memory as you can without thrashing. There is an upper limit to how much it will use, but this is probably in the gigabytes for exponents in even the current DC range. So I should use the PIII with 1 3/4 GB of RAM to do nothing but P-1. This depends upon what it is you want to maximise. If it's your effective contribution to the project, then yes. Absolutely! This is what I do on my Duron 800 with a 'mere' 1/2GB. The idea is that the deep and efficient P-1 you do replaces the probably much less effective effort that the final recipient of the exponent would otherwise have made (or not made, in the case of a few very old clients that might still be running). I've not done any testing, but I'm pretty sure that it would be worthwhile to put any machine with more than about 250MB available to exclusive P-1 use. On the other hand, you will do your ranking in the producer tables no favours if you go down this route. It's an older Xeon with 2MB cache. Will that help too? You'll have to ask George if there is a codepath optimised for this processor. But whether there is or there isn't, should affect only the absolute speed, not the trade-off between P-1 and LL testing. I can't see how a 2MB cache can do any harm, though. How would I do this? I see the following in undoc.txt: You can do P-1 factoring by adding lines to worktodo.ini: Pfactor=exponent,how_far_factored,has_been_LL_tested_once For example, Pfactor=1157,64,0 Unfortunately, pure P-1 work is not supported by the Primenet server, so requires a lot of ongoing administration by the user. First you need to decide which range of exponents is optimal for your system(s). (I'll discuss this below). Then you need to obtain *a lot* of exponents in that range to test. I do roughly eighty P-1s on DC exponents in the ten days or so it would take me to do a single LL. The easiest way to get your exponents is probably to email George and tell him what you want. Alternatively, if the server is currently making assignments in your desired range, then you could obtain them by setting 'Always have this many days of work queued up' to 90 days - manual communication to get some exponents - cut and past from worktodo.ini to a worktodo.saved file - manual communication to get some more - cut and past - etc. This is what I do. The result of this will be a worktodo.saved file with a lot of entries that look like this DoubleCheck=8744819,64,0 DoubleCheck=8774009,64,1 ... (or 'Test=...' etc.) Now copy some of these back to your worktodo.ini file, delete every entry ending in a 1 (These ones are already P-1 complete), change 'DoubleCheck=' or 'Test=' into 'Pfactor=', and change the 0 at the end to a 1 if the assignment was a 'DoubleCheck'. When you next contact the server, any completed work will be reported, but the assignments will not be unreserved, unless you act to make this happen. The easiest way to do this is to set 'Always have this many days of work queued up' to 1 day, and copy your completed exponents from your worktodo.saved file back to your worktodo.ini (not forgetting any that were complete when you got them). You do not need to unreserve exponents obtained directly from George. Like I said, It's *a lot* of user administration. It's not nearly as complicated as it sounds, once you get into the routine, but it's definitely not something you can set up, then forget about. If you're willing to do all this, then there's another optimisation you might consider. Since it's only stage 2 that requires the memory, you could devote your best machine(s) to this task, using your other boxes to feed them by doing stage 1. This is assuming that they're networked together. Moving multimegabyte date files via Floppy Disk Transfer Protocol is not recommended. [...] If you are testing an exponent which is greater than an entry in the fifth column, but less than the corresponding entry int the third column, then avoid using a P4. This applies to all types of work. Actually it's worse than this. The limits are soft, so if you are testing an exponent *slightly* less than an entry in column 5, or *slightly* greater than one in column 3, then you should avoid a P4. Choice of exponent range Stage two's memory requirements are not continuous. This remark is probably best illustrated with an example: on my system, when stage 2-ing an exponent in the range 777 through 9071000, the program uses 448MB. If that much memory isn't available, then it uses 241MB. If that's out of range, then the next level down is 199MB, and so on. There are certainly usage levels higher than I can give it. The benefits of using the higher memory levels are threefold. 1. The algorithm runs faster. 2. The program responds by deepening the search,
Re: Mersenne: P-1 on PIII or P4?
Daran wrote: On Thu, Mar 06, 2003 at 08:12:31PM -0800, Chris Marble wrote: Daran wrote: Whichever machine you choose for P-1, always give it absolutely as much memory as you can without thrashing. There is an upper limit to how much it will use, but this is probably in the gigabytes for exponents in even the current DC range. So I should use the PIII with 1 3/4 GB of RAM to do nothing but P-1. This depends upon what it is you want to maximise. If it's your effective contribution to the project, then yes. I like my stats but I could certainly devote 1 machine out of 20 to this. Assume I've got 1GB of RAM. Do the higher B2s mean I should use a P4 rather than a P3 for this task? Unfortunately, pure P-1 work is not supported by the Primenet server, so requires a lot of ongoing administration by the user. Alternatively, if the server is currently making assignments in your desired range, then you could obtain them by setting 'Always have this many days of work queued up' to 90 days - manual communication to get some exponents - cut and past from worktodo.ini to a worktodo.saved file - manual communication to get some more - cut and past - etc. This is what I do. The result of this will be a worktodo.saved file with a lot of entries that look like this DoubleCheck=8744819,64,0 DoubleCheck=8774009,64,1 ... (or 'Test=...' etc.) Now copy some of these back to your worktodo.ini file, delete every entry ending in a 1 (These ones are already P-1 complete), change 'DoubleCheck=' or 'Test=' into 'Pfactor=', and change the 0 at the end to a 1 if the assignment was a 'DoubleCheck'. Would I unreserve all the exponents that are already P-1 complete? If I don't change the DoubleCheck into Pfactor then couldn't I just let the exponent run and then sometime after P-1 is done move the entry and the 2 tmp files over to another machine to finish it off? If you're willing to do all this, then there's another optimisation you might consider. Since it's only stage 2 that requires the memory, you could devote your best machine(s) to this task, using your other boxes to feed them by doing stage 1. That sounds like more work than I care to do. I can see having 1 machine do P-1 on lots of double-checks. A couple of other points: You are limited in the CPU menu option to 90% of physical memory, but this may be overridden by editing local.ini, where you can set available memory to physical memory less 8MB. As an mprime user I edit the local.ini file all the time. Per your notes I upped *Memory to 466. -- [EMAIL PROTECTED] - HMC UNIX Systems Manager _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 on PIII or P4?
- Original Message - From: Chris Marble [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Tuesday, March 04, 2003 4:00 PM Subject: Mersenne: P-1 on PIII or P4? I've got a couple of P4s that I can use on weekends. I've been using them to finish off exponents that my PIIIs were working on. Is that the right order? P-1 on the PIII and then the rest on the P4. I want to maximize my output. Hmmm. That's an intriguing question. Based upon what I know of the algorithms involved, it *ought* to be the case that you should do any P-1 work on the machine which can give it the most memory, irrespective of processor type. However, some time ago, I was given some information on the actual P-1 bounds chosen for exponents of various sizes, running on systems of various processor/memory configurations. It turns out that P4s choose *much deeper* P-1 bounds than do other processors. For example: 8233409,63,0,Robreid,done,,4,45,,Athlon,1.0/1.3,90 8234243,63,0,Robreid,done,,4,45,,Celeron,540,80 8234257,63,0,Robreid,done,,45000,742500,,P4,1.4,100 The last figure is the amount of available memory. The differences between 80MB and 100MB, and between 8233409 and 8234257 are too small to account for the near doubling in the B2 bound in the case of a P4. Since I do not understand why this should be the case, I don't know for certain, but it looks like a P4 is better for P-1. Whichever machine you choose for P-1, always give it absolutely as much memory as you can without thrashing. There is an upper limit to how much it will use, but this is probably in the gigabytes for exponents in even the current DC range. Memory is not relevant for factorisation, the actual LL test, or stage 1 of the P-1. It used to be the case that TF should be avoided on a P4, but that part of this processor's code has been improved in recent versions, so I don't know if this is still the case. If you ever get an exponent that requires both P-1 and extra TF, do the P-1 before the last bit of TF. This doesn't alter the likelihood of finding a factor, but if you do find one, on average you will find it earlier, and for less work. There are a number of ranges of exponent sizes where it is better to avoid using P4s. George posted the following table some time ago (Best viewed with a fixed width font.) FFT v21 v22.8v21 SSE2 v22.8 SSE2 262144 5255000 5255000 5185000 5158000 327680 652 6545000 6465000 6421000 393216 776 7779000 769 7651000 458752 904 9071000 897 8908000 524288 1033 1038 1024 1018 655360 1283 1289 1272 1265 786432 1530 1534 1516 1507 917504 1785 1789 1766 1755 1048576 2040 2046 2018 2005 1310720 2535 2539 2509 2493 1572864 3015 3019 2992 2969 1835008 3510 3520 3486 3456 2097152 4025 4030 3978 3950 2621440 5000 5002 4935 4910 3145728 5940 5951 5892 5852 3670016 6910 6936 6865 6813 4194304 7930 7930 7836 7791 If you are testing an exponent which is greater than an entry in the fifth column, but less than the corresponding entry int the third column, then avoid using a P4. This applies to all types of work. Where the considerations discussed above conflict, I don't know what the balance is between them. HTH -- [EMAIL PROTECTED] - HMC UNIX Systems Manager Daran G. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 on PIII or P4?
On Thursday 06 March 2003 13:03, Daran wrote: Based upon what I know of the algorithms involved, it *ought* to be the case that you should do any P-1 work on the machine which can give it the most memory, irrespective of processor type. ... assuming the OS allows a single process to grab the amount of memory configured in mprime/Prime95 (this may not always be the case, at any rate under linux, even if adequate physical memory is installed.) However, some time ago, I was given some information on the actual P-1 bounds chosen for exponents of various sizes, running on systems of various processor/memory configurations. It turns out that P4s choose *much deeper* P-1 bounds than do other processors. For example: 8233409,63,0,Robreid,done,,4,45,,Athlon,1.0/1.3,90 8234243,63,0,Robreid,done,,4,45,,Celeron,540,80 8234257,63,0,Robreid,done,,45000,742500,,P4,1.4,100 The last figure is the amount of available memory. The differences between 80MB and 100MB, and between 8233409 and 8234257 are too small to account for the near doubling in the B2 bound in the case of a P4. Yes, that does seem odd. I take it the software version is the same? The only thing that I can think of is that the stage 2 storage space for temporaries is critical for exponents around this size such that having 90 MBytes instead of 100 MBytes results in a reduced number of temporaries, therefore a slower stage 2 iteration time, therefore a significantly lower B2 limit. I note also that the limits being used are typical of DC assignments. For exponents a bit smaller than this, using a P3 with memory configured at 320 MBytes (also no OS restriction plenty of physical memory to support it) but requesting first test limits (Pfactor=exponent,tfbits,0) I'm getting B2 ~ 20 B1 e.g. [Thu Mar 06 12:07:46 2003] UID: beejaybee/Simon1, M7479491 completed P-1, B1=9, B2=1732500, E=4, WY1: C198EE63 The balance between stage 1 and stage 2 should not really depend on the limits chosen since the number of temporaries required is going to be independent of the limit, at any rate above an unrealistically small value. Why am I bothering about this exponent? Well, both LL DC are attributed to the same user... not really a problem, but somehow it feels better to either find a factor or have an independent triple-check when this happens! Regards Brian Beesley _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 on PIII or P4?
Daran wrote: Whichever machine you choose for P-1, always give it absolutely as much memory as you can without thrashing. There is an upper limit to how much it will use, but this is probably in the gigabytes for exponents in even the current DC range. So I should use the PIII with 1 3/4 GB of RAM to do nothing but P-1. It's an older Xeon with 2MB cache. Will that help too? How would I do this? I see the following in undoc.txt: You can do P-1 factoring by adding lines to worktodo.ini: Pfactor=exponent,how_far_factored,has_been_LL_tested_once For example, Pfactor=1157,64,0 There are a number of ranges of exponent sizes where it is better to avoid using P4s. George posted the following table some time ago (Best viewed with a fixed width font.) FFT v21 v22.8v21 SSE2 v22.8 SSE2 262144 5255000 5255000 5185000 5158000 327680 652 6545000 6465000 6421000 393216 776 7779000 769 7651000 458752 904 9071000 897 8908000 524288 1033 1038 1024 1018 655360 1283 1289 1272 1265 786432 1530 1534 1516 1507 917504 1785 1789 1766 1755 1048576 2040 2046 2018 2005 1310720 2535 2539 2509 2493 1572864 3015 3019 2992 2969 1835008 3510 3520 3486 3456 2097152 4025 4030 3978 3950 2621440 5000 5002 4935 4910 3145728 5940 5951 5892 5852 3670016 6910 6936 6865 6813 4194304 7930 7930 7836 7791 If you are testing an exponent which is greater than an entry in the fifth column, but less than the corresponding entry int the third column, then avoid using a P4. This applies to all types of work. Useful info. I've got 2 DCs in one of the ranges but one computer's a PIII and the other's a Dec Alpha running Mlucas-2.7b-gen-5x. -- [EMAIL PROTECTED] - HMC UNIX Systems Manager _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1 on PIII or P4?
I've got a couple of P4s that I can use on weekends. I've been using them to finish off exponents that my PIIIs were working on. Is that the right order? P-1 on the PIII and then the rest on the P4. I want to maximize my output. -- [EMAIL PROTECTED] - HMC UNIX Systems Manager My opinions are my own and probably don't represent anything anyway. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 and non k-smooth factors
- Original Message - From: Alexander Kruppa [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Sent: Wednesday, December 11, 2002 12:11 PM Subject: Re: Mersenne: P-1 and non k-smooth factors Daran wrote: Ad far as I can see it is a regular PostScript. I don't know if the extra l indicates a variant of the format, but the file behaves normally in ghostscript/when printing. OK I can read it now. Understanding it is another matter entirely. However, primitive factors of x^n-y^n must be ==1 (mod n) and so the factors do not behave particularly randomly at all... This doesn't make sense. Any primitive factor f of x^n-y^n is a primitive factor of x^(kn)-y^(kn) for any k, so the above would imply that f==1 (mod kn) for any k. What am I missing? A prime factor of x^n-y^n is called primitive if it divides no x^m-y^m with 0mn. And thus, with x and y distinct (mod p) and neither a multiple of p, Right. I was confusing 'primitive' with 'irreducible'. BTW, I don't think I've thanked you enough for your earlier replies on this subject, which have contributed enormously to my understanding of the problem. [snip lengthy analysis which I will need to study] This causes clumping of primes included by Suyama's powers (some primes appearing often, others not at all) and reduces their efficiency... Could we use this somehow? Would it be worth skipping primes in the B1-B2 range that were highly likely to crop up in a Suyama power? Yes, or compute which ones do actually apprear and eliminate them from the stage 2 primes... I was under the impression that this might be too expensive. ...Another idea is to exclude from stage 2 those primes that appear as factors of (x+y). For D=2310 and B2/B1=100, primes between 13 and 97 may divide (x+y) so that the cofactor is a prime in the stage 2 interval. That requires a bitfield of all the stage 2 primes that must be processed top down which makes getting the prime pairing right more difficult. I tried that once in my own P-1 factorer but it had a bug that I didn't find yet. The saving was iirc ~10% of the multiplies in stage 2. In my experience the program chooses B2 10-20 times the size of B1. All this can be generalised. The goal is to choose a subset of NxN (pairs of positive integers) so that the efficiency is maximal for the factor we hope to find. Of course we won't know the precise factor we want to find, but we can integrate over all remaining candidate factor weighted with their respective probability of dividing the input number. I love this idea! An simple algorithm would be to take all the pairs (x,y) with x=mD for a hightly composite D and yD, gcd(y,D)=1 (as in the current stage 2, but not only pairs where x-y is a prime), factoring all the x^n-y^n over primes B1 (and below some other bound)... Call this other bound C. ...and making a bipartite graph of (x,y) pairs connected with their factors. A greedy algorithm would choose the best (x,y) pair (i.e. where the sum of reciprocals of the connected prime factors maximal) and remove those prime factors and their edges from the graph. Repeat until the best remaining (x,y) pair is worse that some chosen limit. Call this limit epsilon. This assumes that each (x,y) pair costs the same, but in fact, there is a cost associated with increasing x. I doubt that the greedy algo is optimal, but it should be pretty fast, except for the factoring part maybe. I'm certain it wouldn't be. For a start, if you don't take this extra cost into account, and you choose C too high, then your largest x may be much higher than is desirable. If you do take the extra cost into account, by attaching it to each x larger than any previous x, then you'll tend to fill up your bit array from the bottom, and lose much of the benefit of the smaller factors of the larger candidates. Better would be to use a two-pass greedy algorithm. The first using a very large C 1/epsilon, but including the extra cost of large x. Use the result of this to reset C to be just large enough to accommodate the largest x, then redo the algorithm ignoring that extra cost. You might be able to improve it further by choosing a slightly larger C for the second pass, than the one suggested by the first, or you could implement a multipass algorithm as follows:- Choose limits C 1/epsilon and B2 initially equal to B1. Then for each pass, factor in the extra cost only for those x (larger than any previous x) which are also larger than B2. Use the result of each pass to reset B2 to accommodate the largest x. The result should be independent of C, provided the latter is large enough. I doubt that this would be optimal, even if iterated to equilibrium. The problem bears the hallmarks of computational intractability. The so created plan can be stored and distribued to factoring clients. You mean the bitmap of (x,y) pairs? You'd need
Re: Mersenne: P-1 and non k-smooth factors
Daran wrote:
Peter Montgomery's dissertation, An FFT Extension to the Elliptic Curve
Method of Factorization,
ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz ,
What do I need to read a psl file?
Ad far as I can see it is a regular PostScript. I don't know if the
extra l indicates a variant of the format, but the file behaves
normally in ghostscript/when printing.
In addition to the remarks you go on to make, this will only be true for
primes the algebraic factor; intuitively I feel it ought only to
be true
for primes sqrt(factor) ~= x (in the case of x^6-y^6). All these
will be
B2.
However, primitive factors of x^n-y^n must be ==1 (mod n) and so the
factors do not behave particularly randomly at all...
This doesn't make sense. Any primitive factor f of x^n-y^n is a
primitive
factor of x^(kn)-y^(kn) for any k, so the above would imply that f==1
(mod
kn) for any k.
What am I missing?
A prime factor of x^n-y^n is called primitive if it divides no x^m-y^m
with 0mn. And thus, with x and y distinct (mod p) and neither a
multiple of p,
x^n-y^n == 0 (mod p)
x^n == y^n (mod p)
(x/y)^n == 1 (mod p)
Since p is a primitive factor, ord(x/y) = n and n|p-1.
The probability that p|(x^n-y^n) is gcd(n, p-1)/(p-1) if x and y are
chosen independently at random from the residues != 0 (mod p).
Choose some value for x and let y range over all the possible residues
(mod p). x^n and y^n both go into the subgroup of d-th powers (mod p)
where d=gcd(n, p-1) and the order of that subgroup is (p-1)/d. As y
ranges over all the possible residues (mod p), y^n visits every element
in the subgroup d times and so has d matches with x^n. For a randomly
chosen y the chance of a match x^n==y^n is d/(p-1), independent of x.
If we compute k different values of x^n-y^n in stage 2, the probability
of the prime p showing up at least once as a factor among them should be
1-(1-gcd(n, p-1)/(p-1))^k.
However, in the P-1 stage 2 we don't choose x and y at random from all
the possible residues (mod p). We want the analysis for primes B2, and
x=mD B2 and yD. How this changes the analysis is not quite clear to
me.. at least the probability that the linear factors generate p should
be subtracted as we know that their values are p. That gives a
probability of 1-(1-(gcd(n, p-1)-2)/(p-1))^k for odd n. As you pointed
out, the values of the other small terms may not be large enough to
justify a probability of 1/p for p dividing them, but I think the
difference will not be very great.
I have hacked up a small program to determine which primes (within a
given interval) appear as factors of (mD)^n-d^n for mDB2, gcd(d,D)=1
and given n, and the counts come out reasonably close to the predicted
values. I.e. for D=2310, B2=100 and n=4, examining primes in
[1005000, 200] (only the x^2+y^2 term can produce these primes), I
get 9829 distinct primes that appear as factors vs an predicted 8737.26.
The sum of reciprocals of the primes that appear as factors is 0.007096,
vs predicted 0.006270. Curiously, the actual counts are higher than the
predicted values.
For B1=10, D=2310, n=4 and p in [1000, 11000], the number of
primes that appear as factors is 2880 vs 2926.47 and the sum of
reciprocals is 0.000111 vs predicted 0.000114.
For B2=10, D=2310, n=6, primes in [1000, 11000], I get 5720
distinct primes as factors vs 5847.96 predicted, sum of reciprocals
0.000227 vs 0.000227. The predicted values seem to become more accurate
for larger n and p.
These figures seem to support the gcd-2 idea, but I'd feel better if
there were some theoretical grounds to it.
If we accept this estimate, the total chance of finding a factor f for
P-1 with B1 and B2 bounds, Suyama's power n and k distinct (x^n-y^n)
values computed in stage 2 comes out like
Pr[f-1 is B1-smooth] + (1 - Pr[f-1 is B1-smooth]) * Sum_{pB1} 1/p *
Pr[p included] * Pr[(f-1)/p, Stage1]
where Pr[p included] is 1 for p=B2 and 1-(1-(gcd(n, p-1)-2)/(p-1))^k
for pB2.
The goal would then be to maximize the efficiency
(Pr[hit in stage 1] + Pr[hit in stage 2]) / (time for stage 1 + Pr[no
hit in stage 1] * time for stage2 ).
This causes clumping of primes included
by Suyama's powers (some primes appearing often, others not at all) and
reduces their efficiency...
Could we use this somehow? Would it be worth skipping primes in the
B1-B2
range that were highly likely to crop up in a Suyama power?
Yes, or compute which ones do actually apprear and eliminate them from
the stage 2 primes. Another idea is to exclude from stage 2 those primes
that appear as factors of (x+y). For D=2310 and B2/B1=100, primes
between 13 and 97 may divide (x+y) so that the cofactor is a prime in
the stage 2 interval. That requires a bitfield of all the stage 2 primes
that must be processed top down which makes getting the prime pairing
right more difficult. I tried that once in my own P-1 factorer but it
had a bug that I
Re: Mersenne: P-1 and non k-smooth factors
- Original Message - From: Alexander Kruppa [EMAIL PROTECTED] To: George Woltman [EMAIL PROTECTED] Cc: Daran [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Thursday, December 05, 2002 12:18 PM Subject: Re: Mersenne: P-1 and non k-smooth factors George Woltman wrote: At 10:31 PM 12/3/2002 +, Daran wrote: The analysis is more complex than this. It really depends on the prime [...] I'd be greatly interested in such a study. Peter Montgomery's dissertation, An FFT Extension to the Elliptic Curve Method of Factorization, ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz , What do I need to read a psl file? contains in chapter 5 an analysis of Suyama's powers and Dickson polynomials for the Brent-Suyama extension to stage 2. The number of algebraic factors in the Suyama/Dickson polynomial is the interesting part, i.e. That was the conclusion I came to. (x^6-y^6) = (x-y)*(x+y)*(x^2+x*y+y^2)*(x^2-y*x+y^2) where (x-y) and (x+y) usually are both =B2, so primes B2 have two opportunities of appearing as prime factors of algebraic factors of the Suyama polynomial. If we assume that the values taken on by the algebraic factors of the poly behave like integers chosen uniformly at random, we could conclude that a prime pB2 appears in (x^6-y^6) with probability 1-(1-1/p)^2 ~= 2/p. In addition to the remarks you go on to make, this will only be true for primes the algebraic factor; intuitively I feel it ought only to be true for primes sqrt(factor) ~= x (in the case of x^6-y^6). All these will be B2. However, primitive factors of x^n-y^n must be ==1 (mod n) and so the factors do not behave particularly randomly at all... This doesn't make sense. Any primitive factor f of x^n-y^n is a primitive factor of x^(kn)-y^(kn) for any k, so the above would imply that f==1 (mod kn) for any k. What am I missing? Primes p where p-1 has many factors in common with n have a better chance of appearing as factors, while those with p-1 coprime to n can only appear as factor of (x+y)(x-y) and are thus p=B2... Hence E should be chosen to be highly composite, which conclusion I had already come to, from consideration of the number of algebraic factors. This causes clumping of primes included by Suyama's powers (some primes appearing often, others not at all) and reduces their efficiency... Could we use this somehow? Would it be worth skipping primes in the B1-B2 range that were highly likely to crop up in a Suyama power? ...Apparantly Dickson polynomials do better, but I don't really know much about them. Montgomery's dissertation is probably a very good starting point if someone would like to investigate the optimal choice for Suyama's powers (or Dickson polynomials) for Prime95. As soon as I can figure out how to read it. Alex Daran _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 and non k-smooth factors
- Original Message - From: Brian J. Beesley [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Thursday, December 05, 2002 12:31 PM Subject: Re: Mersenne: P-1 and non k-smooth factors There is obviously a tradeoff here between increasing B2 and simplifying E and increasing E compensating for increased run time by lowering B2. However it does seem to be obvious that increasing E always has to be paid for in increased memory requirements. It's the larger values of D, rather than E which use the most memory. The client rarely uses all it's allowed, except in the low memory situations. For example, it needs 46 temps to run at D=150, E=2. If only 45 temps were available, the client, as currently configured, would run at D=120, E=2 using 38 temps. But it could afford to run at D=120, E=6 (42 temps) or even D=120, E=8 (44 temps), although, for reasons given, I don't think the latter would be a good idea. For exponents around 8M, this is not a particular issue. However there is a real, practical constraint so far as Prime95/mprime is concerned - the entire _virtual_ address space is limited to 4 GBytes by the 32 bit address bus, and the OS kernel claims some (usually half) of this, so that the total memory usable by a single process is limited to 2 GBytes. (There is a big memory variant of the linux kernel which expands this to 3 GBytes, but the point still stands). As mentioned by other list members, there's also a 64GB version, which, apparently, doesn't work. I expect they'll have it working by the time 4GB systems become commonplace. Since, on my practical experience, a 17M exponent will quite happily use ~ 800 MBytes in P-1 stage 2,... At 7186MB per temp, that sounds like a plan of D=420, E=4 (104 temps) ...the 32 bit address bus may well be a limiting factor within the exponent range covered by current versions of Prime95/mprime. Easily, even at 17M. To run with D=2310, E=12 requires 496 temps. It would go higher, if the memory was there. D is capped at sqrt(B2-B1). [...] What I was thinking of doing was writing a program to read in the factor database from, say, 1M up (to avoid any factors found by ECM), discard .any below the TF limit, then try to find the smallest B2 which would yield the factor given E=4, 6, 8, 10, or 12. This won't tell us the absolute frequency of extended factors, but the relative frequencies would test, and perhaps quantify, my conjecture about the relative effectiveness of these values. Why not simply use a random sample of numbers of suitable size? Say around 2^41, you are looking for factors from 2^65 upwards with exponents around 2^23. P-1 is really about the factors of k in f=2kp+1 since the +1 is implicit and the 2p comes out in the wash. (Does the size of the numbers in the sample actually matter from the theoretical point of view?) No, but if I use random numbers rather than genuine factors of Mersenne numbers, then the suspicion will be there that there's something special about the latter which invalidates the result. But it would probably be sensible to try this first. Regards Brian Beesley Daran G. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 and non k-smooth factors
- Original Message - From: George Woltman [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Thursday, December 05, 2002 2:35 AM Subject: Re: Mersenne: P-1 and non k-smooth factors The analysis is more complex than this... I never doubted that. :-) [...] Why not take your example: on an 8.1M exponent, B1=45000, B2=731250 and varying values for D and E, I get the following results D E Stage 2 transforms 420 2 93946 420 4 98618 (the default for my memory settings) Done one more: 420 6 103746 It's looking very linear. and write a program that emulates stage 2's selection of (x^E - d^E), does a prime factorization of the value, and keeps track of which factors above B2 get included. It should be possible to calculate your increased chance of finding a factor (someone please fill in the formula here). That's a rather more extensive programming job than the one I had in mind. It would also be expensive at runtime, with a prime factorisation in every cycle. What I was thinking of, is to take the k of known Mersenne factors, or at Brian's suggestion, random integers of an appropriate size, factor them to obtain the second largest and largest factor, a and b, say, then emulate the stage 2 selection of (x^E - d^E) from B1=a through to B2=b or until I find one divisible by b, which ever comes first. Regards Daran _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 and non k-smooth factors
George Woltman wrote: At 10:31 PM 12/3/2002 +, Daran wrote: The analysis is more complex than this. It really depends on the prime [...] I'd be greatly interested in such a study. Peter Montgomery's dissertation, An FFT Extension to the Elliptic Curve Method of Factorization, ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz , contains in chapter 5 an analysis of Suyama's powers and Dickson polynomials for the Brent-Suyama extension to stage 2. The number of algebraic factors in the Suyama/Dickson polynomial is the interesting part, i.e. (x^6-y^6) = (x-y)*(x+y)*(x^2+x*y+y^2)*(x^2-y*x+y^2) where (x-y) and (x+y) usually are both =B2, so primes B2 have two opportunities of appearing as prime factors of algebraic factors of the Suyama polynomial. If we assume that the values taken on by the algebraic factors of the poly behave like integers chosen uniformly at random, we could conclude that a prime pB2 appears in (x^6-y^6) with probability 1-(1-1/p)^2 ~= 2/p. However, primitive factors of x^n-y^n must be ==1 (mod n) and so the factors do not behave particularly randomly at all. Primes p where p-1 has many factors in common with n have a better chance of appearing as factors, while those with p-1 coprime to n can only appear as factor of (x+y)(x-y) and are thus p=B2. This causes clumping of primes included by Suyama's powers (some primes appearing often, others not at all) and reduces their efficiency. Apparantly Dickson polynomials do better, but I don't really know much about them. Montgomery's dissertation is probably a very good starting point if someone would like to investigate the optimal choice for Suyama's powers (or Dickson polynomials) for Prime95. Alex _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 and non k-smooth factors
On Wednesday 04 December 2002 21:46, Daran wrote: [... snip ...] ...though I think there needs to be a careful analysis as to what the extra computation time for actual E values might be... I agree. My tests have been limited to exponents in the 8.1M range, for no particular reason than those are the ones I am doing. Well, you seem to have more experimental evidence than anyone else. As for the theory - whilst there is adequate theoretical modelling of the expected distributions of the largest and second-largest factors of arbitary numbers, I couldn't find much in the literature which would help predict how many extra factors you would expect to find with different values of E. There is obviously a tradeoff here between increasing B2 and simplifying E and increasing E compensating for increased run time by lowering B2. However it does seem to be obvious that increasing E always has to be paid for in increased memory requirements. For exponents around 8M, this is not a particular issue. However there is a real, practical constraint so far as Prime95/mprime is concerned - the entire _virtual_ address space is limited to 4 GBytes by the 32 bit address bus, and the OS kernel claims some (usually half) of this, so that the total memory usable by a single process is limited to 2 GBytes. (There is a big memory variant of the linux kernel which expands this to 3 GBytes, but the point still stands). Since, on my practical experience, a 17M exponent will quite happily use ~ 800 MBytes in P-1 stage 2, the 32 bit address bus may well be a limiting factor within the exponent range covered by current versions of Prime95/mprime. George - is there a sanity check on the memory constraints? If we _don't_ have to worry about memory, at some point it becomes cost-effective to run ECM with small limits instead of P-1 with much larger limits. And ECM can easily dig out some factors which are more or less inaccessible with P-1. I was under the impression the ECM was only practical for small exponents well below the current DC range. ECM stage 2 quickly becomes impractical with larger exponents because of the memory requirement. ECM stage 1 is not particularly heavy on memory. Running stage 1 only with small limits on DC sized exponents is feasible ... it's just a question of whether the extra computation costs would be justified by the discovery of factors which were inaccessible to trial factoring or P-1. [... snip ... I don't disagree but the basic argument is the same as above] In 2 out of the 29 stage 2 factors I have found so far using E=4, k has not been smooth to B2. This suggests that increasing E from 4 to 12 could yield about 20% more factors. I've done a few tests with a modified and recompiled client, which suggests that it would worth it even if E=12 yielded as few as 10% more factors, though I need to investigate this further. That's a very small sample. It's the only sample I have. I'm trying to increase it by doing some P-1s on exponents in the 1.2M range which have only been tested to B1=B2=1000. How many of these were found during stage 2? (If half your factors were found during P-1 stage 2, and half of those used E=4 or greater, then your single 'surprising' factor would not be out of line with my two.) Well, actually I was doing the test in several steps, with gradually increasing B1 then gradually increasing B2 - the cost of the GCDs with small exponents is very small so it's worth checking fairly frequently to see if a factor is available. I don't have the full data to hand but I do have some of it. The distribution of 22 factors found at various limits was as follows: stage 1 B1 = 50 1 stage 1 B1 = 100 1 stage 2 B1 = 100 B2 = 4004 stage 2 B1 = 100 B2 = 1000 5 stage 2 B1 = 100 B2 = 2500 11 Some easier factors were in all probability missed because someone had found them by running P-1 with smaller limits before I started. I have a total of 57 factors, including one found earlier today. A few were by TFs, 30 in P-1 stage 2 (including today's) and the rest in stage 1. OK. Actually for about the last three weeks I've been running P-1 with standard limits on some exponents in the range 2M-6M (those exponents where all the entries in lucas_v have the same user ID, with the exception of a very few where P-1 was already completed to reasonable limits). The system I'm using is configured with mem=224 MBytes (about as much as I dare on a 512 MBytes dual-processor system). I'm getting E=4 logged fairly consistently. The results so far are: No factor found, 130 Factor found in stage 1, 2 Factor found in stage 2, 6 - all smooth to B limits used. One of the factors found in stage 1 is _very_ interesting: 6807510023694431 is a factor of M(5993719) (smooth to B1=353) The factoring depth database had this trial factored
RE: Mersenne: P-1 and non k-smooth factors
From: Brian J. Beesley [mailto:[EMAIL PROTECTED]] usable by a single process is limited to 2 GBytes. (There is a big memory variant of the linux kernel which expands this to 3 GBytes, but the point still stands). FWIW, WinNT and its descendents can be booted with /3gb in boot.ini, whereupon a single process may use up to 3G of physical memory. This switch tends to be used mainly on big SQL server boxes but I found it necessary when running very large filtering and linear algebra jobs for NFS factorizations. For this I needed a very large chunk (1Gb) of *contiguous* virtual memory and although the standard boot mode would let me have up to 2G of VM, system DLLs were loaded somewhere near the 1G region, thereby fragmenting memory. Booting with /3gb placed the OS well out of the way and let me have the space I needed. Paul _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 and non k-smooth factors
Isn't this (3GB user mode) only supported on Windows NT Advanced Server? (which is probably free for you to use but for everyone else costs the same as a new car!) If it isn't then I've encountered some people who will wish they'd have known about this a long time ago :-) Paul Leyland wrote: From: Brian J. Beesley [mailto:[EMAIL PROTECTED]] usable by a single process is limited to 2 GBytes. (There is a big memory variant of the linux kernel which expands this to 3 GBytes, but the point still stands). FWIW, WinNT and its descendents can be booted with /3gb in boot.ini, whereupon a single process may use up to 3G of physical memory. This switch tends to be used mainly on big SQL server boxes but I found it necessary when running very large filtering and linear algebra jobs for NFS factorizations. For this I needed a very large chunk (1Gb) of *contiguous* virtual memory and although the standard boot mode would let me have up to 2G of VM, system DLLs were loaded somewhere near the 1G region, thereby fragmenting memory. Booting with /3gb placed the OS well out of the way and let me have the space I needed. -- === Gareth Randall === _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: P-1 and non k-smooth factors
Do not add the /3GB switch if you are running Windows 2000 Server, Microsoft Small Business Server 2000, or Microsoft BackOffice Server 2000. This switch is designed for use only with Windows 2000 Advanced Server and above. (from the MS knowledge base). Same applies to NT 4, where it only works with the Enterprise edition. -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]] On Behalf Of Gareth Randall Sent: Thursday, December 05, 2002 2:25 PM To: Paul Leyland Cc: Brian J. Beesley; Daran; [EMAIL PROTECTED] Subject: Re: Mersenne: P-1 and non k-smooth factors Isn't this (3GB user mode) only supported on Windows NT Advanced Server? (which is probably free for you to use but for everyone else costs the same as a new car!) If it isn't then I've encountered some people who will wish they'd have known about this a long time ago :-) _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 and non k-smooth factors
On Tuesday 03 December 2002 22:31, Daran wrote: [... snip ...] For clarity, let's write mD as x, so that for a Suyama power E, the exponent (x^E - d^E) is thrown into the mix when either x-d or x+d is prime in [B1...B2], (and only once if both are prime). This works because (provide E is even) x^E - d^E = (x-d)*(x+d)*C where C is a sum of higher order terms. The benefit of prime-pairing arises when E=2. The cost of higher E is AFAICS linear in multiplications. The benefit of higher E comes from any additional factors thrown into the mix by C. This benefit is greatest if C has factors slightly B2 For E=4, C = (x^2 + d^2) For E=6, C = (x^4 + x^2d^2 + d^4) = (x^2 + xd + d^2)*(x^2 - xd + d^2) For E=8, C = (x^2 + d^2)*(x^4 + d^4) I can't think of any reason why either of the two algebraic factors of C when E is 6 should be any better or worse than the single irreducible factor when E=4. And there are two of them. This suggests to me that E=6 should be about twice as effective as E=4 in providing additional factors, at about twice the cost (over and above the 'cost' of E=2). If this is correct, then it will always be worth going to E=6, whenever it is worth going to E=4, (provided there is sufficient memory to do so). Let's see if I get this right. Overwhelmingly, the factors produced by P-1 factoring come out because they are smooth to the limits selected. The fraction that comes out because of the extension is 10%. To double that fraction (i.e. to increase the total number of factors found by 10%) we have to double the stage 2 run time? Doesn't sound that great to me, even without worrying about memory considerations. If we're talking about the _extra_ computation time in stage 2 then obviously the suggestion makes a lot more sense - though I think there needs to be a careful analysis as to what the extra computation time for actual E values might be (as opposed to a rather simplistic linear model, which fails to take into account that some of the temporaries needed for small E probably drop out pretty well for free). If we _don't_ have to worry about memory, at some point it becomes cost-effective to run ECM with small limits instead of P-1 with much larger limits. And ECM can easily dig out some factors which are more or less inaccessible with P-1. [... snip ... I don't disagree but the basic argument is the same as above] In 2 out of the 29 stage 2 factors I have found so far using E=4, k has not been smooth to B2. This suggests that increasing E from 4 to 12 could yield about 20% more factors. I've done a few tests with a modified and recompiled client, which suggests that it would worth it even if E=12 yielded as few as 10% more factors, though I need to investigate this further. That's a very small sample. Some time ago I found a considerable number of first factors for exponents in the range 100,000-150,000 using P-1 with limits up to B1=10^6, B2=25x10^6. The results.txt file doesn't record the E value used; though I did have tons of memory available (in relation to the exponent size) and seem to remember something about wondering what E=12 meant in the console output. Or maybe I'm confusing this with recollections about running ECM? My records show 67 factors found; I mailed George on one occasion because P-1 found a factor which surprised me, but I don't think it happened twice. Incidentally I found a factor only yesterday using P-1 on a production system: [Tue Dec 3 07:54:38 2002] P-1 found a factor in stage #2, B1=22, B2=5665000. UID: beejaybee/Procyon, M17359099 has a factor: 312980494172935109497751 Again no mention of E. If it helps, this system was set up to use 384 MBytes memory. In any case this should have come out without extensions; B1=65267 B2=3077953 is sufficient to find the factor with the standard stage 2 algorithm. Would there be any means of retrieving actual factors found using P-1 and the E values used from the server logs? The problem otherwise is that, so far as the database is concerned, once a factor is found, nobody cares much how! Regards Brian Beesley _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 and non k-smooth factors
- Original Message - From: Brian J. Beesley [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Wednesday, December 04, 2002 2:55 PM Subject: Re: Mersenne: P-1 and non k-smooth factors Let's see if I get this right. Overwhelmingly, the factors produced by P-1 factoring come out because they are smooth to the limits selected. The fraction that comes out because of the extension is 10%. To double that fraction (i.e. to increase the total number of factors found by 10%) we have to double the stage 2 run time? That's not what I meant. Doesn't sound that great to me, even without worrying about memory considerations. If we're talking about the _extra_ computation time in stage 2 then obviously the suggestion makes a lot more sense - Yes. If it takes Time t to run a stage 2 with E=2, and t+d to run it with E=4, then we should be willing to spend t+2d to run it with E=6, and t+5d to run it with E=12, which, as far as I can see, is approximately how the cost increases anyway. I've only had time to run a few tests, but on an 8.1M exponent, B1=45000, B2=731250 and varying values for D and E, I get the following results D E Stage 2 transforms 420 2 93946 420 4 98618(the default for my memory settings) 42012 121520 210 4 104272 150 4 111962 120 4 116464 I did one with D=420, E=6, but I don't seem to have made a note of it. Nor did I record running times, because I was using the computer to do other things. Transforms ought to be reasonably proportionate. The first three tests are consistent with the cost increasing linearly with E, while the latter show the penalty of lowering the memory. (Note that an unmodified client would drop to E=2 below D=210, but I wanted to see just the effect of lowering D) With D=420, E=12 is over 23% dearer than the E=4 which is currently used. However, this does *not* mean that it needs to find more 23% more factors to be worthwhile. If guess_pminus1_bounds is altered to be aware of D and E, then it compensates for the extra cost by reducing B2, trading 'normal' factors for extended ones. My (limited) tests suggest, as I said, that 2% more factors with E=6 or 10% more factors with E=12 would be a worthwhile trade. (This assumes that my formula for estimating the number of squarings is accurate, something I have not checked.) ...though I think there needs to be a careful analysis as to what the extra computation time for actual E values might be... I agree. My tests have been limited to exponents in the 8.1M range, for no particular reason than those are the ones I am doing. (as opposed to a rather simplistic linear model, which fails to take into account that some of the temporaries needed for small E probably drop out pretty well for free). I don't understand. If we _don't_ have to worry about memory, at some point it becomes cost-effective to run ECM with small limits instead of P-1 with much larger limits. And ECM can easily dig out some factors which are more or less inaccessible with P-1. I was under the impression the ECM was only practical for small exponents well below the current DC range. [... snip ... I don't disagree but the basic argument is the same as above] In 2 out of the 29 stage 2 factors I have found so far using E=4, k has not been smooth to B2. This suggests that increasing E from 4 to 12 could yield about 20% more factors. I've done a few tests with a modified and recompiled client, which suggests that it would worth it even if E=12 yielded as few as 10% more factors, though I need to investigate this further. That's a very small sample. It's the only sample I have. I'm trying to increase it by doing some P-1s on exponents in the 1.2M range which have only been tested to B1=B2=1000. Some time ago I found a considerable number of first factors for exponents in the range 100,000-150,000 using P-1 with limits up to B1=10^6, B2=25x10^6. The results.txt file doesn't record the E value used; though I did have tons of memory available (in relation to the exponent size) and seem to remember something about wondering what E=12 meant in the console output. Or maybe I'm confusing this with recollections about running ECM? That's possible as E is also used in the ECM code. But E=12 output from a P-1 means what it says. If the value of E is not output, then it means E=2 (or perhaps E=1, but I've never tried using that little memory.) E (2) is recorded in the results.txt file by recent clients, so either the version of the client you were using then didn't record it, or your memory setting didn't allow E2. My records show 67 factors found; I mailed George on one occasion because P-1 found a factor which surprised me, but I don't think it happened twice. How many of these were found during stage 2? (If half your factors were found during
Re: Mersenne: P-1 and non k-smooth factors
At 10:31 PM 12/3/2002 +, Daran wrote: For clarity, let's write mD as x, so that for a Suyama power E, the exponent (x^E - d^E) is thrown into the mix when either x-d or x+d is prime in [B1...B2], (and only once if both are prime). This works because (provide E is even) x^E - d^E = (x-d)*(x+d)*C where C is a sum of higher order terms. The benefit of prime-pairing arises when E=2. The cost of higher E is AFAICS linear in multiplications. The benefit of higher E comes from any additional factors thrown into the mix by C. This benefit is greatest if C has factors slightly B2 For E=4, C = (x^2 + d^2) For E=6, C = (x^4 + x^2d^2 + d^4) = (x^2 + xd + d^2)*(x^2 - xd + d^2) For E=8, C = (x^2 + d^2)*(x^4 + d^4) The analysis is more complex than this. It really depends on the prime factorization of these algebraic factors. If an algebraic factor's prime factorization contains factors all below B2, then the algebraic factor does you no good. Why not take your example: on an 8.1M exponent, B1=45000, B2=731250 and varying values for D and E, I get the following results D E Stage 2 transforms 420 2 93946 420 4 98618 (the default for my memory settings) and write a program that emulates stage 2's selection of (x^E - d^E), does a prime factorization of the value, and keeps track of which factors above B2 get included. It should be possible to calculate your increased chance of finding a factor (someone please fill in the formula here). Then you can run this on several D,E options and compare it to your count of FFT transforms and come up with the optimal choice of D and E. I'd be greatly interested in such a study. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 and non k-smooth factors
- Original Message - From: George Woltman [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Thursday, November 28, 2002 2:18 AM Subject: Re: Mersenne: P-1 and non k-smooth factors At 06:05 PM 11/27/2002 +, Daran wrote: if (D = 180) E = 2; else if (D = 420) E = 4; else if (D = 2310) E = 12; else if (D = 6930) E = 30; else E = 48; I understand why it chooses the values of D that it does, but why these values of E? I understand why E must be even, and that higher powers ought to be highly composite, but wouldn't 6 be a good intermediate value? 24? 60 for the top end? No good reason. As far as I know, there haven't been any studies on the best values to choose for E. For clarity, let's write mD as x, so that for a Suyama power E, the exponent (x^E - d^E) is thrown into the mix when either x-d or x+d is prime in [B1...B2], (and only once if both are prime). This works because (provide E is even) x^E - d^E = (x-d)*(x+d)*C where C is a sum of higher order terms. The benefit of prime-pairing arises when E=2. The cost of higher E is AFAICS linear in multiplications. The benefit of higher E comes from any additional factors thrown into the mix by C. This benefit is greatest if C has factors slightly B2 For E=4, C = (x^2 + d^2) For E=6, C = (x^4 + x^2d^2 + d^4) = (x^2 + xd + d^2)*(x^2 - xd + d^2) For E=8, C = (x^2 + d^2)*(x^4 + d^4) I can't think of any reason why either of the two algebraic factors of C when E is 6 should be any better or worse than the single irreducible factor when E=4. And there are two of them. This suggests to me that E=6 should be about twice as effective as E=4 in providing additional factors, at about twice the cost (over and above the 'cost' of E=2). If this is correct, then it will always be worth going to E=6, whenever it is worth going to E=4, (provided there is sufficient memory to do so). Turning to E=8 it is tempting to make a similar argument, that (x^4 + d^4) should be about as good as (x^4 + x^2d^2 + d^4). If so then E=8 would be three times as good as E=4 at about three times the cost. However this ignores the fact that (x^4 + d^4) is irreducible, and therefore likely to have one very large factor, (which would not be much use to us) and fewer smaller ones. OTOH an irreducible factor of order four will be better than any single factor of order two. I therefore (tentatively) conclude that E=8 will be better than twice as good as E=4, but not three times as good. With E=10, the situation is even worse. C = (x^8 + x^6d^2 + x^4d^4 + x^2d^6 + d^8), which (I think) is irreducible. It is possible that E=10 may be less effective than E=8 or even E=6. Things improve with E=12. C = (x^2 + d^2)*(x^2 + xd + d^2)*(x^2 - xd + d^2)*(x^4 - x^2d^2 + d^4) i.e. we get every extra factor produced by E=4 and E=6 and then some more, suggesting that E=12 is between four and five times as effective as E=4 at about five times the cost. In 2 out of the 29 stage 2 factors I have found so far using E=4, k has not been smooth to B2. This suggests that increasing E from 4 to 12 could yield about 20% more factors. I've done a few tests with a modified and recompiled client, which suggests that it would worth it even if E=12 yielded as few as 10% more factors, though I need to investigate this further. I freely admit this analysis is simplistic and lacks rigour. Perhaps some of the number theorists on the list could improve upon it. Regards Daran _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 and non k-smooth factors
- Original Message - From: Alexander Kruppa [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Sent: Wednesday, September 25, 2002 12:03 AM Subject: Re: Mersenne: P-1 and non k-smooth factors This is the Brent-Suyama extension, aka Suyama's powers. In short, if you choose a Suyama's power E, a factor f will be found if the largest factor of f-1 divides some (mD)^E - d^E, where D is an integer chosen according to available memory, m and d are integers so that B1 mD-d = B2, 1 = d D and mD-d is prime. [...] ...the choice of D and E depends on the implementation. Prime95 chooses D so that phi(D)+E+4 (phi() is Euler's totient function) residues fit into memory, and chooses E like this: if (D = 180) E = 2; else if (D = 420) E = 4; else if (D = 2310) E = 12; else if (D = 6930) E = 30; else E = 48; (see ecm.c, choose_pminus1_plan() ) I understand why it chooses the values of D that it does, but why these values of E? I understand why E must be even, and that higher powers ought to be highly composite, but wouldn't 6 be a good intermediate value? 24? 60 for the top end? Alex Daran _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 and non k-smooth factors
At 06:05 PM 11/27/2002 +, Daran wrote: if (D = 180) E = 2; else if (D = 420) E = 4; else if (D = 2310) E = 12; else if (D = 6930) E = 30; else E = 48; I understand why it chooses the values of D that it does, but why these values of E? I understand why E must be even, and that higher powers ought to be highly composite, but wouldn't 6 be a good intermediate value? 24? 60 for the top end? No good reason. As far as I know, there haven't been any studies on the best values to choose for E. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 and non k-smooth factors
- Original Message - From: Alexander Kruppa [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Sent: Wednesday, September 25, 2002 1:03 AM Subject: Re: Mersenne: P-1 and non k-smooth factors This is the Brent-Suyama extension, aka Suyama's powers. In short, if you choose a Suyama's power E, a factor f will be found if the largest factor of f-1 divides some (mD)^E - d^E, where D is an integer chosen according to available memory, m and d are integers so that B1 mD-d = B2, 1 = d D and mD-d is prime. Right. And (mD)^E - d^E has mD-d as a factor, which yields all the usual stage 2 factors, while the cofactor ((mD)^E - d^e) / (mD-d) possibly introduces new ones. Thanks to everyone for their replies. Alex Daran _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 limits
At 12:27 AM 7/11/2002 +0100, Daran wrote: P-1 factoring with 459MB available memory, the program chose the following limits for these two exponants. 7786567B1=4, B2=64 7714127B1=4, B2=65 Why did the smaller exponant get the higher B2 limit? The short answer is I don't know. I invite someone to figure it out. Look for the last routine in commonc.c called guess_pminus1_bounds. First off, when dealing with P-1 success vs. cost analysis, the difference between 64 and 65 is negligible. Possible reasons for your case: 1) The code uses inexact interpolation and numerical integration to compute Dickman's function. 2) The GCD cost for the larger exponent is higher. This should be more than offset by the cost of the extra 72440 doublechecking LL iterations. 3) There are more trial factors with the smaller exponent in a given range because factors are 1 mod 2p. The costing routine sums up the chances of finding 65 bit, 66 bit, 67 bit, etc. factors. This should be offset by the higher exponent having a better chance of finding a smooth factor (found factors are 2kp+1 where k is smooth - larger p means smaller k which means a higher chance of success). Of course, the other possibility is a nasty bug in prime95. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1 limits
Prime95 version 22.3.1 P-1 factoring with 459MB available memory, the program chose the following limits for these two exponants. 7786567B1=4, B2=64 7714127B1=4, B2=65 Why did the smaller exponant get the higher B2 limit? Regards Daran G. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 Puzzle
- Original Message - From: Brian J. Beesley [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED]; [EMAIL PROTECTED]; Anurag Garg [EMAIL PROTECTED] Sent: Tuesday, June 11, 2002 8:23 PM Subject: Re: Mersenne: P-1 Puzzle On Tuesday 11 June 2002 06:13, Daran wrote: [... snip ... interesting but non-contentious] Very noticable is the proportion of exponents - in all three ranges - which are not getting a stage two effort at all. 26 out the 85 exponents between 795 and 796000, 24 out of 54 between 1550 and 15505000, 35 out of 57 between 33219000 and 33223000. I do not believe that large numbers of P4 systems are being shipped with just 8MB of RAM! This is true. However the philosophy of the project, correctly in my view, is that the software should not cause noticeable deterioration in the performance of a system when it is being run in the background to normal work. I agree. My remarks were intended to make the case for spinning P-1 off into a separate work type, (yeah, I know, it's difficult to change the server code), and to encourage other readers of this list to consider focussing on P-1 work. [...] The default has to be safe;... Again, I agree. While there will be some people who have made a deliberate decision not to allocate extra memory, in many cases people will simply have accepted the default, which means that some machines which could allocate more memory to stage 2 without adversely affecting the user won't be configured to do this. However that same tendency to accept defaults puts GIMPS programmers under an obligation to set those defaults conservatively. ...IMO the current default memory allowance of 8MB is entirely reasonable, even though it causes P-1 to run stage 1 only for any realistic assignment, and even though _new_ systems are usually delivered with at least 256 MB RAM. Against that is the observation that the basic memory footprint has barely changed in the over three years I've been with the project, while typical system memory has increased by a factor of four or more. A default set to 10% of available memory would allow a 256MB system to perform a modest stage 2 on low assignments in the test range, and on DC assignments, while still using proportionately less memory than three years ago. The effect of this could be further mitigated if the memory dialog included radio buttons to limit further the memory usage to 'minimum' (default), with other options being 'reasonable' and 'desireable', (as described in the helpfile) as well as 'maximum', and 'Do not run'. Thus the default would be to run a minimal stage 2 provided it could be done in 10% of system memory or less. I would consider this to be reasonable and conservative. Running P-1 on a 10 million digit exponent requires in excess of 64 MB memory to be allocated in order to run stage 2 at all. That's a lot to ask as a default! It is. OTOH if the box has 1GB installed, then it's not so much. Regards Brian Beesley Daran _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 Puzzle
- Original Message - From: Daran [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Monday, June 10, 2002 6:54 AM Subject: Re: Mersenne: P-1 Puzzle This appears to have happened to me at least once. I'll spend some time later today cross-referencing my WTD file against pminus1.txt to see if there are any more I don't need to do. Yesterday morning, shortly after 6 UTC, I reserved 42 DC exponents between 7.08M and 7.74M, i.e. all were recently expired exponents. Of these 27 had the P-1 bit set, all of which were P-1 complete, according to the pminus1.txt file dated June 9. Of the 15 with P-1 bit clear, one was in fact P-1 complete. I also reserved 32 test exponents between 12.7 and 13.8M. Of these, 27 had the P-1 bit set, 5 clear. None of these disagreed with pminus1.txt. Finally I checked 28 DC exponents which I had previously reserved, between 7.23M and 7.74M. All had the P-1 bit clear. (I routinely unreserve any exponents I get with P-1 bit set.) Of these, two were P-1 complete. From this, admittedly small and non-random sample, it appears that about one-third of *reassignments* of expired DC exponents have the P-1 bit clear, and that about one in fifteen of these are incorrect, leading to a redundant P-1 rerun by the new owner. I don't know what proportion of DC assignments are reassignments, but given that P-1 testing takes about 2% of the time to run a DC test, I would suggest that the impact of this problem upon the project as a whole is negligible. However, for anyone processing a lot of exponents, particularly those specialising in collecting reassignments, it might be worth putting together a script to identify these anomalies. With 512MB I probably have considerably more available memory than the average machine doing DCs now. That will be less true for machines doing DCs in the future, and probably not true at all for machines doing first time tests. Inspecting pminus1.txt confirms this. I would do a 796 DC exponent with B1=45000,B2=675000. Ignoring those which were obviously P-1ed as first-time test exponents, or where the tester has chosen to go well beyond the optimal limits, there are very few in this range which have been factored deeper than this, and many which have had stage 1 only or a very limited stage 2. I would do a 1550 test exponent with B1=19,B2=4227500, which is better than average, but not to the same extent as with the DC range. And I can P-1 many DC assignments in the time I'd take to do a single test assignment. I'd do a 10M digit exponent with B1=375000,B2=8156250, still better than average, but there are quite a few that go much deeper. Very noticable is the proportion of exponents - in all three ranges - which are not getting a stage two effort at all. 26 out the 85 exponents between 795 and 796000, 24 out of 54 between 1550 and 15505000, 35 out of 57 between 33219000 and 33223000. I do not believe that large numbers of P4 systems are being shipped with just 8MB of RAM! Regards Daran _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 Puzzle
On Sunday 09 June 2002 08:22, Daran wrote: I'm currently concentrating exclusively on P-1 work. The primenet server doesn't support this as a dedicated work type, so my procedure is to reserve some DC exponants, imediately unreserve any which have the P-1 bit already set, P-1 test the rest, then unreserve them without doing any LL testing. One problem I have discovered is that the server doesn't always 'recognise' that a P-1 result has been returned. It can take several days before my individual account report removes the * indicating that factoring work is necessary. In these cases I hold on to the exponant until the result is recognised in order to stop the subsequent 'owner' from doing a redundant P-1 check. In other cases, the P-1 result is recognised imediately. Though I'm not looking for P-1 specifically, I have seen something similar on a large number of occasions. My current assignment report - the DC part of which follows - contains a number of examples. 6493831 D 64 3.3 33.8 93.8 07-Jun-02 07:25 06-Jun-02 06:02 cabbage 0 v18 6530189 D 64 2.3 27.8 64.8 08-Jun-02 06:02 07-Jun-02 06:02 nessus-b 266 v19/v20 6672569 D 64 31.3 13.8 73.8 14-May-02 07:43 09-May-02 06:05 cabbage 0 v18 6881321 D 64 6.3 23.8 63.8 06-Jun-02 06:06 03-Jun-02 06:06 nessus-j 332 v19/v20 6972001 D* 64 0.3 14.7 60.7 09-Jun-02 04:02 caterpillar 654 v19/v20 7009609 D 63 394908824.3 9.8 64.8 07-Jun-02 06:04 16-May-02 06:06 nessus-m 266 v19/v20 7068857 D 63 588757825.3 0.8 60.8 06-Jun-02 06:06 15-May-02 06:05 nessus-j 332 v19/v20 7076669 D* 64 561798830.3 3.8 63.8 07-Jun-02 06:02 10-May-02 06:04 nessus-b 266 v19/v20 7099163 D 63 269335914.3 11.8 65.8 09-Jun-02 06:26 26-May-02 06:43 T4070 366 v19/v20 7908091 D 64 308019117.7 15.4 60.4 08-Jun-02 21:12 22-May-02 19:17 broccoli 400 v19/v20 7937717 D 64 235929510.5 7.6 60.6 09-Jun-02 02:04 30-May-02 00:30 caterpillar 654 v19/v20 7938407 D 64 131072010.3 12.3 60.3 08-Jun-02 20:29 30-May-02 04:16 vision.artb 495 v19/v20 7940447 D 64 9.8 16.8 65.8 09-Jun-02 06:24 30-May-02 17:39 Simon1 1002 v19/v20 7951049 D 64 65536 7.5 10.7 60.7 09-Jun-02 04:31 02-Jun-02 00:40 rhubarb 697 v19/v20 6972001 and 7076669 are starred although the fact bits column seems to indicate that both trial factoring to 2^63 and P-1 have been run. This is _definitely_ true for P-1 on 7076669, the fact is recorded on my system in both results.txt prime.log. So far as 6972001 is concerned, the database (dated 2nd June) indicates P-1 has been run to a reasonable depth but trial factoring has only been done through 2^62. My system definitely won't have done any more trial factoring yet, let alone reported anything, since that system is set up with v22 defaults i.e. defer factoring on new assignments until they reach the head of the queue. 7009609, 7068857 7099163 are not starred although the fact bits column is one short. The nofactor Pminus1 databases (dated 2nd July) give these all trial factored through 2^62 Pminus1 checked to B1=35000, B2=297500 (or higher). The P-1 limits seem sensible for DC assignments, but shouldn't these have been trial factored through 2^63 like most of the other exponents in this range? Currently, I have nine exponants 'warehoused' whose P-1 results have been returned but not recognised, the oldest was done on May 14, which is rather longer than I would expect. There's no question that the server has correctly recieved the result, because it is contained in a recent version of the pminus1.zip file downloaded this morning along with another four exponants 'warehoused' from May 20. Three more, whose results were returned on June 3 have not yet been recorded in this file. There is an entry in the file for the last of the nine, returned on June 5, but the limits are much smaller than the test I did. The most likely explanation is this is a previous owner's P-1 result which wasn't recognised before the exponant was given to me. I wonder what happens if you're working like Daran and someone returns a P-1 result independently (either working outside PrimeNet assignments, or perhaps letting an assigned exponent expire but then reporting results); if PrimeNet gets two P-1 results for the same exponent, which does it keep? This is not trivial; e.g. if you get no factors, B1=10, B2=100 and no factors, B1=20, B2=20 there might still be a factor which would be found if you ran with B1=20, B2=100. Also, if the database says that P-1 stage 1 only has been run (probably due to memory constraints on the system it ran on), at what point is it worthwhile running P-1 for the possible
Re: Mersenne: P-1 Puzzle
At 13:18 09/06/02 +, Brian Beesley wrote: 6972001 and 7076669 are starred although the fact bits column seems to indicate that both trial factoring to 2^63 and P-1 have been run. This is _definitely_ true for P-1 on 7076669, the fact is recorded on my system in both results.txt prime.log. So far as 6972001 is concerned, the database (dated 2nd June) indicates P-1 has been run to a reasonable depth but trial factoring has only been done through 2^62. My system definitely won't have done any more trial factoring yet, let alone reported anything, since that system is set up with v22 defaults i.e. defer factoring on new assignments until they reach the head of the queue. 7009609, 7068857 7099163 are not starred although the fact bits column is one short. The nofactor Pminus1 databases (dated 2nd July) give these all trial factored through 2^62 Pminus1 checked to B1=35000, B2=297500 (or higher). The P-1 limits seem sensible for DC assignments, but shouldn't these have been trial factored through 2^63 like most of the other exponents in this range? Regarding the star, I've noticed that if an exponent doesn't need any factoring when you check it out, the star pretty much always stays there throughout the entire test. If an exponent does need factoring, the star usually disappears after you finish it ( Daran's observations being a counterexample ). However, I have noticed situations where there are discrepancies with the factoring bit depths. Specifically: 7063451 D 63 This one has P-1 factoring done ( which I did ), but is only factored to 2^62 ( instead of 2^63 ). The nofactor.cmp file on the GIMPS status page agrees with this. However, my worktodo.ini says DoubleCheck=7063451,63,1, which possibly has prevented me from doing trial factoring that I would have otherwise done. Also when I checked out these exponents they had P-1 done, but needed trial factoring to 2^63: 6518503 D* 63 -- DoubleCheck=6518503,62,1 6528541 D* 63 -- DoubleCheck=6528541,62,1 I did the trial factoring on one machine with Factor=6518503,62, and put them on another machine with DoubleCheck=6518503,63,1. When I finished the trial factoring, the star went away, but the factored depth did not update. I decided to release 6518503 back to the server, and someone else checked it out, and it still looks like 6518503 D* 63, so I fear they may repeat the factoring I did. Was this caused by finishing the factoring with a Factor= line instead of a DoubleCheck= line? Nick Glover [EMAIL PROTECTED] Computer Science, Clemson University It's good to be open-minded, but not so open that your brains fall out. - Jacob Needleman _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 Puzzle
- Original Message - From: Brian J. Beesley [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Sunday, June 09, 2002 2:18 PM Subject: Re: Mersenne: P-1 Puzzle 6972001 and 7076669 are starred although the fact bits column seems to indicate that both trial factoring to 2^63 and P-1 have been run. This is _definitely_ true for P-1 on 7076669, the fact is recorded on my system in both results.txt prime.log. It also should be recorded in the worktodo.ini file for that exponent. Now if you were to unreserve that exponent, then contact the server sufficiently late in the day so that it is immediately reassigned back to you (rather than giving you a smaller one), then check the WTD file, then you'll find that the P-1 bit will have been unset. (This is how I discovered the problem in the first place.) There is a small risk of losing the assignment, if someone checks it out seconds after you unreserve it. So far as 6972001 is concerned, the database (dated 2nd June) indicates P-1 has been run to a reasonable depth but trial factoring has only been done through 2^62. My system definitely won't have done any more trial factoring yet, let alone reported anything, since that system is set up with v22 defaults i.e. defer factoring on new assignments until they reach the head of the queue. I'll bet its worktodo.ini entry also has the P-1 bit unset, meaning that you will do a redundant P-1 unless you manually fix it. What does it give for the factored bits? 62, or 63? 7009609, 7068857 7099163 are not starred although the fact bits column is one short. The nofactor Pminus1 databases (dated 2nd July) give these all trial factored through 2^62 Pminus1 checked to B1=35000, B2=297500 (or higher). The P-1 limits seem sensible for DC assignments, but shouldn't these have been trial factored through 2^63 like most of the other exponents in this range? Again, what does your WTD file say? [...] I wonder what happens if you're working like Daran and someone returns a P-1 result independently (either working outside PrimeNet assignments, or perhaps letting an assigned exponent expire but then reporting results); Or if someone is working like me who hasn't identified the problem. If they unreserve an exponent whose P-1 hasn't been recognised by the server, then the next owner will do another one, with possibly different limits. This appears to have happened to me at least once. I'll spend some time later today cross-referencing my WTD file against pminus1.txt to see if there are any more I don't need to do. This is not trivial; e.g. if you get no factors, B1=10, B2=100 and no factors, B1=20, B2=20 there might still be a factor which would be found if you ran with B1=20, B2=100. Also, if the database says that P-1 stage 1 only has been run (probably due to memory constraints on the system it ran on), at what point is it worthwhile running P-1 for the possible benefit of finding a factor in stage 2? That question generalises. If the database shows that a shallow P-1 has been run, at what point is it worth running a deeper one, and with what limits? Suppose the a priori optimal bounds for an exponent are, for example B1=4,B2=60, but it turns out that only stage 1 has been run to 4. Assuming that it's worth re-running the P-1 at all, it might be better to drop the B1 limit - to 35000, say, and increase the B2 limit. This would reduce the factor-space overlap with the first test. What's missing in all this is any kind of quantitative analysis. In any case, as long as there are exponents which haven't had a P-1 at all, I prefer to stick to them. [...] Daran, my advice would be to concentrate on exponents above the current DC assignment range which have already been LL tested but not P-1 checked, or on exponents above the current LL assignment range which have been trial factored but not P-1 checked, according to the official database (updated weekly - you will need the pminus1, nofactor hrf3 database files, plus the decomp utility to unscramble nofactor). I have these files, but following your advice would undermine my rational for doing this. With 512MB I probably have considerably more available memory than the average machine doing DCs now. That will be less true for machines doing DCs in the future, and probably not true at all for machines doing first time tests. I can work around the problem while staying within the current DC range. It's just an irritation. Regards Brian Beesley Daran _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: [Fwd: Mersenne: P-1 Stage 2]
- Original Message - From: Alexander Kruppa [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Sent: Saturday, December 15, 2001 2:05 AM Subject: Re: [Fwd: Mersenne: P-1 Stage 2] However, there's another generalisation that occurs to me that would be quite cheap to implement. The purpose of stage two is to catch those factors which are 'just out of reach' of stage 1. However another way a factor could be 'just out of reach' would be if the power of exactly one of the primes B1 was exactly 1 more than stage 1 would find. Stage 2 would find these factors *as well* if the algorithm were run for primes in [2,B2] instead of [B1,B2] Actually that really ought to be [2,~B2/B1] and then [B1,B2]. Another power on top of a prime in [~B2/B1,B1] will take it above B2. Since B2 is typically only an order of magnitude greater than B1 this is not going to make a lot of difference. Has this been investigated? Good point. The implementation I described finds a factor f iff the factorization of ord(a) mod f has only primes and prime powers = B1 and at most one prime = B2. It would be more reasonable if it could have primes and prime powers = B1 and at most one prime _or prime power_ = B2. That prime power has, after all, a probability =1/B2 of dividing a random integer. This is a generalisation of the above. However, that is awful to implement. In stage 1, you exponentiate each prime p by floor(log_p(B1)). In stage 2, you'd have to include small primes p = sqrt(B2), exponentiated by floor(log_p(B2)) - floor(log_p(B1)). Except that for primes above ~B2/B1, this will be zero, so we could ignore them. [...] If you want to make really sure that all powers of primes B2 are included, you can modify stage 1 to do so, i.e. exponentiate each prime pB1 by floor(log_p(B2)). This won't take a lot of extra time and is *much* easier to implement. I agree. The question is, which algorithm gives us the greatest factors to work ratio? Alex Daran _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: [Fwd: Mersenne: P-1 Stage 2]
However, there's another generalisation that occurs to me that would be quite cheap to implement. The purpose of stage two is to catch those factors which are 'just out of reach' of stage 1. However another way a factor could be 'just out of reach' would be if the power of exactly one of the primes B1 was exactly 1 more than stage 1 would find. Stage 2 would find these factors *as well* if the algorithm were run for primes in [2,B2] instead of [B1,B2] Has this been investigated? Good point. The implementation I described finds a factor f iff the factorization of ord(a) mod f has only primes and prime powers = B1 and at most one prime = B2. It would be more reasonable if it could have primes and prime powers = B1 and at most one prime _or prime power_ = B2. That prime power has, after all, a probability =1/B2 of dividing a random integer. However, that is awful to implement. In stage 1, you exponentiate each prime p by floor(log_p(B1)). In stage 2, you'd have to include small primes p = sqrt(B2), exponentiated by floor(log_p(B2)) - floor(log_p(B1)). Actual implementations of the second stage (ex prime pairing) work more like this, the example in my previous post was simplified: Choose D a multiple of small primes, i.e. multiple of 2310 or 210 or 30 (as memory allows), D sqrt(B2-B1) Store x^D store the phi(D) different values of x^n, gcd(n,D)=1, in xn[] p = smallest prime B1 compute x^(mD), so that p in [mD, (m+1)D] accu = 1 for each prime p = B2 accu *= x^(mD) - xn[n], so that mD-n = p p = next prime if p mD then x^mD *= x^D, to go from x^mD to x^(m+1)D gcd(accu, N) We don't store all the x^mD, but compute them as we need them, to save memory. This means we have to process primes in ascending order. If we wanted to include powers of small primes, we'd have to do an extra pass. Since p^(floor(log_p(B2)) - floor(log_p(B1))) is B1, for B1 B2/B1, we can't sort it into a list with our regular stage 2 primes. We'd have to make a list of powers of small primes, sort it and process it separately with the algorithm above. But: We make D a multiple of small primes so that we have to store fewer values in xn (if d|D and d|n, then d|D-n so D-n is not prime.) If we restrict ourselves to (large) primes in stage 2, we can save a lot of memory in xn[], but it'll mean we can't generate powers of those small primes d that divide D, and whose multiples n we delibarately left out of xn[]. We'd have to do yet another pass for those really small primes, and set up a new xn[] for it, with no multiples of small primes left out. If you want to make really sure that all powers of primes B2 are included, you can modify stage 1 to do so, i.e. exponentiate each prime pB1 by floor(log_p(B2)). This won't take a lot of extra time and is *much* easier to implement. Alex _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 Stage 2
- Original Message - From: Alexander Kruppa [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Monday, December 10, 2001 12:16 AM Subject: Re: Mersenne: P-1 Stage 2 P-1 stage 1 computes x = a^E (mod N), where E is the product of all primes and prime powers = B1. Right. The math page says 3^(2*E*P) and neglects to mention the (mod N). It also doesn't make it clear that E is a product of prime *powers*, and not just a primordial. I didn't understand how that could work, but this makes rather more sense. So if we were using P-1 to factorise 1000 using B1=15 we would calculate E = 2^9 * 3^6 * 5^4 * 7^3 * 11^2 * 13^2 Or did you mean E = 2^3 * 3^2 * 5 * 7 * 11 * 13 ? [...] For each x^p_i we compute this way, we multiply this x^p_i-1 to an accumulator. (Mod N) ? This generalises surely. You could have a third bound B3, and allow one prime between B1 B2, and a second prime between B1 B3. And then a fourth bound B4 and so on. (I'm not suggesting that it would be useful to implement this.) Thanks for a full and thought-provoking reply. Alex Daran G. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 Stage 2
Daran wrote: - Original Message - From: Alexander Kruppa [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Monday, December 10, 2001 12:16 AM Subject: Re: Mersenne: P-1 Stage 2 P-1 stage 1 computes x = a^E (mod N), where E is the product of all primes and prime powers = B1. Right. The math page says 3^(2*E*P) and neglects to mention the (mod N). It also doesn't make it clear that E is a product of prime *powers*, and not just a primordial. I didn't understand how that could work, but this makes rather more sense. So if we were using P-1 to factorise 1000 using B1=15 we would calculate E = 2^9 * 3^6 * 5^4 * 7^3 * 11^2 * 13^2 Or did you mean E = 2^3 * 3^2 * 5 * 7 * 11 * 13 ? The programmer of the P-1 algorithm is free to choose, either way will find factors. But in practice one uses the second alternative for efficiency. A prime power p^n has a probability of 1/p^n of dividing a random integer, so we include all those primes and prime powers with a probability = 1/B1, that is all primes and prime powers p^n = B1. [...] For each x^p_i we compute this way, we multiply this x^p_i-1 to an accumulator. (Mod N) ? Yup. We only want the final gcd with N, so all arithmetic can be done (mod N). This generalises surely. You could have a third bound B3, and allow one prime between B1 B2, and a second prime between B1 B3. And then a fourth bound B4 and so on. (I'm not suggesting that it would be useful to implement this.) Actually, it wouldn't work well. If we wanted to allow two large primes in factor-1, one from [B1, B2] and one from [B1, B3], we have to include all _combinations_ of such primes, i.e. for all p_1 in [B1, B2] compute x^p_1 for all p_2 in [B1, B3] compute (x^p_1)^p_2 multiply that to accu gcd(accu, N) The inner loop would be iterated (pi(B2)-pi(B1))*(pi(B3)-pi(B1)) times, where pi(n) is the # of primes =n, and that would be a terribly large number. I haven't heard of a practical three-stage algorithm yet. Alex _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1 Stage 2
The math page http://www.mersenne.org/math.htm explains how to do a stage 1 P-1 test with given bound B1, but it omits the explanation of the enhansement that uses B2 in stage 2. Anyone care to explain how this is done? Cheers Daran G. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 Stage 2
Daran wrote:
The math page http://www.mersenne.org/math.htm explains how to do a stage 1
P-1 test with given bound B1, but it omits the explanation of the
enhansement that uses B2 in stage 2. Anyone care to explain
how this is done?
Cheers
Daran G.
P-1 stage 1 computes x = a^E (mod N), where E is the product of all
primes and prime powers = B1.
If stage 1 does not find a factor, gcd(x-1, N) = 1, we go to stage 2.
The idea behind a second stage for P-1, P+1 and ECM is that a random
number will usually have its biggest prime factor quite a bit larger
than the second biggest, so it is worthwhile to figure something out to
include a single big prime more quickly.
We can go from x^p_i to x^p_{i+1}, where p_i is the i-th prime, quickly
by multiplying by x^(p_{i-1} - p_i). The difference between consecutive
primes is relatively small, apparantly no bigger than (log(B2)^2),so we
have no problem precomputing x^n for even n to cover all the possible
differences of consecutive primes we're having in our stage 2.
For each x^p_i we compute this way, we multiply this x^p_i-1 to an
accumulator.
We find the factor f of N if there is a prime p within our stage 2
interval so that f-1 | E*p (more specifically, ord(a) mod f | E*p),
since then a^(E*p) - 1 == 0 (mod f), thus the accumulator == 0 (mod f)
and a final gcd will reveal f.
We get something like: (x is assumed intact from stage 1)
xn[j] = x^(2*j), 1 2*j max(p_{i+1} - p_i), p_{i+1} = B2
last_p = last prime done in stage 1
for B1 p = B2, p prime
x = x * xn[(p - last_p)/2]
accu *= x-1
last_p = p
print gcd(accu, N)
This needs two multiplies per prime in the stage 2 interval, as opposed
to about 20 squarings (for a prime around 2^20) if it had been included
in stage 1.
We can speed that up further. x^n - x^m = x^m (x^(n-m) - 1), thus we
can get the (x^p - 1) we want by a single subtraction if we can write p
as n-m. (The extra x^m factor on the right side does not hurt.)
For example, for D ~= sqrt(B2-B1) store values
xm[i] = x^i, 1 = i D
and
xD[i] = x^(i*D) , B1/D i B2/D+1
Since we have only odd p, we can make D even and store xm only for
odd i.
Now we can do
for B1 p = B2, p prime
accu *= (xD[i] - xm[j) where Di-j = p
print gcd(accu, N)
Thus we need only one multiply per prime in the stage 2 interval, aside
from the about 2*sqrt(B2-B1) multiplies in setting up the tables.
However, we need more storage for precomputed values.
It can be done even faster, by pairing up primes, which can reduce the
number of multiplies again by almost half.
The definitive source for info on these algorithms is Montgomery,
Speeding the Pollard and elliptic curve methods of factorization, Math.
Comp. Vol. 48, 1987, pp. 243-265.
There are other enhancements that are even faster but require much more
memory (and which I don't quite understand), try P. Montgomery R.
Silverman, An FFT extension to the P-1 factoring algorithm, Math. Comp.
Vol. 54, 1990, pp. 839-854, also available online at
ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz .
BTW, Prime95 uses the one-multiply variant with prime-pairing, plus
something stange called Suyama's powers (don't ask me), for both P-1
and ECM.
Alex
_
Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: p-1 records
Is this a bug in the reporting software? I don't have the tools to work it out exactly, but a 103-bit number should be slightly larger than 2^103, or Nope. A 103-bit number N should lie in the range 2^102 = N 2^103. Something really odd is going on. Perhaps this small example will make things clearer: N(dec) N(bin) bits 1 1 1 2 10 2 3 11 2 4 100 3 5 101 3 6 110 3 7 111 3 81000 4 91001 4 101010 4 111011 4 121100 4 131101 4 141110 4 15 4 16 1 5 ... Paul _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: p-1 records
Gordon Spence wrote: Currently my team report cleared list shows 338 double checks and 12 double checked factored including this monster 6630223 87 DF 195139088771490335223859559 07-Apr-01 07:58 trilog (In fact when it was checked in PrimeNet initially rejected it because it was longer than this sort of check was supposed to find! Has anyone found a factor bigger than 87 bits using Prime95?) 10750127 103 F 7866348588447235992766781311399 14-Jan-01 10:57 Arnor Aries 11781977 103 F 8765843379800293878049454631169 15-Dec-00 20:06 mmesserWork_NT 11926087 103 F 8167296501437056056688534765783 07-Jan-01 10:52 rsuntagKayak_XU 12348829 103 F 9722991869324431663702571958950 22-Feb-01 07:48 SCUM C7375CE26 12423109 103 F 9668741834447195893278167681393 01-Mar-01 14:36 CamLewis work-syn-1 12469069 103 F 7539700408276934619634505308431 09-Mar-01 14:17 chbarr2Domain01 these are the first 6 I found. YotN, Henk _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: p-1 records
At 10:28 PM 12/4/2001 +0100, Henk Stokhorst wrote: (as part of a listing of factors found by himself) 12348829 103 F 9722991869324431663702571958950 22-Feb-01 07:48 SCUM C7375CE26 Is this a bug in the reporting software? I don't have the tools to work it out exactly, but a 103-bit number should be slightly larger than 2^103, or 10141204801825835211973625643008. the factor 9722991869324431663702571958950 is one digit too short, and thus appears to be truncated. The fact that it is even, and there is a relative shortage of Mrsenne numbers wandering about with even factors (or, for that matter, factors of five) would seem to me to confirm that. However, if it were truncated it couldn't have the beginning digit 9 - then it'd have 106 bits, unless my mental math is off. Something really odd is going on. Nathan _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: p-1 records
At 05:40 PM 12/4/2001 -0500, Nathan Russell wrote: 12348829 103 F 9722991869324431663702571958950 22-Feb-01 07:48 Is this a bug in the reporting software? Something really odd is going on. Yes. The structure used to pass back factors found only supports factors up to 32 digits. The server misreports the bit-length for very large factors. You may notice that when you finish an assignment two messages are sent to the server. One is the aforementioned C structure. The other is a text message (the same text as is written to results.txt). Fortunately, I use the text messages to update my databases which has no such 32 digit limitation. The largest factor found by P-1 factoring of large exponents is 35 digits: 1318781363113922700063643342764849026462401 _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1
You caught me, it was a PrimeNet assigned 33 million exponent which is a _10_ million digit Mersenne - what's a zero between friends? :) I am in so much trouble. For the first two weeks (during factoring) my completion date moved day for day. Now that I've started LL, the completion date is moving at 8 days per day! I thought the completion date logic was improved. There is a guy I know running for 73 days at 866 mhz and his completion date is 1168 days. I thought he must not be running 24/7 or running more than work item or doing something he shouldn't. I was prepared to wait for 190 days, but 16 days later I'm at 211. I don't think I'm going to be happy with 360 days let alone something along the line of 1168! Carleton - Original Message - From: Ken Kriesel [EMAIL PROTECTED] To: CARLETON GARRISON [EMAIL PROTECTED] Sent: Saturday, July 28, 2001 12:10 PM Subject: Re: Mersenne: P-1 At 01:58 AM 7/26/2001 -0400, you wrote: It has just taken me a week, each!, on a cutting edge laptop to do trial and P-1 factoring on a 100 million digit Mersenne. What code are you using for the above? Prime95's current limit is 2^79,300,000, or 23,871,678 decimal digits. Or did you type an extra zero? Ken _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1
On a 1200 TBird it tooks 196 days to LL 33309379. Hope that will show you : it's all right :) Christian You caught me, it was a PrimeNet assigned 33 million exponent which is a _10_ million digit Mersenne - what's a zero between friends? :) I am in so much trouble. For the first two weeks (during factoring) my completion date moved day for day. Now that I've started LL, the completion date is moving at 8 days per day! I thought the completion date logic was improved. There is a guy I know running for 73 days at 866 mhz and his completion date is 1168 days. I thought he must not be running 24/7 or running more than work item or doing something he shouldn't. I was prepared to wait for 190 days, but 16 days later I'm at 211. I don't think I'm going to be happy with 360 days let alone something along the line of 1168! Carleton _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1
P.L., Crunching on supercomputers, pioneering number theory, and having colleagues like Richard Brent (who squarely fits the bill of people who want Mersenne factors - not just knowing their primality) must be a blast! It is my gut reaction, that incredibly amazing CPU advances like those we've witnessed over the past 20 years, are the answer to all modern day computational dilemmas - factoring today's most wanted composites to be no exception. Your statement has made me look deeper. The difference between factoring 2^211 and 2^311 seems trivial, but using trial factoring I understand this difference equates to a billion-fold (2^30) increase in computational resource. At that pace, CPU advancements haven't kept up! The below mentioned algorithms truely, amazing, impress me. It has just taken me a week, each!, on a cutting edge laptop to do trial and P-1 factoring on a 100 million digit Mersenne. I know we do this factoring to potentially shorten the primality test, but I also thought it was this project's desire to either provide the least possible divisor, or to say none exists to a given lower boundary. That is, if we have by-product work beyond simple primality (no factors under 20 digits), then let's verify it and be a source for the next project. In my lifetime: man walked on the moon (and sent probes out of the solar system); Fermat's 'big' theorem was solved; the human genome was mapped. I look at expert's short-sightedness; RSA-100 was considered safe for a lifetime. I look at distributed computing efforts, SETI with 3 million participants, and understand it is in its infancy. I expect computer architecture will allow human comparable AI in my lifetime. But will all this focus increase today's computer factoring baseline by up to 2^466 (trial factoring multiple, what would the multiple be including today's algorithms?) without algorithmic advancement? If I weren't 40... I just read an article where someone said it he could see a billion people, running machines with a million CPUS, each CPU running a million times faster than today's - in ten years. All that, adds up to 2^75. You're a smart man, and you have grounded my feet awhile. What say I check-in again in 15 years. Carleton - Original Message - From: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Wednesday, July 25, 2001 7:05 PM Subject: Re: Mersenne: P-1 From: CARLETON GARRISON [EMAIL PROTECTED] I honestly thought that the long term goal (maybe not by this panel but for others) was to factor all these numbers and that we were setting/recording a lower boundary for that effort. Carleton Garrison It will be a _long_ time before we are completely factoring those values of 2^n +- 1 which are now being subject to LL testing. In the 1983 Cunningham edition, (2^211 - 1)/15173 was the first incomplete 2^n +- 1 factorization. In the 1988 edition it was (2^311 - 1)/5344847. Now, in 2001, the exponent has risen to 641. This threshold exponent advanced 20 per year between 1983 and 1988, due primarily to the MPQS and ECM algorithms. Since 1988, it has risen about 25 per year, due primarily to the Number Field Sieve. Unless there are major algorithmic advances, don't expect to pass 2^2000 - 1 in our lifetimes. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1
George, I'll see if I can work out a solution with Scott. A minimum solution would have the server return whether or not the exponent has already had P-1 factoring done. A better solution would include giving CPU credit for P-1 factoring and making it a separate work type. Right now I am running PrimtNT as a service. To see what stage I'm in, I've been stop/starting the service in order to get that info written to the 'results.txt' file. NTSETUP 'manual communication', and 'status' simply give me a 'prime.log' completion date. If I've missed something please lead me in the correct direction; if not, is this something possible for the next release? BTW, like I mentioned in an earlier post, I've been running through stages 1 and 2 for the past 12 days at say 90% capacity - 'status' has now has me finishing exactly 12 days later than it originally stated. Do completion date computations include factoring? Should I be worried? Thanks, Carleton _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1
On 23 Jul 2001, at 19:13, CARLETON GARRISON wrote: The name of the game is validate - by duplication. You cannot make a case without duplicating the result. This is to safeguard against the many gremlins that can occur - faulty overclocked CPUs, etc. But the only thing that goes wrong if a factor is missed is that a LL test gets run unneccessarily. It simply isn't worth rerunning all the factoring on the offchance that a small number of runs will glitch miss a factor. If the error rate of LL tests is about 1% then P-1, being much shorter, should be less than 0.1%. Trial factoring doesn't use the FPU much, so the processor will probably run much cooler errors may be even less likely than that. The point is that _even if factoring is omitted altogether_ LL DC will still eliminate a composite number. The purpose of doing factoring is to _save time_ by eliminating LL testing for those numbers where finding a factor is cheap enough to be cost effective. If someone finds a factor, someone ofer a PrimeNet can do a single division case and confirm the result. The server already does that automatically! The time required to _check_ a factor is miniscule. Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1
I honestly thought that the long term goal (maybe not by this panel but for others) was to factor all these numbers and that we were setting/recording a lower boundary for that effort. Carleton Garrison - Original Message - From: Brian J. Beesley [EMAIL PROTECTED] To: CARLETON GARRISON [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Sent: Wednesday, July 25, 2001 3:32 PM Subject: Re: Mersenne: P-1 On 23 Jul 2001, at 19:13, CARLETON GARRISON wrote: The name of the game is validate - by duplication. You cannot make a case without duplicating the result. This is to safeguard against the many gremlins that can occur - faulty overclocked CPUs, etc. But the only thing that goes wrong if a factor is missed is that a LL test gets run unneccessarily. It simply isn't worth rerunning all the factoring on the offchance that a small number of runs will glitch miss a factor. If the error rate of LL tests is about 1% then P-1, being much shorter, should be less than 0.1%. Trial factoring doesn't use the FPU much, so the processor will probably run much cooler errors may be even less likely than that. The point is that _even if factoring is omitted altogether_ LL DC will still eliminate a composite number. The purpose of doing factoring is to _save time_ by eliminating LL testing for those numbers where finding a factor is cheap enough to be cost effective. If someone finds a factor, someone ofer a PrimeNet can do a single division case and confirm the result. The server already does that automatically! The time required to _check_ a factor is miniscule. Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1
From: CARLETON GARRISON [EMAIL PROTECTED] I honestly thought that the long term goal (maybe not by this panel but for others) was to factor all these numbers and that we were setting/recording a lower boundary for that effort. Carleton Garrison It will be a _long_ time before we are completely factoring those values of 2^n +- 1 which are now being subject to LL testing. In the 1983 Cunningham edition, (2^211 - 1)/15173 was the first incomplete 2^n +- 1 factorization. In the 1988 edition it was (2^311 - 1)/5344847. Now, in 2001, the exponent has risen to 641. This threshold exponent advanced 20 per year between 1983 and 1988, due primarily to the MPQS and ECM algorithms. Since 1988, it has risen about 25 per year, due primarily to the Number Field Sieve. Unless there are major algorithmic advances, don't expect to pass 2^2000 - 1 in our lifetimes. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1
I honestly thought that the long term goal (maybe not by this panel but for others) was to factor all these numbers and that we were setting/recording a lower boundary for that effort. The main purpose is to find the Biggest Known Prime. Since that keeps changing, it's hard to say if we ever had a long term goal. In the 1983 Cunningham edition, (2^211 - 1)/15173 was the first incomplete 2^n +- 1 factorization. In the 1988 edition it was (2^311 - 1)/5344847. Now, in 2001, the exponent has risen to 641. This threshold exponent advanced 20 per year between 1983 and 1988, due primarily to the MPQS and ECM algorithms. Since 1988, it has risen about 25 per year, due primarily to the Number Field Sieve. Unless there are major algorithmic advances, don't expect to pass 2^2000 - 1 in our lifetimes. And don't forget, there are still mersenne numbers known to be composite with NO Known Factors (ooh, a mystery). Last I looked, the lowest exponent was 727. That's mighty low. Bob Farrington
Re: Mersenne: P-1
Hi, At 06:35 AM 7/24/2001 +0100, Daran wrote: As far as I can tell, both first time and DC LLs do P-1 factoring, but not trial factoring. (I suspect they will trial factor first if the exponant has not already been trial factored far enough, but I don't recall encountering this.) Both will do trial factoring if necessary. It is pretty rare that a DC needs more trial factoring. if the historical error rate for P-1s is the same as for LLs, (which is a reasonable assumption, given that they use the same FFT code*), then the probability of a second P-1 (using the same bounds) finding a factor that a first misses will be about 1% of this, i.e 0.02-0.05%, and only a single DC would be saved. Clearly not economical. You are correct. Since P-1 factoring was introduced over a year ago, I'm sure there have been quite a few needless P-1 runs. This happens primarily on triple-checks and first-time tests that were abandoned after the P-1 run completed. On the plus side, double-checking has still not reached the point where first-time checking was when P-1 factoring was released. Saying all that doesn't mean we couldn't break out work into more work unit types, it would just mean we'd also have to have a factoring DC work unit type if it was to be removed from the LL runs. I'll see if I can work out a solution with Scott. A minimum solution would have the server return whether or not the exponent has already had P-1 factoring done. A better solution would include giving CPU credit for P-1 factoring and making it a separate work type. I'll keep y'all posted. Best regards, George _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1
-Original Message- From: George Woltman [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED]; [EMAIL PROTECTED] [EMAIL PROTECTED] Date: 24 July 2001 21:17 Subject: Re: Mersenne: P-1 I'll see if I can work out a solution with Scott. A minimum solution would have the server return whether or not the exponent has already had P-1 factoring done. Better, perhaps (but more work to implement) would be to have the server return the B1 and B2 values used. The client could compare these to the values it would use if it were going to do this, based upon its available memory, and caculate whether a rerun would be economical. A better solution would include giving CPU credit for P-1 factoring and making it a separate work type. That might be a little complicated, since a machine which has high memory availability only at night might be better off getting two different types of work to do. I'll keep y'all posted. Best regards, George Daran G. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1
-Original Message- From: CARLETON GARRISON [EMAIL PROTECTED] To: Daran [EMAIL PROTECTED]; [EMAIL PROTECTED] [EMAIL PROTECTED] Date: 24 July 2001 00:18 Subject: Re: Mersenne: P-1 Daran, Again I'm not the most qualified person to reply but... The name of the game is validate - by duplication. You cannot make a case without duplicating the result. This is to safeguard against the many gremlins that can occur - faulty overclocked CPUs, etc. If someone finds a factor, someone ofer a PrimeNet can do a single division case and confirm the result. Yes. Verifying a factor is trivial. If not, then it is my understanding a first time LL will also do factoring. As far as I can tell, both first time and DC LLs do P-1 factoring, but not trial factoring. (I suspect they will trial factor first if the exponant has not already been trial factored far enough, but I don't recall encountering this.) However, it is likely that most of the exponants within the current DC range were first time LL checked before P-1 factoring was introduced. It is possible that once exponants are reached that were P-1 checked the first time round, they might not be checked again. Whether the first time comes back prime or composite, then PrimeNet knows that two factorings confirm no factors to a certain boundary - say 2^60. P-1 factoring uses boundaries in a different way, i.e searches a different space (that of smooth factors) from trial factoring. It's a question of probabilities. If P-1 factoring takes - say - 2% of the time to do an LL, and a success eliminates the need for first time /and/ double check LLs, then it's worth doing one if it has a sucess rate of more than 1%. For the P-1 tests I've done, the estimates for the probability of success ranged from 2-5%, depending upon how much memory I allowed it. (I've not done enough to confirm the accuracy of these estimates, but I've been told they're good). However, if the historical error rate for P-1s is the same as for LLs, (which is a reasonable assumption, given that they use the same FFT code*), then the probability of a second P-1 (using the same bounds) finding a factor that a first misses will be about 1% of this, i.e 0.02-0.05%, and only a single DC would be saved. Clearly not economical. [...] Saying all that doesn't mean we couldn't break out work into more work unit types, it would just mean we'd also have to have a factoring DC work unit type if it was to be removed from the LL runs. No, for the reason given above. The question boils down to whether enough people would like to do factoring DCs. It boils down to whether people with lots of memory (which is likely to be the newer faster machines) would be willing to do some P-1 factoring on it's own, and whether the gains would be worth the programming effort. This computer is a Duron running at 943MHz - hardly cutting edge speed - with 512MB RAM, which is ample for stage 2 P-1s. There must be many out there - particularly those doing DCs - which don't have enough RAM, or are running older clients. I'd be happy to do nothing but P-1s on these exponants that would otherwise never be tested in this way. Carleton Daran *A counterargument is that P-1 can use huge amounts of ram - hundreds of megabytes - and so might encounter memory errors that LLs don't. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1
I assume that p-1 factorisation is only done once, i.e., it is only done prior to a DC if it wasn't done at the time of the first-time test. Isn't there a case for splitting off p-1 into an entirely separate work unit? That way machines with insufficient memory either to run stage 2 at all, or to do so with a good chance of success, could be given pretested exponants for first-time/DC LLs Regards Daran G. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1 factoring only
L.S., I would enjoy it if it would be possible to have a prime95 version with a P-1 factoring assignments only option. My pc starts to crunch (literally, really, it starts to peep intermittantly like as if it needs lubricant) if I switch to LL testing. It would save time for the people prefering LL tests, just like the regular factoring only option does now. YotN, Henk _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 Credit
Hi Eric, Eric Hahn [EMAIL PROTECTED] wrote: Terry S. Arnold wrote: Does anyone have any skinny on when we will start getting credit for 1. doing P-1 testing? 2. finding a factor during P-1 testing? AFAIK, from what George has said, credit will eventually be given after BOTH v21 comes out, and the Scott has time to do some modifications to the PrimeNet server... Time Frame? ...??... Changes to support this are being designed. Mostly we needed to first get the next-generation Entropia network deployed to support v21 and other applications. This has been happening for a while now, so we will be resuming a focus on GIMPS soon. Regards, scott kurowski Entropia, Inc. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
Re: Mersenne: P-1 Credit
Hi Eric, Eric Hahn [EMAIL PROTECTED] wrote: Terry S. Arnold wrote: Does anyone have any skinny on when we will start getting credit for 1. doing P-1 testing? 2. finding a factor during P-1 testing? AFAIK, from what George has said, credit will eventually be given after BOTH v21 comes out, and the Scott has time to do some modifications to the PrimeNet server... Time Frame? ...??... Changes to support this are being designed. Mostly we needed to first get the next-generation Entropia network deployed to support v21 and other applications. This has been happening for a while now, so we will be resuming a focus on GIMPS soon. Regards, scott kurowski Entropia, Inc. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
Mersenne: P-1 Credit
Does anyone have any skinny on when we will start getting credit for 1. doing P-1 testing? 2. finding a factor during P-1 testing? Terry Terry S. Arnold 2975 B Street San Diego, CA 92102 USA [EMAIL PROTECTED] (619) 235-8181 (voice) (619) 235-0016 (fax) _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
Re: Mersenne: P-1 Credit
I've found 2 factors so far during P-1 testing and received 0.001 years (about 8 or 9 hours) credit for each. Not much consolation as it 'cost' upwards of 100 P90 hours each to find them, but it beats getting no credit for spending the same amount of time not finding any. Steve "binarydigits" Harris [EMAIL PROTECTED] -Original Message- From: Terry S. Arnold [EMAIL PROTECTED] To: [EMAIL PROTECTED] [EMAIL PROTECTED] Date: Thursday, September 07, 2000 1:46 AM Subject: Mersenne: P-1 Credit Does anyone have any skinny on when we will start getting credit for 1. doing P-1 testing? 2. finding a factor during P-1 testing? Terry Terry S. Arnold 2975 B Street San Diego, CA 92102 USA [EMAIL PROTECTED] (619) 235-8181 (voice) (619) 235-0016 (fax) _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
Re: Mersenne: P-1 Credit
Terry S. Arnold wrote: Does anyone have any skinny on when we will start getting credit for 1. doing P-1 testing? 2. finding a factor during P-1 testing? AFAIK, from what George has said, credit will eventually be given after BOTH v21 comes out, and the Scott has time to do some modifications to the PrimeNet server... Time Frame? ...??... Eric _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
Re: Mersenne: P-1 Credit
On 7 Sep 00, at 9:27, Steve wrote: I've found 2 factors so far during P-1 testing and received 0.001 years (about 8 or 9 hours) credit for each. Not much consolation as it 'cost' upwards of 100 P90 hours each to find them, but it beats getting no credit for spending the same amount of time not finding any. You always did get a small amount of credit for finding a factor (using trial factoring) compared with the effort that went in i.e. you got about 10x as much credit for running trial factoring unsuccessfully than for finding the "largest possible" factor in the range you were searching. I think PrimeNet credits factors found using P-1 as though they were found using trial factoring. However there is, as yet, no credit given for unsuccessful P-1 factoring effort. Don't lose sight of the fact that the purpose of running P-1 is to save time overall by avoiding running LL tests on those exponents which happen to be susceptible to P-1 factoring effort. Also, if you're running LL tests, you're certainly spending not more than 5% of your total effort running P-1 (significantly less than that if you're running double-checks), which is more than offset by the efficiency improvement between v18 and v19. Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
Mersenne: P-1 Database
Wanted: Brave Souls Re: P-1 Testing small exponents Besides exponents in the 200,000 - 500,000 range that are available, new ranges in the 751 - 100,000 are now available! Note, however, the smallest exponents have been tested to some degree already. As a result, they will take a good degree of time to test. Some save files are available though! If you're interested in P-1 testing some small exponents, let me know. For exponents under 30,000, bounds of at least B1 = 1E8 (100M) and B2 = 4E12 (4B) are requested... Eric _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
Mersenne: P-1 Testing
Hi, I was running a double check (assigned by Entropia) and found a factor, this is the second time that this has happened. I was just wondering about a few things 1. How often does this happen? 2. Does the original tester still "lose" the LL-credit they originally received. If they do then this doesn't seem fair to me, after all when they did the LL-test we didn't have the capability to find that factor. 3. Is it worth going back and performing a P-1 test on all Mersenne candidates with no known factor 4. Or is it better just to factor them deeper towards 2^72 Just out of interest I ran P-1 testing on another couple of numbers but no factor turned up. It only took about 3 hours for each test though... [Thu Jun 22 15:19:41 2000] UID: nitro/liberator, M3200543 completed P-1, B1=4, B2=60, WW1: 52E3BFCC [Thu Jun 22 19:00:18 2000] UID: nitro/liberator, M4056419 completed P-1, B1=45000, B2=652500, WW1: 691E386D regards G _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1 Database
Hello! All, I've updated the P-1 database again, adding two new lists. There are now four lists available: 1) The entire database (includes *all* tested exponents) 2) Tested prime exponents with no known factors 3) Tested prime exponents with at least one known factor 4) Tested composite exponents NOTE: Exponents with a factor found by P-1 are not listed if I don't know the bounds used for them. In addition, the exponent range between 200,000 - 500,000 is now available for reservations for further (deeper) testing... May the search be with you... Eric P-1 Database: http://mersenne.wackye.com http://www.mcn.org/2/ehahn/mersenne/ _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 Testing
I was running a double check (assigned by Entropia) and found a factor, this is the second time that this has happened. I was just wondering about a few things 1. How often does this happen? Depends on the bounds, which in turn depends on the exponent and your memory settings. The estimated probability of finding a factor is given at the beginning of the run is typically between 0.02 0.05. 2. Does the original tester still "lose" the LL-credit they originally received. If they do then this doesn't seem fair to me, after all when they did the LL-test we didn't have the capability to find that factor. Yes, in George's tables, but not according to PrimeNet. George's tables are recalculated each time from the list of exponents without known factors and take no account of factoring effort. PrimeNet accumulates all effort contributed "in good faith" by the user for both LL testing and factoring but does not include any credit for results submitted manually. 3. Is it worth going back and performing a P-1 test on all Mersenne candidates with no known factor If we simply want to eliminate exponents as candidates for Mersenne primes, once we have a pair of matching residuals there seems no point in searching for factors. If we are interested in actually finding factors then P-1 will find factors for _some_ exponents at a lower compuational cost than ECM should therefore be tried before ECM. But note that a large fraction of exponents will fail to succumb to either P-1 or ECM even with very heavy expenditure of effort. 4. Or is it better just to factor them deeper towards 2^72 Once we have trial factored to the Prime95 limit there seems lillte point in going further. For typical exponents, P-1 followed by ECM is likely (but not guaranteed) to find factors in this range with a higher frequncy in terms of factors found per CPU year. Just out of interest I ran P-1 testing on another couple of numbers but no factor turned up. It only took about 3 hours for each test though... [Thu Jun 22 15:19:41 2000] UID: nitro/liberator, M3200543 completed P-1, B1=4, B2=60, WW1: 52E3BFCC [Thu Jun 22 19:00:18 2000] UID: nitro/liberator, M4056419 completed P-1, B1=45000, B2=652500, WW1: 691E386D There are a large number of much smaller exponents which have had very little factoring effort other than trial factoring. See Eric Hahn's database of P-1 factoring effort ... http://www.mcn.org/2/ehahn/mersenne/mersenne.html Personally I think it's more interesting either to eliminate candidates before LL tests are run, or to try to find a factor for some of the smaller exponents for which no factors are known. Over the last 10 days or so I've tested 45 exponents with no known factors in the range 125,000 - 149,999 using P-1 with B1=1E6, B2=2.5E7 and have found two factors: P-1 found a factor in stage #2, B1=100, B2=2500. UID: beejaybee/Simon2, M143977 has a factor: 1660886238958203449182951 P-1 found a factor in stage #1, B1=100, B2=2500. UID: beejaybee/Simon2, M125933 has a factor: 1306727074606217680681 The runs take 1.5 - 2.0 hours each on a PIII-450. Although this success rate is a bit lower than I'd hoped for (just bad luck, I presume), it's a _lot_ better than trying to find factors of numbers in the Cunningham tables using ECM. Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1 Database is online!
Greetings all, The first iteration of the P-1 Factoring database is now online! It still has some work to be done, including (but not limited to) collecting, sorting through, and merging a lot of information for exponents 1,000,000, and separating the list into two (one for exponents without any known factors, one for exponents with at least one known factor). The address to find it at is: http://mersenne.wackye.com Eric _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Mersenne P-1 Database
Calling all P-1 factorers, I'm in the process of creating a database of P-1 factoring data for all Mersenne numbers. I have not found any other database for this information available on the 'net. There is some data kept by Will that's available, but it only goes to M(169,991)... I am collecting data for unfactored Mersennes presently, but this may expand -- depending on size of the database -- to include all Mersenne numbers not completely factored... If you're interested in seeing this database get started, and of making use of it, please send me your data. I need the exponent, B1 bound, and B2 bound. You can send the a results file if that's the easiest... Eric _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 memory vs vacation time
On 12 May 00, at 3:25, Shot wrote: 1) Where can I find some mathematical info on P-1 factoring (preferably everything, "for dummies")? The mathematical background to the modern factoring methods is distinctly non-trivial. However there are accessible explanations of the ideas behind the algorithms in several standard works. For a general introduction to factoring methods, try "Primes and Programming" by Peter Giblin (Cambridge University Press (1993), ISBN 0-521-40988-8). This book is fairly accessible and very reasonably priced, but the only reference to P-1 is to stage 1 only and is presented as an exercise. For a detailed explanation of the P-1 algorithm, refer to "Prime Numbers and Computer Methods for Factorization" by Hans Riesel (Birkhauser (1994), ISBN 0-8176-3743-5), which is expensive and by no means easy going. 2) When I use Prime95's Vacation or Holiday feature, does the program assume that the vacation time should be treated as nighttime for the purpose of P-1 factoring? Good point. My guess is that day/night setting takes no account of vacation time. However, is this really a problem? If running P-1 stage 2 and daytime begins, the program will suspend P-1 get on with something else, resuming the suspended P-1 job when daytime ends again. So the work gets finished up anyway, whether vacation time is in effect or not. BTW: George, I think many people (myself included) surf the web using 800x600 resolution - new Mersenne page's menu is a little to wide for that setting. Not a big issue, but a little annoying. Nowadays I tend to run in 1024x768 but with the browser window size set a bit smaller than that (though not as small as 800x600). I think 1024x768 is becoming pretty well the default resolution. However, I still believe that it's helpful to users to design web pages so they can be usefully viewed when displayed at 640x480 - even if this means preparing a differently formatted version of the page to suit users with low resolution displays. What about WAP mobiles with very small displays very limited graphics capability? What about an implementation of the LL Test for WAP mobiles? Would be a good way of making sure that the battery on the damn thing was always flat ;-) Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1 memory vs vacation time
I just downloaded Prime95 v20.4.1 and I have two questions: 1) Where can I find some mathematical info on P-1 factoring (preferably everything, "for dummies")? 2) When I use Prime95's Vacation or Holiday feature, does the program assume that the vacation time should be treated as nighttime for the purpose of P-1 factoring? I'd suggest additional option in the Vacation feature - a checkbox allowing Prime95 treat that free time as nighttime. My reasoning: I can see two possible ways - the abandoned computer is used by some other person (not connected to GIMPS) or the computer is unused. There have to be an option to let that other person use the computer as normal (thus treating the vacation time normally), but it would be a loss if the computer was totally unused and couldn't work with all of the nighttime memory. BTW: George, I think many people (myself included) surf the web using 800x600 resolution - new Mersenne page's menu is a little to wide for that setting. Not a big issue, but a little annoying. Cheers, -- Shot __ c"? [EMAIL PROTECTED] -- http://www.shot.prv.pl/ -- [EMAIL PROTECTED] `-' 12.05. na stronie nowe cytaty On a faucet in a Finnish restroom: To stop the drip, turn cock to right. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1 factoring of large exponent Mersenne numbers
A nasty thought just struck me. It's well known that factors of M(p) are of the form 2kp+1. It's also well known that factors found by the P-1 algorithm are of the form (product of powers of small primes) + 1 where "small" means less than an arbitrarily chosen limit B1. I omit stage 2 from consideration here. When applying P-1 to mersenne numbers, an additional 2*p ought to be included in the product, over and above all the powers of prime B1. Can anyone who knows for certain reassure me that this has been done for the prime95 V20 implementation? If it hasn't been done, my computation for the QA effort on M(42282367) with B1 = 100 has been a waste of a week's cpu. Paul _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1 factoring of large exponent Mersenne numbers
Paul Leyland writes: A nasty thought just struck me. It struck me in a different context some time ago; it might even be archived. When applying P-1 to mersenne numbers, an additional 2*p ought to be included in the product, over and above all the powers of prime B1. Can anyone who knows for certain reassure me that this has been done for the prime95 V20 implementation? I don't know about the prime95 V20 implementation per se, but George was aware of this quite some time ago, because he once told me that it is/was being done in Factor98, his older, stand-alone, P-1 factorer. While I'm here, I still accept P-1 factoring reservations and Factor98 and Factor95 save files for small exponent Mersennes. Will _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 factoring of large exponent Mersenne numbers
Hi Paul, At 09:40 AM 4/7/00 -0700, Paul Leyland wrote: When applying P-1 to mersenne numbers, an additional 2*p ought to be included in the product, over and above all the powers of prime B1. Can anyone who knows for certain reassure me that this has been done for the prime95 V20 implementation? This has been done. Your CPU-week has not been wasted. Regards, George _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1 factoring of large exponent Mersenne numbers
Paul Leyland wrote: It's well known that factors of M(p) are of the form 2kp+1. When applying P-1 to mersenne numbers, an additional 2*p ought to be included in the product, over and above all the powers of prime B1. Can anyone who knows for certain reassure me that this has been done for the prime95 V20 implementation? Yes, thats a property of P-1 that makes it very well-suited for factoring Mersennes. If the exponent is 10^x, you get x (+log_10(2) to be precise..) digits in the factor for free. This is used in all P-1 implementations that I am aware of. And here's another little extra: Factors are 1 or 7 (mod 8). Lets look at the 1 (mod 8) case: 2kp+1 = 1 (8) 2kp=0 (8) kp=0 (4) p is an odd prime = k is divisible by 4. Since the chance of the factor being 1 (8) seems to be 50%, 4 has a 50% chance of dividing k, 8 has a 25% chance, etc, so on average, theres yet another 2! So you best start by exponentiating your root by 4*p. Considering the 7 (mod 8) case (I dont know the proof off my head) it turns out that 3 has a 50% chance of dividing k, 5 has a 25% chance, 7 a 1/6 chance etc - so the k is a little more smooth then you'd expect a random number to be. I've been stuggling with modelling this into a formula that tells the chance of finding a factor of a given size with P-1, given certain bounds, but I got lost in cases that mutually exclude somewhere.. I have a little time now (exams done! :) and try some more. Somehow I feel that, since the 1 or 7 (8) property halves the number of factors to consider and P-1 seems to fully benefit from this property through "extra smoothness", the difficulty of the task of factoring k by P-1 should be reduced to factoring some number k/sqrt(2). That would be interesting to (dis-)prove. Ciao, Alex. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1 Factoring Walk-Through
TeamG: Am looking for a detailed, step-by-step walk-through of the P-1 factoring process. Any suggestions? Thanks And Regards, Stefanovic _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: p-1 and trial factoring
On 25 Feb 00, at 16:52, George Woltman wrote: However, it must be pointed out that at some point you are better off switching to ECM rather than expanding the P-1 bounds. I'm not sure what that point is. And, at some point, ECM itself gives way to CFRAC, SNFS, ... It's possible to find pathological examples of numbers which are easily factored by any one method but practically impervious to the others. The resources needed must be taken into account. ECM on Mersenne numbers with exponents well into the millions is going to be slow _very_ memory intensive. Let's get P-1 going first "argue" about implemeting ECM (for "trial factoring" of large exponents) later. Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: p-1 and trial factoring
BJB wrote: Yes - I think we need this database - with or without savefiles, it's a waste of effort to inadvertently duplicate work done before. Since P-1 is deterministic (like trial factoring, but unlike Pollard's rho or ECM) you should get the same result every if you use the same limits on the same exponent. If your implementations of rho and ECM are not deterministic, I suggest that you reimplement and/or get a working machine. Running rho with the same iterated function and starting value on the same exponent should give the same result every time. Running ecm with the same limits and the same curve on the same exponent should likewise give you the same result every time. Indeed, rerunning a new implementation with the same parameters as an old and (presumably) working implementation is one of the important ways of debugging and tuning the new version. The degree of freedom in choosing an elliptic curve for ECM is probably what you're hinting at. I'd suggest that a database of number of curves at run each B1/B2 limit is still useful. George keeps such a database for small exponents. Paul _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: p-1 and trial factoring
At 02:55 AM 2/27/2000 -0800, Paul Leyland [EMAIL PROTECTED] wrote: BJB wrote: Yes - I think we need this database - with or without savefiles, it's a waste of effort to inadvertently duplicate work done before. Since P-1 is deterministic (like trial factoring, but unlike Pollard's rho or ECM) you should get the same result every if you use the same limits on the same exponent. ... The degree of freedom in choosing an elliptic curve for ECM is probably what you're hinting at. I'd suggest that a database of number of curves at run each B1/B2 limit is still useful. George keeps such a database for small exponents. Paul It's my understanding that the choice of curve is randomized intentionally, and that the space of possible curves for each exponent is so large that it is more efficient to check random curves than to attempt to eliminate the very small chance of calculating the same curve more than once. This approach is used not only in GIMPS, but in George's implementation of Richard Crandall's program for searching for factors of Fermat primes. It is not necessary or advisable to run all possible curves. In fact, for F16, my runs produced in sequence, the following seed numbers, many of which found the factor 825753601: Attacking 2^65536 + 1 Selecting elliptic curve seed s = 1561883045: Selecting elliptic curve seed s = 630999867: Selecting elliptic curve seed s = 1921480920: Selecting elliptic curve seed s = 1664751173: Selecting elliptic curve seed s = 671100398: Selecting elliptic curve seed s = 2008555722: Selecting elliptic curve seed s = 112071784: Selecting elliptic curve seed s = 1157242418: Selecting elliptic curve seed s = 690847237: Selecting elliptic curve seed s = 823396944: Selecting elliptic curve seed s = 1372799571: Selecting elliptic curve seed s = 244007149: Selecting elliptic curve seed s = 2013596788: Selecting elliptic curve seed s = 1958155050: Selecting elliptic curve seed s = 441279715: Selecting elliptic curve seed s = 248788694: Selecting elliptic curve seed s = 831355685: Note that they go to at least 2 x 10^9. Ken _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: p-1 and trial factoring
Reto Keiser writes: A lot of factors of exponents between 1 and 100 were found using the new P-1 method. Is there a database which contains which exponent were tested using which B1 and maybe a database od the save files? The P-1 data is also collected by me, in the 'o:' lines of my programs' usual format (merfmt.txt). I also collect P-1 save files and try to keep track of who is running Factor98 and other (older) P-1 programs on which exponents. Note that this will likely not affect the new GIMPS and Primenet P-1 efforts, as I'm concentrating on small exponents where complete factorizations might be feasible; the new GIMPS P-1 efforts will be to find a first factor to avoid having to do LL tests. Will http://www.garlic.com/~wedgingt/mersenne.html mersfmt.txt _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: p-1 and trial factoring
On 25 Feb 00, at 15:23, Reto Keiser wrote: > Why can't we do first first the factorization up to n-2 bits (1/4) of the > trial factoring time, then start the P-1 factoring up to 1/3 of the B1 > value, after this, we can complete the trial factoring process and at the > end we complete the P-1 (using the save file od intermediate file). (the > parameters can be optimized) This sounds fairly sensible. However, this entails splitting the factoring part into fairly small sub-assignments, which may cause unneccessary complications with the server. Also, trial factoring and P-1 are quite different from the point of view of system requirements - trial factoring uses very little memory (in practice it runs almost entirely in the L1 cache) whereas P-1 is actually more of a memory hog than LL testing. So I suspect we want some bias towards early trial factoring rather than P-1. > until now >210 factors are found for 10megadiginumbers and more than 280 > exponents were factored up to 68 bits. Some (about 7) 67 digit factors > were found but none with 68 bits. This is likely to be a statistical anomoly. A sample size of 7 is a bit small to condemn the data as biased. > A lot of factors of exponents between 1 and 100 were found using > the new P-1 method. Is there a database which contains which exponent were > tested using which B1 and maybe a database od the save files? Yes - I think we need this database - with or without savefiles, it's a waste of effort to inadvertently duplicate work done before. Since P-1 is deterministic (like trial factoring, but unlike Pollard's rho or ECM) you should get the same result every if you use the same limits on the same exponent. If anyone has any data to contribute, I'd be willing to assemble publish the database. I also have adequate storage space on my anon ftp server for save files. Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: p-1 and trial factoring
Hi, At 03:23 PM 2/25/00 +0100, Reto Keiser wrote: parallel use of p-1 and trial factoring --- Why can't we do first first the factorization up to n-2 bits (1/4) of the trial factoring time, then start the P-1 factoring up to 1/3 of the B1 value, after this, we can complete the trial factoring process and at the end we complete the P-1 (using the save file od intermediate file). (the parameters can be optimized) I can't see any flaws in your reasoning, although it would be a bit unwieldy to implement. no 68 bit factors - until now 210 factors are found for 10megadiginumbers and more than 280 exponents were factored up to 68 bits. Some (about 7) 67 digit factors were found but none with 68 bits. My database has: 3321966173867482830512390441 3322338783006905661336745889 33221387123317319076102495049 33235409128314644111933147703 33238463131707491089550166169 33230671139408728702078150121 33224957193425473534465274127 That's 6 67-bit factors and 1 68-bit factor. Not the expected distribution, but nothing to be concerned about yet either. organization of p-1 factoring - A lot of factors of exponents between 1 and 100 were found using the new P-1 method. Is there a database which contains which exponent were tested using which B1 and maybe a database od the save files? All exponents from 2 to 11 were done with B1=1M and B2=40M Exponents from 11 to 60 (still in progress) were done with B1=100K and B2=4M. I still have the save files for exponents below 11. I think Alex has the save files for the larger exponents. However, it must be pointed out that at some point you are better off switching to ECM rather than expanding the P-1 bounds. I'm not sure what that point is. Regards, George _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1 factoring
I've been reading up on the P-1 method ... am I missing something? For a Mersenne number 2^n-1 with n prime we know that all the factors are of the form 2kn+1 for some integer k. So the factorization of p-1 _must_ include at least one factor equal to n. But the text leads me to believe that the P-1 method will only find factors when the factorization of P-1 contains no primes greater than the search limit. So, is using P-1 to factor Mersenne numbers with exponents in the millions but with B1 ~ 60,000 and B2 ~ 720,000 doomed to failure, or is my interpretation of the text completely wrong? I am (as an experiment) currently running P-1 on 2^11692589-1 using B1=6 and B2=72. I happen to know that 5318756664776903 ( = 2*k*11692589+1 for the prime k = 227441359) is a factor of this number, it will be interesting to see if P-1 finds it. Trial factoring will find this particular factor quite quickly! Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: P-1 factoring
I've been reading up on the P-1 method ... am I missing something? I don't think so, except perhaps for on possibility... For a Mersenne number 2^n-1 with n prime we know that all the factors are of the form 2kn+1 for some integer k. So the factorization of p-1 _must_ include at least one factor equal to n. But the text leads me to believe that the P-1 method will only find factors when the factorization of P-1 contains no primes greater than the search limit. So, is using P-1 to factor Mersenne numbers with exponents in the millions but with B1 ~ 60,000 and B2 ~ 720,000 doomed to failure, or is my interpretation of the text completely wrong? I believe, or at least sincerely hope, that the text is incomplete. Every implementation of P-1 of which I'm aware which is to be used to factor integers whose factors are known to be of the form kp-1 invariably throw in an additional k, as well as all the prime powers up to the B1 limit. (And likewise for P+1 and factors of the from kp+1). If the text is not incomplete, someone fix the program! Paul _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1
Hi folks Thanks for the "p-1 for dummies" e-mail. But as everyone on this list knows, any factor of a Mersenne number looks like 2*k*p+1 for N=2^p-1. Plugging this into the above equation gives q=2*k*p+1 q-1=2*k*p Doesn't this mean the lower bound on a "p-1" method search should be greater that the Mersenne exponent (the p in 2^p-1) to have the best chance of success? Then the "upper bound" of the "p-1" search can be resevered for cracking a big factor in the "k" of a Mersenne factor. This is a great point, one that I stopped a little way short on. Indeed the 'p-1' method constructs a large product of small primes, that you're hoping will be a multiple of q-1. Since we know q-1 is a multiple of 2p, it makes sense for us to start the p-1 method not at some base a, but at a^(2p). And as you point out, the upper bound then is in fact an upper bound on the factors of k. Provided we search as far as the factors of the unknown k, we will succeed. Starting at a^(2p) is relatively a small calculation, and saves us having to wait until the P-1 method includes p in the exponentiation (it's highly unlikely we would discover one before). Of course, its possible that even so, we may not find a factor, but it makes sense to include as much as we know about the factors at the very start of the method. Alternatively, we could specify p as a lower bound - something which is probably a good idea anyway, the calculation of a P-1 factoring is then comparable to a primality test. Going to a P-1 limit of 'p' certainly covers all factors with k=p, and many others besides. The factors that aren't covered are those with a prime or prime power factor of k above the P-1 limit. That can help you make a good guess as to how efficient your factoring attempt has been, of course, do not forget it is also possible to save the result of a P-1 attempt, return later, and "exponentiate some more" to increase the upper bound. Chris _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1
Well, see the topic. In other words, is it possible to get a quick "P-1 factoring for dummies" rundown? At which point is P-1 factoring worth the effort? Does it have any overlappign with ECM? How should the bounds be chosen for any given exponent, and will higher bounds always find any factors smaller bounds would have, or is there an advantage to running lower bounds? As I understand, every run with _same_ bounds would find the same factors? -Donwulff _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1
Hi there Well, see the topic. In other words, is it possible to get a quick "P-1 factoring for dummies" rundown? Sure, let's give it a try. Suppose we do some calculations modulo some number N. In effect we're actually doing all the calculations modulo all the prime factors of N, but of course we don't know what those prime factors are. But if we could find a calculation for which one of the prime factors would 'disappear', it would help us find that factor. Fermat's little theorem tells us that a^(p-1)=1 mod p, for all primes p. In fact, for each a there is a smallest number x0 such that a^x=1 mod p (the exponent of a modulo p). All we usually know about x is it divides p-1 The idea behind P-1 factoring is this, if we compute R=a^(some big very composite number)-1 mod N if our 'big composite number' is divisible by x, what is left will be divisible by some unknown factor p of N, and we could find p by examining gcd(R,N). Usually the big composite number is a product of powers of many small primes, so it has many factors and there is a good chance the unknown x (which is probably p-1) is a factor of it. At which point is P-1 factoring worth the effort? Probably as soon as your factoring attempts have exceeded what the machine is comfortable with. If you've reached 2^32, try P-1 for a little while. Trial-factoring will be slower if you carried on trying factors, also your probability of success with trial-factoring large numbers is extremely low. (p divides random N with probability 1/p). Of course P-1 may fail. You may have to go a very long way before the unknown x divides your big composite number - what if x itself has a large prime factor? P-1 would not find it until your P-1 loop reached that prime (in other words, your limit has to be bigger than the biggest prime factor of the unknown x). However there are factors that P-1 finds 'easily', and even a failed P-1 run can tell you a little more information about the number which might help if you try some more trial-factoring. (you know for instance that any factor must have some prime, or power of prime, factor of p-1 above the limit). Does it have any overlappign with ECM? The theory's very similar. Both algorithms attempt to find a point where one of the unknown prime factors 'disappears' from the calculation. However ECM has better odds. In P-1 attempts, the unknown x is fixed. You can't do anything about it, and even if you try using a different base a, you're very likely going to have a similar x with the same problems (a large factor). In ECM, choosing a different curve could give an equivalent 'x' value that varies a lot. One of those 'x' values may disappear quite quickly from the calculations. (but again, with large values it could be a long time before that happens). Of course the steps involved in ECM factoring are a little more complex than P-1... How should the bounds be chosen for any given exponent, and will higher bounds always find any factors smaller bounds would have, or is there an advantage to running lower bounds? As I understand, every run with _same_ bounds would find the same factors? In theory you can change the base and the bounds. Changing the base often has little or no effect, unless you are incredibly lucky (of course, 'obvious' bases related to the number are likely to be of little use - don't use base a=2 for Mersennes!). Changing the bounds though can make the difference between finding a factor, and not finding one. We may fail when we test a^(some small composite number)-1 but we may succeed when we test a^((some small composite number)*(some larger composite number))-1 By writing it like this you can also see that the larger bound succeeds if ever the smaller bound does. (the top line always divides the bottom line, so any factors of the top also appear at the bottom). Of course larger bounds take longer to calculate, and there is also a possibility that larger bounds would find "more than one" factor in one run. Ideally you check periodically through the calculation to see if you have already met a factor, but that might take time. The overriding "decision factor" is based purely on the time you're willing to spend. Factoring being explicitly harder than primality testing, you might be happy with, say, spending 10 times as long searching for a factor as you would on a proof the number was composite. So you might find "some very big composite number" 10 times the bit length of N was acceptable. 10 times the bit length of N is a good ballpark estimate for the bounds setting for the P-1 test to get that sort of time required. Of course if you were willing to spend 100, 1000 times as long, you could set the bounds higher... but in that case, bear in mind that the P-1 test is often unsuccessful. If you have that much time to spend, you might prefer to dedicate it to a more sophisticated algorithm. Just like trial-factoring, you have to increase the bounds *A LOT* before your chances of
Re: Mersenne: P-1
But as everyone on this list knows, any factor of a Mersenne number looks like 2*k*p+1 for N=2^p-1. Plugging this into the above equation gives q=2*k*p+1 q-1=2*k*p Correct. Doesn't this mean the lower bound on a "p-1" method search should be greater that the Mersenne exponent (the p in 2^p-1) to have the best chance of success? Then the "upper bound" of the "p-1" search can be resevered for cracking a big factor in the "k" of a Mersenne factor. No. Simply multiply the exponent on the base by p. This produces the desired result, without having to go to the extra effort of extending the bound that far. I probably should add a section on P-1 to the FAQ. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1 second stage
I've just finished trying to factor F24 using the P-1 method with a bound #1 of 1,000,000. No factor was found. Unfortunately, I do not have enough memory to run stage 2. So, is there a volunteer that would be willing to run stage 2 on their computer. It will take about 3 weeks. You need 256MB of memory. The program will use 100 MB of that for the full 3 weeks. How does the stage 2 of P-1 work? Why does it require more memory? How do you know how long it will take if you don't even know what speed of computer is being used? :) The only references that I've seen to it say that it involves random walks and the birthday paradox. Can anyone point me to any online resources? (Library is closed for a week in preparations for the start of a new semester) Thank you, Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1 factorers
Are there any programs available (preferably PC) for P-1 factoring that work with arbitary numbers rather than only specific types (such as the Mersenne programs)? Andrew Walker
RE: Mersenne: P-1 factorers
Hi, Are there any programs available (preferably PC) for P-1 factoring that work with arbitary numbers rather than only specific types (such as the Mersenne programs)? If you are familiar with compiling and linking C program, you can use Richard Crandall's large integer package which includes first stage implementations of p-1 and ECM. You can download it from his Perfectly Scientific web site at http://www.perfsci.com/ Don Leclair [EMAIL PROTECTED]
