Mersenne: Factoring hiccup?
An odd thing happened today. I have version 21.4.1 on my laptop (a PIII-1000, but only turned on a few hours a day so that LL tests would take months) doing trial factoring. I ahppened to see the following in the screen display tonight: [Feb 13 01:44] Factoring M21632497 to 2^67 is 14.43% complete. [Feb 13 01:45] Factoring M21632497 to 2^67 is 14.46% complete. [Feb 13 01:46] Factoring M21632497 to 2^67 is 14.49% complete. [Feb 13 01:47] Factoring M21632497 to 2^67 is 14.52% complete. [Feb 13 01:48] Factoring M21632497 to 2^67 is 14.55% complete. [Feb 13 01:49] Factoring M21632497 to 2^67 is 16.14% complete. Strange. Do we know if this is just a minor glitch in the GUI, or if the factoring algorithm actually misses factors? GRB _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring Top 100
AH yes... I recall when I was up there at about 120 on LL maybe better. (Bnow someplace around 240 not sure i'll need to go look after this msg. (B Even with 12 or so systems it still slips... the PC's , like me, are (Bgetting old!!! On the factor side (slow old PC ) they just keep chewing (Balong... I do enjoy the 2GHZ PC knocking out a double ck every 4 (Bdays... soon it will be into the 90x range. (B (By'all have a good day. (B (BMichael (B (BRussel Brooks wrote: (B Well I've recently reached my 2nd GIMPS goal of getting into the (B top 100 factoring. Last summer I made it to the top 1000 LL (B testers and then switched from double checks to factoring to (B make my mark there. (B (B Now what to try for? :-) (B (B Cheers... Russ (B (B DIGITAL FREEDOM! -- http://www.eff.org/ (B (B _ (B Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm (B Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers (B (B (B (B_ (BUnsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm (BMersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring Top 100
Well I've recently reached my 2nd GIMPS goal of getting into the (Btop 100 factoring. Last summer I made it to the top 1000 LL (Btesters and then switched from double checks to factoring to (Bmake my mark there. (B (BNow what to try for? :-) (B (BCheers... Russ (B (BDIGITAL FREEDOM! -- http://www.eff.org/ (B (B_ (BUnsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm (BMersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Factoring Top 100
Well, you could be goofy like me and try to get to the same # ranking in both the factoring and LL test stats. For a while I was #15 on both, but I think my factoring slipped to #16 and my LL moved to #14... Better add another factoring machine. :) The fun part is you don't even need to have a bunch of machines... Just shoot for being like #98 on both lists or something, adjust your work accordingly to get it just right. :) I suppose it's easier as you reach higher on the stats because we're more spread out there, but the jostling for the #15 position in the factoring table does seem pretty close, relatively speaking... Aaron -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]] On Behalf Of Russel Brooks Sent: Tuesday, January 21, 2003 4:07 PM To: [EMAIL PROTECTED] Subject: Mersenne: Factoring Top 100 Well I've recently reached my 2nd GIMPS goal of getting into the top 100 factoring. Last summer I made it to the top 1000 LL testers and then switched from double checks to factoring to make my mark there. Now what to try for? :-) Cheers... Russ _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring Top 100
At 12:07 AM 1/22/03 +, Russel Brooks wrote: Well I've recently reached my 2nd GIMPS goal of getting into the top 100 factoring. Last summer I made it to the top 1000 LL testers and then switched from double checks to factoring to make my mark there. Now what to try for? :-) Bah, top 100 factoring isn't that hard! :) I just checked my ranking and with only four computers I'm sitting at 140 and top 100 looks quite doable. You could make your mark by poaching the last remaining exponent under M38, assuming that Draco Malfoy doesn't beat you to it. :) _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring top 10
Hi, At 11:41 AM 2/12/2002 -0800, Aaron Blosser wrote: PS - I'm just thrilled because I found a factor of an exponent that beat my previous record... 101 bit factor. I'm too lazy to look through the cleared exponents list, so does anyone know what the largest factor is that has been found by GIMPS lately? The top 10 - 39 digits for the biggest! 1433462339 56379662829467477289264041716715663 1318781335 63113922700063643342764849026462401 1075012734 4777866348588447235992766781311399 1293216734 4314676575733979321708362055504719 1050634734 2529967840093210987185485731119337 1345961334 2004522251312746653413939484232703 1454281734 1001733277749555116882783777187313 1234882933 972299186932443166370257195895087 1437882733 749393632720558083108841526201431 1311127132 35439060242916356936579100907769 _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring bits
Hi, At 09:18 PM 2/12/2002 +0100, Achim Passauer wrote: And for all other readers all(?) factors with more than 99 bits which are part of the latest cleared exponents report: 14308961 103 F 9394020965332917865679071542783 There are two minor shortcoming in the prime95 to primenet protocol. It reports the first 32 digits of a found factor. Thus, the report will never display more than 103 bits as the length of the found factor. Also if P-1 finds a composite factor prime95 reports this as one gigantic factor rather than two smaller factors. Naturally, this is all cleared up when it is entered into the master database. Its just that the primenet server reports can be a little misleading. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring assignment ends early w/no factor
I have a machine that was close to finishing its first factoring assigment. It was 94.5% complete on the last (to 65 bits) pass. I estimate the remainder would take about 3 to 4 hours to complete. I started up a kids program for my son, he played with it for about 15 minutes and then exited. I was very surprised to note that the factoring assignment reported as complete with no factors found, and without the display going past 94.5% (each tick was about 0.08%). I've never noticed a factoring assignment end early without finding a factor before, but I haven't run very many. I don't know if this is normal or if the kids program (heavy on animated graphics and sound, like most kids program) caused a glitch in Prime95. It's an AMD K6-2 processor, and I do note that Prime95 way overestimates the amount of time it takes to do factoring assignments on it, but I don't think that should cause this oddity. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Re: MERSENNE: Factoring Failure?
Steve Harris wrote: -Original Message- From: [EMAIL PROTECTED] [EMAIL PROTECTED] To: [EMAIL PROTECTED] [EMAIL PROTECTED] Date: Tuesday, October 02, 2001 3:44 PM Subject: Re: FW: Mersenne: Re: Factoring Failure? snip Either way, GIMPS has never considered missing a factor as a big deal. It only means some wasted effort running a LL test that could have been avoided. True enough - though I'm concerned that the no factors below 2^N database may be seriously flawed, from the point of view of GIMPS it would seem to be a waste of time to go round redoing trial factoring just to fix this problem. Yes, from the point of view of GIMPS (that is, searching for Mersenne primes) it's not a huge deal... but there also exists an effort to fully factor the candidates that are not prime, and this throws a big problem into that project. Someone could be trial factoring an exponent from 2^59 to 2^65 and find a factor in that range after a smaller factor had been missed, and it will go into the database as the smallest factor when it actually is not. Might be decades before the smaller factor is discovered. Actually... IIRC... George noted once that the database of smallest KNOWN factors was just that... and did NOT necessarily mean that it contained the smallest factors of any given exponent... There was a bug in a previous version (v19??) which caused Prime95 to not continue trial-factoring to find a smaller factor after one had been found and it had been stopped (or went to sleep)... There was also the advent of P-1 factoring which does not necessarily find the smallest factor, but instead finds factors comprised of lots of small factors, and can therefore miss smaller factors which does not have lots of small factors... In this case... the database would not necessarily have the smallest factor for every exponent with a factor found... but instead the smallest KNOWN factor... which is not necessarily the smallest factor for that exponent... Eric _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring failure?
Yesterday I was assigned M7027303 to doublecheck. The number came with the claim that it had no factors less than 62 bits. But my P-1 factorization of the number found this 55-bit factor: [Sun Sep 30 13:53:26 2001] P-1 found a factor in stage #1, B1=35000, B2=463750. UID: dswanson/nosnawsd, M7027303 has a factor: 31090234297428433 I thought this was mighty peculiar, so I stuck Factor=7027303,0,0 into my worktodo file to force a complete refactorization of the number. Sure enough, about three minutes later out pops the result: [Sun Sep 30 15:06:10 2001] UID: dswanson/nosnawsd, M7027303 has a factor: 31090234297428433 Somebody wasted a lot of time doing a first-time LL test on this number. Does anybody have any idea how common factoring errors might be in the exponents not factored database, particularly since doublechecks are not commonly done on the factoring results? Dan _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring on a P4 - CORRECTION
--- Forwarded message follows --- From: Brian J. Beesley [EMAIL PROTECTED] To: [EMAIL PROTECTED] Date sent: Fri, 22 Jun 2001 18:46:43 - Subject:Re: Mersenne: Factoring on a P4 Copies to: [EMAIL PROTECTED] On 22 Jun 2001, at 13:12, [EMAIL PROTECTED] wrote: For some reason, I am at a loss to explain, a v21 P4 1.4 GHz factors significantely slower that a P3 v20 700MHz. Is there a reason, and solution, for this? Good question. AFAIK George has done nothing to the factoring code. You will see a big speed loss if you compare factoring under 2^64 with factoring over 2^64 on _any_ system - that's simply explained by triple- precision integer arithmetic being much slower than double-precision integer arithmetic. Intel's development for the P4 was very much geared towards making SSE2 work well. Unfortunately this left less room in the silicon for some of the ordinary integer stuff on which the factoring code (but not the LL testing code) in Prime95 depends. If memory serves me right, the 32 bit by 32 bit integer multiply instruction was badly hit by this. Consequently the factoring throughput of a P4 would be expected to be considerably less than that of a PIII running at the same clock speed. I would expect that a PIII-700 and a P4-1400 would probably run factoring at about the same speed. Earlier I wrote: For now, those who are lucky enough to have P4 systems are probably best advised to stick to LL testing (and trial factoring - which will not be affected by any inefficiency in the P4 integer instructions), leaving trial factoring to those with slower systems. Slip of the brain, I'm afraid. I meant LL testing (and P-1 factoring... Incidentally ECM ought to run pretty well on the P4, though there may be some more optimization to come for the very small run lengths typically used by 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: Factoring on a P4
For some reason, I am at a loss to explain, a v21 P4 1.4 GHz factors significantely slower that a P3 v20 700MHz. Is there a reason, and solution, for this? Bradford J. Brown - This message was sent using GSWeb Mail Services. http://www.gasou.edu/gsumail _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring on a P4
On 22 Jun 2001, at 13:12, [EMAIL PROTECTED] wrote: For some reason, I am at a loss to explain, a v21 P4 1.4 GHz factors significantely slower that a P3 v20 700MHz. Is there a reason, and solution, for this? Good question. AFAIK George has done nothing to the factoring code. You will see a big speed loss if you compare factoring under 2^64 with factoring over 2^64 on _any_ system - that's simply explained by triple- precision integer arithmetic being much slower than double-precision integer arithmetic. Intel's development for the P4 was very much geared towards making SSE2 work well. Unfortunately this left less room in the silicon for some of the ordinary integer stuff on which the factoring code (but not the LL testing code) in Prime95 depends. If memory serves me right, the 32 bit by 32 bit integer multiply instruction was badly hit by this. Consequently the factoring throughput of a P4 would be expected to be considerably less than that of a PIII running at the same clock speed. I would expect that a PIII-700 and a P4-1400 would probably run factoring at about the same speed. For now, those who are lucky enough to have P4 systems are probably best advised to stick to LL testing (and trial factoring - which will not be affected by any inefficiency in the P4 integer instructions), leaving trial factoring to those with slower systems. Conversely, if you need a system with optimal integer performance, you'd be much better advised to buy a system based on a fast Athlon processor than a system based on a Pentium 4. Athlons running integer code even run much cooler; the FPU turns itself off when it isn't needed, leading to a big drop in current consumption. BTW there was an unreasonable acceleration of trial factoring between the P5 architecture (Pentium Classic/MMX) and the P6 architecture (Pentium Pro / PII / PIII / Celeron / Xeon), so you can't simply assume that Intel doesn't care about integer performance! 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: Factoring on a P4
BTW there was an unreasonable acceleration of trial factoring between the P5 architecture (Pentium Classic/MMX) and the P6 architecture (Pentium Pro / PII / PIII / Celeron / Xeon), so you can't simply assume that Intel doesn't care about integer performance! But they clearly don't care about it on the P4: Command Ticks on P2/P3Ticks on P4 MOV 1 1 ADD/SUB 1 1 ADC/SBB 2 8 MUL 4 14-18 SHR/SHL 1 4 Michael. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring on a P4
Bradford J. Brown wrote: For some reason, I am at a loss to explain, a v21 P4 1.4 GHz factors significantely slower that a P3 v20 700MHz. Is there a reason, and solution, for this? Hmmm... Good question... AFAIK, the only change George has or is going to make in the factoring code since v19... is to change the Athlon over to use the P2/P3 code path... instead of the 486 code path... Doing such will allow Athlons to trial-factor 2.5-3x faster... There really isn't a whole lot more speed increase that can be gained from the factoring code as a whole, AFAIK... You will also notice a BIG speed decrease with trial-factoring on ANY machine as you move from factoring up to 2^62... to factoring up to 2^64... to factoring above 2^64... This is expected with the extra instructions necessary to handle the larger trial-factor sizes... Eric _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring M727 through M(M727) revisited
Hi all, I think I found a (although purely theoretical) way to find a factor of M(p) by factoring M(M(p)). Ok here goes: f is a prime factor of M(M(p)), 2^(M(p)) = 1 (mod f) so the order of 2 in Z/f*Z is !=1, divides M(p) but is not neccessarily equal to M(p). Lets call it c. Since the order of 2 also divides f-1, c|f-1. The problem with trial division of M(M(p)) is that you can't limit the candidate divisors to multiples of the factors of M(p) when you know these factors - so you'd have to resort to testing all primes as candidate divisors (or at least those where divisor-1 has a large prime factor). This is impractical for large c and therefore large f. The interesting case is when c != M(p), f != 1 (mod M(p)) and f = 2*k*c+1 for a small k. Then the P-1 method could recover that factor if the bound is =k or k is smooth and you do an extra exponentiation by M(p), i.e. f = GCD(3^(M(p)*E)-1,M(M(P))), E product of primes and prime powers =bound. The trick here is that P-1 finds the factor f if the exponent E is any multiple of f-1. You don't have to know c in order to exponentiate by it - knowing that c|M(p) suffices. GCD(M(p), f-1) will finally recover the factor of M(p). The only drawback is that M(M(727)), and indeed any M(M(P)) for yet unfactored M(p), is so gargantuan that doing arithmetic modulo it is completely out of the question. But the idea looks interesting on paper. Ciao, Alex. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring on elderly machines.
At 06:05 AM 3/4/01 -0800, Paul Leyland wrote: Three weeks ago, I wrote: The integer factoring people can always use more cycles, and even antique machines make valuable contributions in a reasonable time. For instance, I have small number of DECstations and a Sun SS2 on my home network all running the ECMNET client. These boxes are perhaps as powerful as a 486DX2-66. A few days ago my DECstation 5000/240 found a 32-digit factor of Cullen(831), that is 831*2^831+1, with the ECMNET client. Ok, so it's not a Mersenne number but the ECMNET server could just as easily be loaded with them. Owners of elderly machines should not despair just yet. Paul Speaking for myself, having completed over 260 factorings over 5 years, with no primes found, I say that elderly owners of machines should not despair just yet. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: factoring the higher exponents
On 15 Dec 00, at 10:39, Henk Stokhorst wrote: I spend the past months factoring the range 16.000.000 up to 17.000.000 form 2^52 up to 2^58. I reported the results once a week, which are included in the database. This week someone else started to work on this as well although up to 2^56. This work is therefor done twice. What is being done and can be done to avoid this? Well, if people would stick to PrimeNet assignments, this sort of thing wouldn't happen... At least the other "culprit" is bothering to report the results, and the duplicated effort isn't too much - only about one quarter of your investment. BTW would anyone who has run P-1 on exponents in the range 10 to 125000 (prime, with no known factors) without reporting the limits used please report them to me. I'm working through them with B1=1E6, B2=25E6 but seem not to be finding any factors - possibly someone has done them before? Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: factoring the higher exponents
L.S., I spend the past months factoring the range 16.000.000 up to 17.000.000 form 2^52 up to 2^58. I reported the results once a week, which are included in the database. This week someone else started to work on this as well although up to 2^56. This work is therefor done twice. What is being done and can be done to avoid this? YotN, Henk Stokhorst _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Factoring
We could let prime95 decide the next election grin. Give everybody a different prime number. Multiply the primes for candidate A together, likewise for B. And like in this election, unless we can completely factor the results, we wouldn't know who won, either. :) I note the smiley, but I also assume that we know the original primes as well, as it's built into the double voting detection mechanism. If after dividing through all allocated primes the residue is 1, we can conclude that at least one voter registered a protest by spoiling their ballot paper. Note that we also know who did *not* vote, if their prime doesn't appear in either product. A major problem with this protocol as I see it is that a third party can steal your vote by stealing your prime and using it first. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring
Paul Leyland wrote: We could let prime95 decide the next election grin. Give everybody a different prime number. Multiply the primes for candidate A together, likewise for B. And like in this election, unless we can completely factor the results, we wouldn't know who won, either. :) I note the smiley, but I also assume that we know the original primes as well, as it's built into the double voting detection mechanism. If after dividing through all allocated primes the residue is 1, we can conclude that at least one voter registered a protest by spoiling their ballot paper. Note that we also know who did *not* vote, if their prime doesn't appear in either product. A major problem with this protocol as I see it is that a third party can steal your vote by stealing your prime and using it first. These problems could be solved by storing the primes on a single, secured machine and then sending them to voters, eg, on a floppy through certified mail. Correct me if I'm wrong, but by using primes with, say, 150 decimal digits generated from strong random numbers, we'd be quite safe. The problem is for the government to factor the huge composite number for each candidate afterwards. Can someone give me a rough estimate of how long it would take a good supercomputer to check an arbitrary 100,000,000 digit number for several factors that are each a known 150 digit arbitrary prime? Nathan _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Factoring
The problem is for the government to factor the huge composite number for each candidate afterwards. Can someone give me a rough estimate of how long it would take a good supercomputer to check an arbitrary 100,000,000 digit number for several factors that are each a known 150 digit arbitrary prime? Not long at all, and you don't need a supercomputer. It's perfectly parallelizable. Use a room full of PCs and give them disjoint ranges of primes to test. A major problem, which no-one has yet commented on, is that the protocol as stated doesn't allow a secret vote. Only if no-one other than the voter knows who received which number, and the voter knows only his/her own, can it be secret. Patching up this hole is relatively straightforward and is left as an exercise for the reader ;-) Paul _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring
Hi folks, Off-topic I know, but... We could let prime95 decide the next election grin. Give everybody a different prime number. Multiply the primes for candidate A together, likewise for B. And like in this election, unless we can completely factor the results, we wouldn't know who won, either. :) _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring
Chris Nash proposed: We could let prime95 decide the next election grin. Give everybody a different prime number. Multiply the primes for candidate A together, likewise for B. And like in this election, unless we can completely factor the results, we wouldn't know who won, either. No need to factor during primery elections. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Factoring with ECM
From: Yann Forget [mailto:[EMAIL PROTECTED]] Could you explain this to me ? I can try. The text below is deliberately informal in style and far from mathematically rigorous. The mathematicians on the list will have to forgive me; those who want a more rigorous explanation should be able to find one with relative ease. I am factoring Fermat numbers with ECM. Is this relevant in this case ? It is relevant for all numbers, but only when ECM produces a composite factor. To be honest, your chance of finding even one unknown factor of a Fermat number with ECM is tiny, and your chances of finding two or more *on the same curve* are somewhere between nil and negligible. Paul Leyland said: As long as the coefficients of the curve and the starting point are recorded, we can re-run exactly the same computation, with the small primes curtailed as in the p-1 case, on the same curve and the number c. It's because my software doesn't normally output the curve and starting point used that the idea hadn't occurred to me. Ok, what's happening with ECM is that we are performing arithmetic not with ordinary integers but with points on an elliptic curve --- a polynomial of the form y^2 = ax^3+b. (Actually, we are calculating with integers, but in a complicated manner which corresponds to manipulating points on a polynomial). The "starting point" I mentioned is a point which lies on the curve and, with a few special exceptions, it doesn't matter too much which point is chosen. When the arithmetic is performed modulo a composite number, there are a finite number of points on the curve. Each different curve will, in general, have a different number of points. When the number of points on a particular curve is divisible *only* by primes less than the first stage limit B1, with perhaps at most one prime larger than B1 but smaller than the 2nd stage limit B2, ECM will find a corresponding factor. Usually this factor will be a prime, but occasionally it will be the product of two or more primes. Each of these primes corresponds to a different selection of small primes smaller than B1 and, usually, only one will correspond to the prime larger than B1 and smaller than B2. If you then repeat the calculation, using exactly the same curve and starting point but with a reduced set of primes B1 and/or omit the one B1, the factor which corresponds to the omitted primes *won't* be discovered, thereby revealing the other. Paul _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring Assignments: Are They Always First-Time?
Stefan Struiker writes: When a requested factoring assignment is listed with, say, 52 in an account log, does this mean it has been factored to 52 bits, but _without_ success? Yes, the number should have no factors less than 2^52. Or could a factor have already been found in some cases, but less than 52 bits long? Nope, unless the factor was not reported for some reason (bug, disk crash, etc.). My strategy in factoring 13.3 mill exponents and up, is to save L-L testing and DCing time by knocking some out early. Seem to be on a roll, too, with factors found 40% of the time, with a turnaround of 40 hours per. That's a very high rate of factors, I'd've thought, but that happens sometimes. In any case, Prime95 "knows" how much factoring work should be done for a particular Mersenne number before starting an LL test (first or double-check) on it and will do more factoring if the data it gets from Primenet (or other source) indicates the number has not been factored "enough". The predicated chances of finding a factor during trial and P-1 factoring is taken into account, along with how long the factoring takes to do and how long the two LL tests will take. So your phrase "knocking some out early" is exactly correct: if noone tries to factor a particular Mersenne number before it is given to a Prime95 that wants to run an LL test, that Prime95 will do some factoring first, usually before it even finishes the prior Mersenne number's LL test (to make sure it has "enough" work in worktodo.ini). Eric Hahn writes: If it's listed as 52 in the fact-bits column of the report, it means that it's been trial-factored thru 2^52 without any factors being found. Currently, all exponents thru Prime95's limit of 79.3M have been factored to at least 2^50... If a factor is found for an exponent, it's eliminated from further testing of any kind. Yup. Here's a short summary of my current data. For Mersenne numbers with prime exponent that have no LL test nor a factor, here are the smallest exponents trial factored only as far as the last column: M( 5178743 )U: 2^62 M( 8896813 )U: 2^61 M( 9993539 )U: 2^60 M( 10078559 )U: 2^55 M( 11300657 )U: 2^54 M( 11505331 )U: 2^53 M( 11521879 )U: 2^52 M( 20500019 )U: 2^51 M( 30100181 )U: 2^50 M( 79300037 )U: 2^45 M( 79306169 )U: 2^43 The exponents above 79.3 million have probably only been worked on by me, personally, since they're above Prime95's limit, but I'm still a bit surprised they haven't been factored further; trial factoring to the same depth is _easier_ for larger exponents, not harder. Jeff Woods writes: Isn't the factor itself verified? Yes, if only by me, as I noted in another thread in the last couple of weeks. Will http://www.garlic.com/~wedgingt/mersenne.html _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring
Thanks for the factor.exe citation. At 01:40 AM 6/16/00 -0700, Jim Howell wrote: [Wed 14 Jun 2000, Paul Leyland writes] Today I found this number 3756482676803749223044867243823 with ECM and B1=10,000. It has two factors, each of 16 digits, which could *not* have been found by trial division in any reasonable time. - I use a program called "factor.exe", which uses several factoring methods. It factors the above number within several seconds. (For this number, the factors are found with the P-1 method.) In case anyone is interested, the factors are 1483398061194277 and 2532349728015299. This program runs on Windows, and can be downloaded from Chris Caldwell's main page, at: http://www.utm.edu/research/primes Go down to section 4, (Software), and look for "factor.exe", described as a DOS program, but it actually runs in a Command Window on Windows 95 and later, and (probably) not under actual DOS. I find "factor.exe" quite useful for factoring small numbers (it will accept numbers up to about 130 digits). --Jim !DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" HTMLHEAD META content="text/html; charset=iso-8859-1" http-equiv=Content-Type META content="MSHTML 5.00.2314.1000" name=GENERATOR STYLE/STYLE /HEAD BODY bgColor=#ff DIVFONT face=Arial size=2[Wed 14 Jun 2000, Paul Leyland writes]/FONT/DIV DIVFONT face=Arial size=2BRToday I found this number 3756482676803749223044867243823 with ECM andBRB1=10,000.nbsp; It has two factors, each of 16 digits, which could *not* haveBRbeen found by trial division in any reasonable time./FONT/DIV DIVFONT face=Arial size=2/FONTnbsp;/DIV DIVFONT face=Arial size=2-/FONT/DIV DIVFONT face=Arial size=2/FONTnbsp;/DIV DIVFONT face=Arial size=2I use a program called "factor.exe", which uses several factoring methods.nbsp; It factors the above numbernbsp;within several seconds.nbsp; (For this number, the factors are found with the P-1 method.)nbsp; In case anyone is interested, the factors arenbsp; 1483398061194277 and 2532349728015299.BR/FONT/DIV DIVFONT face=Arial size=2This program runs on Windows, and can be downloaded from Chris Caldwell's main page, at:/FONT/DIV DIVFONT face=Arial size=2/FONTnbsp;/DIV DIVFONT face=Arial size=2A href="http://www.utm.edu/research/primes"http://www.utm.edu/research/prime s/A/FONT/DIV DIVFONT face=Arial size=2/FONTnbsp;/DIV DIVFONT face=Arial size=2Go down to section 4, (Software), and look for "factor.exe", described as a DOS program, but it actually runs in a Command Window on Windows 95 and later, and (probably) not under actual DOS.nbsp; I find "factor.exe" quite useful for factoring small numbers (it will accept numbers up to about 130 digits)./FONT/DIV DIVFONT face=Arial size=2--Jim/FONT/DIV DIVFONT face=Arial size=2nbsp;/DIV/FONT/BODY/HTML _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring Assignments: Are They Always First-Time?
At 01:00 PM 6/17/00 -0700, you wrote: being found. Currently, all exponents thru Prime95's limit of 79.3M have been factored to at least 2^50... If a factor is found for an exponent, it's eliminated from further testing of any kind. Isn't the factor itself verified? _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring Assignments: Are They Always First-Time?
From: Jeff Woods [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: Mersenne: Factoring Assignments: Are They Always "First-Time?" Date: Sat, 17 Jun 2000 17:14:00 -0400 At 01:00 PM 6/17/00 -0700, you wrote: (snip) If a factor is found for an exponent, it's eliminated from further testing of any kind. Isn't the factor itself verified? I would assume it is, however verifying a factor takes well under a P-90 second. Nathan Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring Assignments: Are They Always First-Time?
Jeff Woods wrote: being found. Currently, all exponents thru Prime95's limit of 79.3M have been factored to at least 2^50... If a factor is found for an exponent, it's eliminated from further testing of any kind. Isn't the factor itself verified? Yes, it is. However, at least in the case of Prime95, George has written the code such that the factor is validated before it's even displayed as a being a factor and written to the results file. If it's invalid, the code continues as if the "factor" was never found... Eric _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring
[Wed 14 Jun 2000, Paul Leyland writes] Today I found this number 3756482676803749223044867243823 with ECM andB1=10,000. It has two factors, each of 16 digits, which could *not* havebeen found by trial division in any reasonable time. - I use a program called "factor.exe", which uses several factoring methods. It factors the above numberwithin several seconds. (For this number, the factors are found with the P-1 method.) In case anyone is interested, the factors are 1483398061194277 and 2532349728015299. This program runs on Windows, and can be downloaded from Chris Caldwell's main page, at: http://www.utm.edu/research/primes Go down to section 4, (Software), and look for "factor.exe", described as a DOS program, but it actually runs in a Command Window on Windows 95 and later, and (probably) not under actual DOS. I find "factor.exe" quite useful for factoring small numbers (it will accept numbers up to about 130 digits). --Jim
Mersenne: Factoring with ECM
Hi, Could you explain this to me ? I am factoring Fermat numbers with ECM. Is this relevant in this case ? Thanks in advance, Yann Paul Leyland said: As long as the coefficients of the curve and the starting point are recorded, we can re-run exactly the same computation, with the small primes curtailed as in the p-1 case, on the same curve and the number c. It's because my software doesn't normally output the curve and starting point used that the idea hadn't occurred to me. Paul -- Ionix Services, les services réseaux d'aujourd'hui http://www.ionix-services.com/ Tel 04 38 12 38 90 Fax 04 38 12 38 94 _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: factoring
Brian Beesley (Mersenne Digest 715, 7. April) wrote: There are also factoring programs available in portable high-level-language source format, in particular look for Mfactor.c If it wasn't for the fact that factoring is so far ahead of LL testing, I'd probably switch my Alpha system to factoring - with its 64 bit integer registers and quad-issue pipeline, the architecture is much better suited to factoring than LL testing, and the performance is somewhat startling for factoring (up to 63 bits) even though the program is neither tuned to the hardware nor hand optimized. True, the generic-C component of Mfactor is not tuned to any particular hardware. But Peter Montgomery (author of Mfactor) has written assembly code supplements for two architectures (Alpha and MIPS) which support 64 x 64 == 128-bit integer multiply, and thus on those platforms the program is very speedy. On the MIPS and pre-21264 Alphas (which don't fully pipeline integer multiply) the single functional unit that does integer multiply is saturated and thus Mfactor may not perform as well on a cycle-by-cycle basis as one would hope for, but the performance should still be quite good. On the Alpha 21264 (which fully pipelines IMUL) Mfactor should really scream, but of course the 21264 is extremely good at the floating-point ops that dominate an Mlucas run, too. The Sparc, alas, has a very poor integer multiply capability and should be used for floating-point work (i.e. LL testing) only. I think the suggestion to have one machine (whether that be a PC running Prime95 or a MIPS or Alpha running Mfactor) do all the factoring needed to keep multiple non-PC machines well-fed with exponents is a good one, since otherwise, juggling factoring and LL work becomes a pain. Note that Mfactor (as currently configured) doesn't support putting multiple exponents into a to-do file, so the best way to trial factor lots of exponents is probably just to paste the one-line inputs needed for the exponents, one after another, into the same window - when the program finishes the current exponent, it'll read the next input line from the buffer. Of course, this doesn't permit one to log out, so is best done on a machine which one owns (then one can at least lock the display when one needs to leave.) Mfactor (source and precompiled binaries for MIPS/Irix and Alpha/Unix) is available at my ftp site: ftp://209.133.33.182/pub/mayer/README.html Happy hunting, -Ernst _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: factoring
snipped a lot Note that Mfactor (as currently configured) doesn't support putting multiple exponents into a to-do file, so the best way to trial factor lots of exponents is probably just to paste the one-line inputs needed for the exponents, one after another, into the same window - when the program finishes the current exponent, it'll read the next input line from the buffer. Of course, this doesn't permit one to log out, so is best done on a machine which one owns (then one can at least lock the display when one needs to leave.) We are talking (some flavour of) unix here aren't we? You could make an input file with the factors (As you must enter them, including any stuff you must enter before you enter the first factor) and then run mfactor in the background nohup mfactor input.file output.file then you can log out. Kind Regards, Martijn -- http://jkf.penguinpowered.com Linux distributies voor maar Fl 10 per CD, inclusief verzendkosten! _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring Depths
Dave Mullen wrote: I'd just like to get a clarification on some files I downloaded from the Entropia FTP. Re the file of exponents, and how far they have been trial factored. I extracted a range using the decomp program. Each exponent has a number by the side, but I am unclear to what this number refers. Is it a) The bitlength of the K value alone i.e. a bit length of 32 would indicate all K values 1 to (2^32) have been tested ? or b) The bitlength of 2 x K x Exp + 1 as computed ? Just to save me repeating previously done work. The answer is B. It the length of the actual factor being tested. Therefore, 1139,64 means that all potential factors thru 2^64 (18,446,744,073,709,551,615) have been tested (all ~10^12 of them). Eric _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring Depths
I'd just like to get a clarification on some files I downloaded from the Entropia FTP. Re the file of exponents, and how far they have been trial factored. I extracted a range using the decomp program. Each exponent has a number by the side, but I am unclear to what this number refers. Is it a) The bitlength of the K value alone i.e. a bit length of 32 would indicate all K values 1 to (2^32) have been tested ? or b) The bitlength of 2 x K x Exp + 1 as computed ? Just to save me repeating previously done work. Thanks Dave
Re: Mersenne: Factoring beyond ECM
LiDIA is a free package for long number arithmetic. It includes a demo-program for factoring numbers with trial factoring, ECM and MPQS successive. See here: http://www.informatik.tu-darmstadt.de/TI/LiDIA/Welcome.html regards Martin -Ursprüngliche Nachricht- Von: Foghorn Leghorn [EMAIL PROTECTED] An: [EMAIL PROTECTED] Gesendet: Samstag, 22. Januar 2000 23:24 Betreff: Mersenne: Factoring beyond ECM I'm interested in trying to factor composite numbers with 100 to 200 digits. ECM becomes impractical for numbers without any factors below 50 digits or so. I have heard of algorithms such as MPQS which are used to tackle larger numbers. Are there any (preferably free) implementations of this method (or another) that would be feasible to run on a home PC or Unix workstations? Foghorn Leghorn [EMAIL PROTECTED] _ 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
Mersenne: Factoring beyond ECM
I'm interested in trying to factor composite numbers with 100 to 200 digits. ECM becomes impractical for numbers without any factors below 50 digits or so. I have heard of algorithms such as MPQS which are used to tackle larger numbers. Are there any (preferably free) implementations of this method (or another) that would be feasible to run on a home PC or Unix workstations? Foghorn Leghorn [EMAIL PROTECTED] _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring beyond ECM
On Sat, 22 Jan 2000, Foghorn Leghorn wrote: I'm interested in trying to factor composite numbers with 100 to 200 digits. ECM becomes impractical for numbers without any factors below 50 digits or so. I have heard of algorithms such as MPQS which are used to tackle larger numbers. Are there any (preferably free) implementations of this method (or another) that would be feasible to run on a home PC or Unix workstations? MPQS is ok for numbers up to about 100 digits, at which time NFS takes over. Have a look at Conrad Curry's NFSNET, http://orca.st.usm.edu/~cwcurry/nfs/nfs.html Foghorn Leghorn [EMAIL PROTECTED] -- Henrik Olsen, Dawn Solutions I/S URL=http://www.iaeste.dk/~henrik/ Thomas Daggert to Lucifer: I have my soul, and I have my faith. What do you have... angel? The Prophecy _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring beyond ECM
On Sun, 23 Jan 2000 02:06:26 +0100 (CET), you wrote: MPQS is ok for numbers up to about 100 digits, at which time NFS takes over. Is there a good implementation of this available online? Have a look at Conrad Curry's NFSNET, http://orca.st.usm.edu/~cwcurry/nfs/nfs.html Foghorn Leghorn [EMAIL PROTECTED] _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring Mersenne
Hello! I was fiddling around with Mersenne factors the other day and came across an interesting result. I'm not sure if it is of any use, but I think if anyone can extend it just a little further, then it would cut down the numbers we would have to try to factor by a HUGE amount... Anyway, any mersenne's factor can be written as 2kp+1 So any persenne number 2^p - 1 (here on written as P) can be written as (2ap+1)(2bp+1) = P i.f.f. it is not a prime Now define x = p(a+b)+1, y=p(a-b) Then x+y=2ap+1, x-y=2bp+1 so P=(x-y)(x+y) x^2 - y^2 = P Now write n=a+b, m=a-b so x=pn+1 , y=pm Then (pn)^2 + 2pn + 1 + (pm)^2 = P taking this mod p^2 and rearranging a little 2pn = P-1 mod p^2 this means 2pn = (P-1) + pZ for some integer Z so (P-1) must have a factor of p, which we can cancel (we also know this directly). Call (P-1)/p = Q Then 2n = Q mod p n = Q/2 mod p which is well defined Therefore we can find the sun of the two factors mod p. I have tried (and failed so far) to get a similar relationship for y (or a or b) If we could get such a relationship for y, and we assumed we were looking for the smallest factor, then we could work out something about that factor (hopefully it's value mod p) which would cut down on factoring requirements. Any ideas? Chris Jefferson, Girton College, Cambridge, [EMAIL PROTECTED] Someone may have beaten me to Fermat's Last Theorem, but I've done Riemann's general equation. However it won't fit in my signature file... _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring 2^n+1 and 2^n-1
Hi, Ernst Mayer once mentioned to me that Prime95 needs twice the FFT size for 2^n+1 numbers (compared to 2^n+1 numbers). Does that mean that George is using the identity 2^(2n)-1 = (2^n+1)(2^n-1) ? I was wondering why ECM on 2^n+1 numbers took much longer than on 2^n-1 of the same size.. That would mean that I can do ECM on, for example, P773 and M773 at the same time by doing ECM on M1546, and it will take just as long as ECM on only P773, right? When I find a factor, I'll just have see which number it divides. Ciao, Alex. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring 2^n+1 and 2^n-1
On 3 Nov 99, at 13:53, Alex Kruppa wrote: Ernst Mayer once mentioned to me that Prime95 needs twice the FFT size for 2^n+1 numbers (compared to 2^n+1 numbers). Does that mean that George is using the identity 2^(2n)-1 = (2^n+1)(2^n-1) ? I was wondering why ECM on 2^n+1 numbers took much longer than on 2^n-1 of the same size.. It used to be the case that 2^n+1 was only using power-of-two FFT run lengths. v19 has addressed this problem; I think you'll find that ECM on 2^n+/-1 takes about the same time now (for the same n). That would mean that I can do ECM on, for example, P773 and M773 at the same time by doing ECM on M1546, and it will take just as long as ECM on only P773, right? When I find a factor, I'll just have see which number it divides. Interesting idea ... but, the algorithm being O(n log n), it _should_ take a bit longer to run a single transform with run length 2N than it does to run two transforms each with run length N. This is particularly relevant since there is a good chance (with small exponents) that the FFT will run from the processor cache; if doubling the FFT run length causes overspill into main memory, the performance could suffer dramatically. 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: Factoring numbers...
On Tue, 12 Oct 1999, Jukka Santala wrote: Is it just me, or does factoring smaller Mersenne numbers take propotionally much longer? I would expect M727 to be much faster than the 33M range to a fixed depth, yet the opposite _seems_ to be true. It's not just you, it's a natural consequence of the property that all factors of Mp must be of the form 2kp+1, so with a fixed depth and larger p there are fewer possible factors to check. Ofcourse, I can't be sure about this, because the real complaint I have is that factoring numbers to depths beyond the "default" seems nearly impossible. The manual factoring assignment seems like the only possibility to force these, yet it doesn't work like the normal factoring (Doing one bit depth at time) and is a pain on a dual-CPU machine. Is it possible we'd get a third parameter to the Factor= work-line specifying the intended depth for the factorization? Also, usually for some reason Prime95 seems to reject most (all?) Factor= statements I've tried, could we get some more detailed instructions on this? -Donwulff _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers -- Henrik Olsen, Dawn Solutions I/S URL=http://www.iaeste.dk/~henrik/ No, power off on shutdown is not SMP safe. It kind of happens to work on a lot of boards. If making that APM call reformats your disk and plays tetris on an SMP box, the bios vendor is within spec (if a little peculiar).Alan Cox, on the Linux Kernel list _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring numbers...
George Woltman wrote: Since factors are of the form 2kp+1 there are many more factors to test when you factoring M727. Yes each factor can be tested in less time, but this is overwhelmed by extra factors to test. Thanks to everybody pointing this one out, I missed the obivious implication of the form of factors earlier. It does make sense now, though. You will find more factors using ECM. Compare the cost of running 700 curves at B1=25 (this will find most 30-digit factors) against trial factoring to 99 bits! It is true that ECM can miss a factor, but for M727 which has had thousands of curves run at bounds as high as 50,000,000 - the chance of finding a factor smaller than 30 digits is.well, zero. By now it should be obivious I'm not too well versed in this stuff, however... I've always been told that ECM is "not guaranteed to find all factors", is it however expected (or guaranteed, if you will) to find all factors under X bits given _enough_ curves? And is the probability of finding any given factor by ECM only a function of it's number of bits, or do other things affect it as well..? -Donwulff _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring numbers...
"Brian J. Beesley" wrote: // Regarding factoring Mersennes to v19 depth... If you do decide to do this, you're on your own - don't be surprised if someone else does the same thing independently - there's no mechanism for coordination to avoid wasted effort. Partially. There now exists software to automate most of this, with intent to update the shared status files every month. Don't remember the URL, but little browsing of the Prime95 homepage should turn this stuff up. It's not exactly what I was looking for, though, I'm playing on filling some of the holes in Cunningham-tables and this means expending some extra effort on the lower Mersenne numbers. I'd like to have trial-factoring beyond the v19 limit among the options to go at this, altough I'm understanding this isn't apparently very fruitful method. Anyway, still waiting to hear if ECM will, eventually, find all factors or if it leaves "factors" in the range... -Donwulff _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring numbers...
Jukka Santala wrote: Is it just me, or does factoring smaller Mersenne numbers take propotionally much longer? I would expect M727 to be much faster than the 33M range to a fixed depth, yet the opposite _seems_ to be true. For any given factoring bit-depth, larger exponents will take a shorter period than smaller exponents. This is due to the number of potential factors that are available in at any given depth. Each bit-depth takes twice the amount of time to test as the previous one (ie: 2^57 takes 2x the length of 2^56) To determine the approximate number of potential factors that must be tested at any given depth, take the bit-size of the first pontentail factor, 2p+1, and double for each bit-depth up to the bit-depth you want. Finally, divide by 2 (eliminating potentials not meeting the 8n-1 or 8n+1 rule). So, the first potential factor of 727 would be 1455 (an 11-bit number). Take 1 for the number of potential 11-bit factors, and double over and over until you get where you want (2 12-bit potentials, 4 13-bit, 8 14-bit, etc.). However, 33,219,283's first potential factor is 66,438,567 (a 26-bit number). It has 1 26-bit potential, 2 27-bit, 4 28-bit, etc. Take these numbers and divide by 2 for the numbers of potential factors that need testing. You can see how there are *way* more potential 57-bit factors for 727 than 33,219,283. NOTE: These figures are approximate as 727 may only have say 3 potential 14-bit factors to test. (Actually, it only has 2!). It will give you a good idea of the number of potential factors you are looking at testing for any given bit-depth though... To illustrate better: To test the exponent 727 at 2^57 (only 57-bit factors), you must test approx. 7 x 10^13 potential factors. To test the exponent 33,219,283 at 2^57 (only 57-bit factors), you must only test approx. 2.15 x 10^9 potentail factors. BTW, there is a more accurate way to determine the exact number of potential factors that need to be tested at any given depth, but requires a little more effort. And when we're talking a difference of a couple million potential factors with a total of 100 trillion potential factors to test, is it really important to know the exact number?? Eric Hahn _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Factoring numbers...
Anyway, still waiting to hear if ECM will, eventually, find all factors or if it leaves "factors" in the range... The best way of thinking about this is that each curve at a given bound has a small but non-zero probability of finding a factor of a certain length, assuming that one exists. There are a very large number of curves available, and so the probability of missing the factor on *all* the curves can be made extremely low --- but non-zero. This handwaving approach is far from rigorous but it is an extremely good approximation of the truth. So yes, in principle it can leave factors undiscovered. In practice, it will find them within a reasonable time --- but depending on your luck that time could be short or it could be lengthy. A few examples from personal experience might be illustrative. The largest factor I've found with ECM was a 45-digit factor of 423*2^423+1 and was found in phase 1 with the curve bound set at 3 million. I estimate I had a roughly one in twenty thousand chance of finding that factor in the number of curves I ran. At the other extreme, I recently used MPQS to finish off a factorization of an 89-digit integer, only to find that one of the factors had 30 digits. I had already found a 33-digit factor of the number for which the C89 was the cofactor, but missed the P30. I estimate that I had a less than 1% chance of missing the smaller factor given the amount of ECM work I had done. In the first case I was lucky, and the second I was unlucky. That's the nature of ECM. Paul _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring data
Hi all, At several users request I've uploaded factoring data for all exponents below 79,300,000. You'll need a special decompression program I wrote. See http://www.mersenne.org/status.htm for details. Regards, George _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring
Does anybody know if there is an exponent where the factor is, or know whether there is a proof on whether a factor can (or can't) be, a root?? A square?? To clarify this: We know that any factor of 2^p-1 is in the form 2kp+1. Letting x =2, Can (2kp+1)^x = 2^p-1 ?? Can (2kp+1)^x * (2kp+1) ... = 2^p-1 ?? Eric Hahn _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring
At 04:27 PM 9/21/99 -0700, Eric Hahn wrote: We know that any factor of 2^p-1 is in the form 2kp+1. Letting x =2, Can (2kp+1)^x = 2^p-1 ?? Can (2kp+1)^x * (2kp+1) ... = 2^p-1 ?? No known factors of Mersenne numbers have x1, but it hasn't been proven that it is impossible. +-+ | Jud McCranie| | | | Programming Achieved with Structure, Clarity, And Logic | +-+ _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring LL tests
I was reading Fermat's Enigma today and something occurred to me...would it be possible to work with a number quicker if we used a higher base? I.E. Use base 32 instead of base 10? Thus, you're doing less math. Of course, this would have to be in software because the floats can't be in that base. G-Man _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring LL tests
At 01:10 PM 7/18/99 -0400, Geoffrey Faivre-Malloy wrote: I was reading Fermat's Enigma today and something occurred to me...would it be possible to work with a number quicker if we used a higher base? I.E. Use base 32 instead of base 10? Multiple precision arithmetic operations do that. +--+ | Jud "program first and think later" McCranie | +--+ _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring and Databases
I may be a little obtuse here (and spelling, expression of ideas may be inadequate) but A Mersenne number's prime divisors are unique to that number. Letting a and b be primes, 2^a - 1 and 2^b - 1 have completely different factors. So we can make a table (database) with p1 divides M(q1) p2 divides M(q2) p3 cannot divide any Mersenne number p4 divides M(q3) p5 cannot divide any Mersenne number p6 divides M(q2) etc. where p1 = 3, p2 = 5 and so on for all the primes in sequence. The q1, q2 will also be primes but not necessarily in sequence and may occur several times (as it does for p6). I will use the language that "pn belongs to qm" to mean that the nth prime is a divisor of the Mersenne number q sub-m (2^qm - 1). I can then say that pn (the nth prime) either fits condition A (it divides M(qm) where qm is known) or that pn fits condition B (it cannot divide any Mersenne number). ALERT: Am I right about conditions A and B or does condition B work for specific Mersenne numbers only? I suspect that if someone looked at the primes up to p200, the 200th prime, all have an associated Mersenne number M(qm) (M of q sub-m). Lucas Wiman, for example, states that he has found 1868 new factors in the range of Brian's 10,000,000+ digits, which I take to mean that 1,868 new primes are known to belong to a specific qm. Why test factor for primes in the range 2^1 to 2^10? If someone made the table I described, it is possible that all primes less than 2^10 are in the table I have described because they are known divisors of a Mersenne number OR are not candidates for dividing any Mersenne number by other conditions (subject to the ALERT above). Therefore factoring could start at 2^10 + 1 and continue up to 2^x (where x is a suitable integer that GIMPS choses). Eventually, all primes in the range 2^10 to 2^11 will be covered (not a candidate for a divisor of a Mersenne number or the prime is known to belong to qm for some m). Then 2^11 from 2^12 will be covered, etc. There is a key idea here, that each pn will eventually belong to some qm, and that the smallest pn without a qm will rise over time due to the effort of factorers such as Lucas Wiman. Would we be able to try brute force factoring at some point for the Mersenne number M(s) where s 10,000,000 since there are so many primes taken out of the potential list? ALERT: I said "each pn will eventually belong to some qm". Is it possible that p1234 (the 1,234th prime) is never a divisor of a Mersenne number? O.K. Ken, Luke, Brian and you other smarter-than-me guys and good mathematicians, fix this up, shoot it down, use it or whatever else is possible. Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
re: Mersenne: Factoring and Databases
Why test factor for primes in the range 2^1 to 2^10? If someone made the table I described, it is possible that all primes less than 2^10 are in the table I have described because they are known divisors of a Mersenne number OR are not candidates for dividing any Mersenne number by other conditions (subject to the ALERT above). Remember that the smallest factor of M_p (p prime) is 2*p+1. This is the smallest factor in a fair number of cases. This means, however, that the smallest M_p which has a factor around 2^10 must have p~=2^9. I think we're well past that point. If I understand you correctly, you suggest making a massive table of primes, and what M_p they divide. This would be very inefficient!! Since I doubt that you could Store such a table in memory, the lookup time would be enormous compared to the time spent to actually testing the factor. Even if you could store it in memory, I think that the lookup time would still be greater than the time spent testing the factor. If you mean to create a range (eg: 2^32) and test for which M_p divide primes in that range one by testing the potential factors, this might work, though Chris Nash did this on smaller ranges, and most of the results weren't worth much. I think it is much faster to test exponents for factors rather than the other way around, when dealing only with prime exponents. -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Factoring, again
Will change the "engine" to keep going to 2^33 after finding the first factor report the results from that. OK, here's the results. (All factors to 2^33 found, input is 159,975 largest primes 36 million) Sieve 6 smallest primes, 3517525 calls, 40.15s Sieve 10 smallest primes, 2972446 calls, 39.82s Sieve 14 smallest primes, 2693566 calls, 41.75s Sieve 18 smallest primes, 2515556 calls, 44.76s (The first 2 primes are sieved out "mod 120" as in George's code. The others are done in groups of 4 since you can do arithmetic modulo p in an 8 bit field if p128) Model the time as T=aX + bY + Z where X is time per call to the factoring routine, Y is time to sieve 1 extra prime and Z is a fixed overhead. So we have 2693566X + 14Y + Z = 41.75 2972446X + 10Y + Z = 39.82 3517525X + 6Y + Z = 40.15 Solving this system of equations (to a sensible precision) yields (X = 8.49E-6,Y = 1.074,Z = 3.84) The result for 18 primes sieved is consistent with this model to within a couple of tenths of a second. The timings come from the PC RTC, which has a resulution of 55 mS, so this fit is reasonable. Will, am sending you an extra message containing the "factors found" file for verification. Regards Brian Beesley Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Factoring, again
Brian J. Beesley writes: I put a development version on my anon ftp server about three days ago. ftp://lettuce.edsc.ulst.ac.uk/gimps/DecaMega/factor95.c Um, that's an unfortunate choice of name; George's P-1 factorer is "Factor95" (though there's a newer version, renamed to Factor98). Of course, George's "95" was for the year he wrote it, I think, rather than the number of bits, which I'd guess is your reason for that name.:) This is the 95-bit-capable code I gave George about early April. It isn't fully optimised, it needs to be turned into MASM source, properly aligned have removed the horrendous slow kludge used to work around a serious MS VC++ inline assembler bug. The 63-bit-capable code I'm using is simply hacked down from this in an obvious way. I didn't even bother to look for any more optimization which would be possible as a result of the various temporary results being one 32-bit word shorter. And here I thought it was quite fast enough already.:) The sieving I'm messing about with is embedded in the "engine" that generates possible factors, rather than the factoring code itself. Interesting. That is also, as I recall, how Peter-Lawrence Montgomery's trial factoring program does this. Mersfacgmp does the sieving and factoring in the same loop, which probably costs it quite a bit in terms of locality in comparison. Well, against my code is that it stops as soon as it finds one factor So does George's (in each sieve pass), but not mersfacgmp (unless it's told to on the command line) nor (I think) PLM's program, triald. Quite frequently one finds that the first factor one tries works (if p = 3 mod 4 and 2p+1 is prime, this is _guaranteed_, but obviously isn't worth coding as a special case). Yup. Also my program reads a list of exponents from a file rather than generating them, So does mersfacgmp, George's, and PLM's. Though mersfacgmp can also read from standard input; it doesn't have to be a file. Mersfacgmp can also read its own output, to continue from earlier work, whether a factor was found or not. however I don't think there's much speed penalty involved in this either way. My code is written so that various multiple-precision operations will "early out" is the high word is zero, this happens a lot when the factors are 2^32, Yup. Libgmp also has this, to an extent, since numbers are stored in a variable length array. mind you I could write a one-stage version for factors 2^31 which would be faster still. Somehow I don't think we need that.:) In fact, I could already generate a list of all primes up to 2^32 and the Mersenne exponents, composite or not, that they factor, using my "reverse" method. That might even be less than a day on my new P233 MMX. The only reason I haven't done it, actually, is that I _still_ don't have enough disk space ... unless I save the data in some compact, binary format. But I may run it anyway, and then keep only the data for prime exponents under 100 million or so. The code I'm using to output factors is inefficient, but I don't think that's a major factor. Almost certainly correct. Though running it with profiling would tell us for sure. The PII-350 timings are actually for one thread on a dual PII-350 system, there were two instances of Prime95 running LL tests in the background. For this reason I think a fairer PII-350/P90 ratio would be 4.5 rather than the usual 5. (4 is definitely low...) Probably, but recall that I fudged some the other way because there was probably another program running on my machine as well. And, if there was, it was at the same priority, not (relatively) nice'd. Not that it really matters; your code is obviously faster. Will change the "engine" to keep going to 2^33 after finding the first factor report the results from that. Thanks; I've already got and unpacked the data and it looks fine. I'll compare to what mersfacgmp has done - it continued from your first factors to the next power of two as part of my update scripts - to double check everything. Meanwhile, ran again to 2^40 with sieveing of first 10 primes got 266,072,661 calls in 3530 secs. Bearing in mind sieving overheads etc. it looks like I'm getting better than 10 uS per pass of the factoring routine. I don't know how this relates to Prime95's internal reporting, the same system gets "0.036 sec per iteration" factoring (using the routine that works to 2^62) running Prime95, but I don't know what that's measuring. I'd guess George will let you know. There's definitely a few percent to be wrung out of my code, when I get a chance. Even better.:) Will Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Factoring and M38
Well, looks like factoring on TI calculators won't be feasible or useful. :-( Before more data comes in, I'd like to state that I believe three things: A) The 38th Mersenne prime discovered has an exponent in the neighborhood of 6,900,000. B) We *are* missing a Mersenne prime between 3021377 and the 38th discovered prime (all that's been disclosed about it is that it has an exponent between 6 and 7 million). I believe that this missing prime's exponent is in the neighborhood of 4,700,000. C) The exponent of the Mersenne prime that wins the EFF decamillion digit prize will either be just at the limit (33.22 million) or it will be in the neighborhood of 48 million. Time will tell to see if I'm right. :-D Ptoo bad (C) won't be confirmed/rejected for a few years. S.T.L. (June 19, 1999) Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Factoring
Chris Jefferson [EMAIL PROTECTED] writes: Just one question / comment. We want to find 2^p mod n where n is in form 2kp + 1 If we KNOW 2kp + 1 is prime, then the euler totient fn. of n is 2kp, call this T Also, if a is co-prime to n, a^T=1 mod n 2 is obviously co-prime to n, so 2^T=1 mod n So another way of working out if a factor would be to work out So if 2kp + 1 is prime, 2^(2kp)=1 mod (2kp + 1) Herein lies my problem: I know that if p is prime, 'mod p' is a group under muliplication. I know that 2*(2^(p-2))=1 mod p so 2^(p-2) is the inverse of 2 and only by multilplying by 2^(p-2) can I get 1. Now, this implies that for no 0N2kp, 2^N=1 mod (2kp + 1) so 2^p cannot be 1 mod (2kp + 1) ? If q (= 2kp + 1 in Chris's notation) is an odd prime, then 2^(q-1) == 1 (mod q) by Fermat's little theorem. We are interested in the multiplicative group modulo q. The order of 2 divides q-1 = 2kp. We check whether this order (Chris's N) divides p (in which case it must equal p since p is prime). Check the computations with p = 11 and q = 23. 2 * 2^(p-2) = 2 * 512 = 1024 == 1 (mod 11). So 512 == 6 (mod 11) is a multiplicative inverse of 2. How does this prevent 2^11 == 1 (mod 23)? Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Factoring
Now, this implies that for no 0N2kp, 2^N=1 mod (2kp + 1) That depends on whether 2 is a primitive root of 2kp+1. If 2kp+1=11, p=5, 2 is a primitive root and 2^p is -1. If 2kp+1=7, p=3, it isn't, and 2^p is 1. phma Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Factoring
I was just wondering, could anyone give me any info on how factoring is done, is there a preliminary factoring before numbers send out, how high we factor, what possible factors are, etc. and also, I would really like to see the maths behind it as well. I need something to study over summmer vac :) Chris Jefferson, Girton College, Cambridge, [EMAIL PROTECTED] Someone may have beaten me to Fermat's Last Theorem, but I've done Riemann's general equation. However it won't fit in my signature file... Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: factoring 10^7 digits
Sounds about right for a SWAG estimate. SWAG? SWAG stands for Scientific Wild-Assed Guess - translation: educated guess -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Factoring Mersenne numbers
Sorry if this has been mentioned before, but... I was thinking (always dangerous!) about some of the smaller Mersenne numbers, like 2^727-1, for which no factors are known. 2^727-1 has 219 digits, and we are pretty darn sure that it has no prime factors less than 40 digits long. Therefore it would seem sensible to "assume" that it is the product of only two prime factors. This may be also a reasonable assumption for some other small exponents for which no factors are known. In this case, there exist (large prime) integers a, b such that (2 * a * n + 1) * (2 * b * n + 1) = 2^n - 1 A bit of rearrangement leads to the equation 2 * a * b * n^2 + (a + b) * n - 2^(n - 1) = 0 which it looks "feasible" to solve - yielding directly the two prime factors of 2^n-1, assuming the assumption is correct. On the other hand, if the equation has no integer solutions for a b, then we know that the assumption is incorrect, and that there must therefore be more than two factors of 2^(n-1). Given that a 219 digit number can't have all that many factors each bigger than 10^40, it seems that it might be worthwhile trying to solve the equation, at least for n=727. Regards Brian Beesley Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Factoring Mersenne numbers
Earlier today I wrote: In this case, there exist (large prime) integers a, b such that (2 * a * n + 1) * (2 * b * n + 1) = 2^n - 1 A bit of rearrangement leads to the equation 2 * a * b * n^2 + (a + b) * n - 2^(n - 1) = 0 which it looks "feasible" to solve - yielding directly the two prime factors of 2^n-1, assuming the assumption is correct. Aaargh! The correct rearrangement is 2 * a * b * n^2 + (a + b) * n - (2^(n - 1) - 1) = 0 Doesn't affect the argument, though. Regards Brian Beesley Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Factoring Mersenne numbers
At 02:48 PM 5/27/99 +, [EMAIL PROTECTED] wrote: which it looks "feasible" to solve - yielding directly the two prime factors of 2^n-1, assuming the assumption is correct. Aaargh! The correct rearrangement is 2 * a * b * n^2 + (a + b) * n - (2^(n - 1) - 1) = 0 Doesn't affect the argument, though. But I don't see how you're going to find a solution of this any faster than factoring. About 1980 I had an idea similar to this to find a factor that looked at the remainders of division and did a sort of Newton's method to find a root, which immediately gave a factor. It worked great when the number was a square. Otherwise it degenerated into a poor implementation of a brute force search. +---+ | Jud McCranie [EMAIL PROTECTED] | | | | Inside every composite integer is a prime | | factor waiting to get out.| +---+ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Factoring Mersenne numbers
I was thinking (always dangerous!) about some of the smaller Mersenne numbers, like 2^727-1, for which no factors are known. 2^727-1 has 219 digits, and we are pretty darn sure that it has no prime factors less than 40 digits long. Therefore it would seem sensible to "assume" that it is the product of only two prime factors. ... In this case, there exist (large prime) integers a, b such that (2 * a * n + 1) * (2 * b * n + 1) = 2^n - 1 Actually, all factors of any 2^n-1 can be expressed in the form 2*a*n+1, including 2^n-1 itself (for prime n, obviously.) -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Factoring bignums
On Wed, 12 May 1999, Pierre Abbat wrote: Is there a program for factoring numbers up to, say, 2^128 in a reasonable time? I tried bc but it doesn't have a factor command, so I wrote a loop and it spent all its time outputting. Get Richard Crandall's giantint package, it contains factor, which will factor "any size" numbers, using a variety of algorithms. As for time, I just did a quick test: echo 123456789012345678901234567890123456789012345678901234 |time ./factor Sieving... 2 * 73 * 1723 * Commencing Pollard rho... .. .. .. Commencing Pollard (p-1)... .. Commencing ECM... Choosing curve 1, with s = 352116908, B = 1000, C = 5: .. 17108860903 * 28685059068699533197755335074782923141 14.11user 0.01system 0:15.72elapsed 89%CPU This on a 188MHz Pentium. You can get giantint from http://www.perfsci.com/ -- Henrik Olsen, Dawn Solutions I/S URL=http://www.iaeste.dk/~henrik/ `Can you count, Banjo?' He looked smug. `Yes, miss. On m'fingers, miss.' `So you can count up to ...?' Susan prompted. `Thirteen, miss,' said Banjo proudly. Terry Pratchett, Hogfather Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: factoring and LL-testing with perl
Hi all,
I haven't run prime95 the past year and I'm still among the
top ten producers. Well, last time I checked I was.
Didn't think I would last that long up there. ;-)
I was goofing around with perl today and recalled a cool
way of factoring/primality checking using patternmatching.
I also tried out the bigint module and did some LL-testing,
verifying all known MP's from M2281 and down.
I thought I'd share some code, very simple but perhaps
interesting for some.
Here's an LL-test of M13. Change the assignment on the
first row to test another number, remember it has
to be prime. M13 is the biggest number this code can handle.
# LL-test 1
$P = 13;
$MP = (1 $P) - 1;
$U = 4;
for ($i = 1; $i $P - 1; $i++)
{
$U = ($U * $U - 2) % $MP;
}
if ($U == 0) { print "M$P is prime\n"; }
else { print "M$P is composite\n" }
Perl is nice, this particular code is very similar to C,
in case you haven't noticed.
Next step is incorporating the bigint module which is a part of the
standard perl distribution:
# LL-test 2
use Math::BigInt;
for $P (3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61) {
$MP = Math::BigInt-new(2);
$MP = ($MP ** $P) - 1;
$U = Math::BigInt-new(4);
for ($i = Math::BigInt-new(1); $i-bcmp($P - 1); $i = $i + 1)
{
$U = ($U * $U - 2) % $MP;
print "\r$i\t($P)\t";
}
$not = $U == 0 ? '' : ' not';
print "M$P is$not prime\n";
}
Besides support for big numbers the test is now wrapped up in a
loop that tests prime exponents = 61 and 2
Also, progress printing in the innermost loop has been added.
Now to the patternmatching, this is fun. The number to factor
is represented as a string of characters, eg:
'o' is 5
The concept is to find a sequence of 2 or more characters that
is repeated 2 or more times and matches the whole sequence.
The pattern for this is:
/^(oo+)\1+$/
Short explanation:
o matches a literal o
+ means 1 or more, thus oo+ matches 2 or more o's
Quantifiers in perl are greedy, meaning they match
as much as possible.
The parens are for catching parts of the matched string
to special variables. The first pair goes to $1, the second
to $2, etc.
\1 is a backreference, meaning the exakt sequence that was
matched by the first pair of parens.
^ means match at the beginning
$ means match at the end
The forward slashes are perls regex-operator.
Now some code:
while ($num = STDIN)
{
chomp $num; # ditch the newline char
last if $num == 0; # like C's break
$seq = 'o' x $num; # make a sequence of $num o's
# =~ is perls match-operator
print "$num is prime\n" unless $seq =~ /^(oo+)\1+$/;
}
When the pattern matches we have a factor represented by
the length of $1, the dividend of the number being
tested and it's smallest prime factor. We can alter the
regex slightly to get the smallest prime factor into $1
instead. Quantifiers are greedy by default in perl but
can be forced to the opposite by appending a ?
/^(oo+?)\1+$/
Imagine we are testing the number 30. The new regex will
match the 2 first o's with (oo+) and then repeat the sequence
15 times to exactly match the string. With the first regex
(oo+) would match all 30 o's before the engine continues,
only to fail immediately. It would the back up and pop off
1 char, matching 29 o's and try again. This proceeds until
until 15 is reached and the total expression matches. This
process is called backtracking. We need this knowledge for
the next step.
If we were to completely factorize our original number (30)
we would probably want do something like this:
while (match) {
print the found factor, $1
replace the number, $N, with the $N / $1
}
print the remaining prime factor
What's interesting in our case is that the number is
represented by the length of a sequence, so how do
we say N = N / F in an easy way? The obvious
$N = 'o' x (length($N) / length($1));
works fine, thats what I would have come up with. The
Perl Cookbook demonstrates a method using more pattern-
matching and substitution. The idea is to replace each
repeated sequence with a single o. With our example of
30 each pair of o's becomes a single o leaving 15. The
next step substitutes each triplet with a single o
leaving 5. In perl:
$N =~ s/$1/o/g;
This means search for $1 in $N and replace with o
The g is for global meaning all occurences.
# almost exactly from the book...
# shift is a function that pulls the next argument from the
# commandline.
for ($N = ('o' x shift); $N =~ /^(oo+?)\1+$/; $N =~ s/$1/o/g;) {
print length($1), " ";
}
print length($N);
Robert
~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^
Robert Friberg
Delphi, C, Perl developer for hire
Boras, Sweden
~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^~v~^
Mersenne: Factoring bugs
[EMAIL PROTECTED] writes: As LL tests begin to go beyond the limits of older machines, now may be a good time to consider a distributed factoring effort. I've wanted to see one for a while now but frankly, implementing many of the algorithms is over my head. That, and the lack of a permanent home have made me shelf it. If, however, anyone wants to talk about donating code or a server, I don't see why we couldn't make one, and factor some of the unfinished mersennes. See ECMNet. I'm pretty sure there's a link off www.mersenne.org and off my mersenne.html. There's a new server/client setup that's apparently almost as automatic as Prime95/PrimeNet. (I haven't had time to try it yet). But note that ECMNet is trying to completely factor various numbers, including the Mersennes with exponents into the low thousands; it is not trying to find factors of the Mersenne numbers that GIMPS is interested in. If you want to do the latter, use Prime95. In my mind, the v17 bug illustrates how important factoring is. It provides an easily-verified proof of compositeness. Yes, and that's the whole reason there is a factorer part of GIMPS: because having it eliminates possibilities faster, and with no need for a doublecheck. Factors are very easy to confirm; my 200MHz Pentium can probably verify every known factor in a day or three (and I have had it do so a few times in the past). But Prime95's factoring code has also had bugs at times; a bug-free program is - as I'm sure most of us are aware - effectively impossible. Which is part of why there are other programs that do the same things, like the mers package that I maintain. Prior bugs in the mers package LL testers and factorers were exposed by comparisons with output from Prime95, just as prior bugs in Prime95 were exposed by comparisons with the mers package programs. Will http://www.garlic.com/~wedgingt/mersenne.html Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Factoring...
Howdy, I'm running PrimeNet on my 486sx/25 Linux router box (yeah, I know...). Right now it's factoring M8956237, and it seems to do about one pass per day. It's going to take a while. :) Would adding a 487 math co-processor speed this up? If so, by how much? I have no idea about the algorythm used, so I don't know if this is primarily doing integer or floating point operations. Thanks, Bryan -- Bryan Fullertonhttp://www.samurai.com/ Owner, Lead Consultant http://www.feh.net/ Samurai Consulting http://www.icomm.ca/ "No, we don't do seppuku." Can you feel the Ohmu call? Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Factoring
Hi, Last weekend when i was testing Prime 95 i noticed that factoring low numbers took much longer as high numbers. Factoring M17XXX from 2^52 to 2^54 took minutes per pass while factoring M9XX from 2^52 to 2^54 took about one minute to complete the whole factoring. How is this possible? Greetz Sander __ Get Your Private, Free Email at http://www.hotmail.com
Re: Mersenne: Factoring
"Sander Hoogendoorn" [EMAIL PROTECTED] asks Last weekend when i was testing Prime 95 i noticed that factoring low numbers took much longer as high numbers. Factoring M17XXX from 2^52 to 2^54 took minutes per pass while factoring M9XX from 2^52 to 2^54 took about one minute to complete the whole factoring. How is this possible? Only primes in [2^52, 2^54] which are congruent to 1 modulo 17XXX (or modulo 9XX) need be checked. [There are other restrictions, such as the prime being == +- 1 modulo 8.] For the larger exponent, the density of candidate divisors is 17XXX / 9XX ~= 1/50 times as large. For the larger exponent, the cost of testing each divisor (using the binary method of exponentiation) is log_2(9XX) / log_2(17XXX) ~= 23/14 times as long. Overall, when the interval [2^52, 2^54] is fixed, the checking for the larger exponent proceeds 50 * (14/23) ~= 30 times as fast. On the other hand LL testing for the larger exponent takes 50 times as many iterations, and each iteration takes about 50 * (23/14) ~= 80 times as long, so this cost grows by a factor of 4000. Keeping the (LL costs)/(factoring costs) ratio constant, the factoring could search an interval 30 * 4000 ~= 2^17 times as long. Alas, [2^69, 2^71] needs more than 64 bits of precision to store candidate divisors, so you probably stop factoring at 2^64 or switch to other algorithms.
Mersenne: Factoring
Sander Hoogendoorn writes: Last weekend when i was testing Prime 95 i noticed that factoring low numbers took much longer as high numbers. Factoring M17XXX from 2^52 to 2^54 took minutes per pass while factoring M9XX from 2^52 to 2^54 took about one minute to complete the whole factoring. How is this possible? All factors of a Mersenne number with a prime exponent, p, are of the form 2*k*p + 1 where k is a natural number (positive integer). So the larger p is, the fewer the number of possible factors between two constants like 2^52 and 2^54. In this case, 17XXX divided by 9XX is at most 0.2%, so checking all the possible factors of M17XXX takes about 500 times as much CPU as checking all the possible factors of M9XX within the same range of numbers. This a large part of why higher exponent Mersennes are trial factored farther than lower exponent Mersennes. While I'm here, I'll mention for the newcomers that I collect all sorts of factoring data on Mersenne numbers, including George Woltman's ECM GIMPS data, the Cunningham Project ftp site data maintained by Paul Leyland, Conrad Curry's Factor98 data, and directly from interested individuals like yourself; just send it to me in email, plain text or as MIME attachment(s). The data I've collected for exponents under 200,000 is available below. I have data for many larger exponents, including all primes thru 21.5 million or so, but do not have room on my ISP's web server to upload it. Will http://www.garlic.com/~wedgingt/mersenne.html (proofs, links, etc.) mersfmt.txt (data format description) mersdata.zip (data, zip'd) mersdata.tgz (same data, different packing) factoredM.txt (completely factored Mersennes) ...
Mersenne: Factoring Fermat numbers
Sorry if this is a duplicate message. I am not sure if my previous attempt to
send this message got there or not.
Several months ago I downloaded fermat.exe from the Mersenne.org site
("zip file" at http://www.mersenne.org/fermat.htm). This program attempts
to find factors of Fermat numbers (F16 to F20) using ECM factoring.
I have run it occasionally, and it seems to work. (I have found some of
the known factors, but no new ones yet.)
More recently, I downloaded the source code from Perfectly Scientific
Inc (link is on the same page as above). I have compiled the source code
successfully, but the resulting program does not seem to be working, since I have
found none of the known factors with several runs of the program. (The output to
the screen looks the same as George's executable, except for not finding any
factors.) I even modified the line that says "seed = random number"
to say "seed = value", where "value" is a number that resulted in finding a factor
in the original executable. (Note: the original executable and my executable
are for Windows 95/NT.)
My first few compiles were with Watcom C. I then tried MS Visual C/C++,
using the command line that was suggested in the comments in the file fermat.c:
cl -O2 fermat.c fgiants.c giants.c
A couple of "test programs" are included with the Perf-Sci source files.
These programs use giants.c (but not fgiants.c). I tried these two (with
Watcom C) and they seem to work OK.
The comments at the top of each of the files used for "fermat.exe"
indicate that changes have been made since George's executable was created.
Perhaps Perf-Sci introduced a bug somewhere? Does anyone have any other ideas
about what the problem could be?
Mersenne: Factoring
Ok, George's programs looks for only for factors of M(n) in form 1) 2kn+1 that's clear why 2) 1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,or 119 modulo 120 but this is not. Why factors 120k+13 are not considered? Or 120k+19? Why only those 16 reminders of ~30 primes below 120?
Re: Mersenne: Factoring
At 08:30 AM 1/12/99 -0500, Alexey Guzeev wrote: Ok, George's programs looks for only for factors of M(n) in form 1) 2kn+1 that's clear why 2) 1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,or 119 modulo 120 but this is not. Why factors 120k+13 are not considered? Or 120k+19? Why only those 16 reminders of ~30 primes below 120? Only primes of the form 2kn+1 can divide 2^n-1. +---+ | Jud McCranie [EMAIL PROTECTED] or @camcat.com | | | | "We should regard the digital computer system as an | | instrument to assist the number theorist in investigating | | the properties of his universe - the natural numbers."| | -- D. H. Lehmer, 1974 (paraphrased) | +---+
Mersenne: factoring code
I wrote: Henk Stokhorst writes: table:1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,119 In case it still isn't clear to someone out there, this is the list of numbers less than 120 that are relatively prime (no common factors greater than 1) to 120. Oops! I should have thought about this some more before sending this out; it's not quite correct. All the numbers in this table are indeed relatively prime to 120, but there are 16 more such numbers, each differing from one of the above by 60. My only excuse is that I was thinking in terms of my old, pre-GIMPS, factoring code, which used 60 instead of 120 but still had 16 entries. Those 16 out of 60 are equal to (2 - 1)*(3 - 1)*(5 - 1) out of 2*3*5: cancel half, then one third, then one fifth. Will
Mersenne: factoring code
Henk Stokhorst writes: table:1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,119 In case it still isn't clear to someone out there, this is the list of numbers less than 120 that are relatively prime (no common factors greater than 1) to 120. for number := first to last number in table do for factor := smallest to highest possible factor do result := Mersenne candidate divided by factor if result = number then factor found ; exit next factor next number Yes, this is the basic idea. While I would have expected the code for factor := smallest to highest possible factor do result := Mersenne candidate divided by factor for number := first to last number in table do if result = number then factor found ; exit next number next factor This is slightly incorrect; the "division" (the actual code does no long division) still has to take place inside the inner loop: for factor := smallest to highest possible factor do for number := first to last number in table do result := Mersenne candidate divided by (factor + number) if result = (factor + number) then (factor + number) is a factor ; exit next number next factor to be faster. Of course it isn't, but why? I believe that most of it is because there is less to do in the innermost loop. For example, the increase in the possible factor in the first case is a constant, the index into table doesn't change in the inner loop, and table isn't even read from in the inner loop. But it's also not quite that simple. If the Mersenne has one small factor and it happens to be 119 mod 120, the first method will search the entire range 15 times before finding it; the second method will find it quickly and exit. But the assembly code version is so fast - especially compared to the LL test times for the large exponents GIMPS is working on now - that it's probably not worth worrying about this last effect. Will
