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
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: 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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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.
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) | +---+
