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 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
Mersenne: Demonstration of LL test for M7
<< A while ago someone posted a demonstration of the Lucas-Lehmer test for, I think, 2^7-1. >> LL test: S[0] = 4 S[k+1] = S[k] ^2 - 2 mod 2^P - 1 2^P - 1 is prime if and only if S[P-2] = 0. Demonstration for 2^7 - 1 = 127: S[0] = 4 S[1] = 4^2 - 2 mod 127 = 14 S[2] = 14^2 - 2 mod 127 = 194 mod 127 = 67 S[3] = 67^2 - 2 mod 127 = 4487 mod 127 = 42 S[4] = 42^2 - 2 mod 127 = 1762 mod 127 = 111 S[5] = 111^2 - 2 mod 127 = 12319 mod 127 = 0 S[7-2] = S[5] = 0, hence 2^7 - 1 is prime. QED YEA STL _ 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: Best chance to make a "real" contribution?
At 15:14 01/22/2000 -0500, George Woltman wrote: > >Finding new factors isn't hard. Over half of the candidates are eliminated >by finding a factor rather than the expensive LL test. GIMPS by default >assigns slower machines to do the factoring work. Thus, it is not >uncommon for powerful machines to always get LL assignments and >never find a factor. This brings up something I've been wondering about. I have a dual Celeron setup running 2 instances of mprime under Linux. With both processors crunching on LL tests, I get iteration times for each processor of around .263 for exponents around 899 (where they are presently cranking). However, if one of them factors while the other does LL testing, the processor doing the LL testing takes about .220 seconds per iteration, while the one factoring also shows a factoring speed more consistent with the speed I would expect for the processor speed. My question is: Do I get more "work" done by having both doing LL testing, or would this box contribute more to the effort by having one CPU performing factoring while the other does LL testing? Thanks! Kel, coming up on 4 years of hunting for Mersenne primes _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Best chance to make a "real" contribution?
Hi Gerry, At 11:35 AM 1/22/00 -0800, Gerry Snyder wrote: >First of all, let me say that it is a thrill to be helping in the GIMPS. Welcome aboard! >Getting more computing power for the search is the main reason my new >linux system is a dual Celeron rather than a single. The second processor is a cheap way to add horsepower. It will help on many other computing tasks. An excellent decision. >But finding a factor (or another factor) of a Mersenne number would seem >more real. Finding new factors isn't hard. Over half of the candidates are eliminated by finding a factor rather than the expensive LL test. GIMPS by default assigns slower machines to do the factoring work. Thus, it is not uncommon for powerful machines to always get LL assignments and never find a factor. If you want the thrill of finding a factor, ask one of your CPUs to get factoring work only (the Test/Primenet dialog box). You can change this setting back at a later time. Finding new factors of small Mersennes, so called Cunningham factors, is getting more difficult. ECMNet and GIMPS have picked off most of the "easy" factors. I have two CPUs running ECM full-time. The last Cunningham factor I found was last summer. I do occasionally find new factors of medium-sized (1200 to 10) Mersenne numbers. In any event, choose the type of work you find most interesting. The goal here is to have fun while contributing to math research. Best regards, George _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne Digest V1 #682
Mersenne Digest Saturday, January 22 2000 Volume 01 : Number 682 -- Date: Thu, 20 Jan 2000 03:11:37 -0700 From: "Aaron Blosser" <[EMAIL PROTECTED]> Subject: RE: Mersenne: Doubling PIII (500) Memory To Increase LL Performance > Would increasing PIII (500MHz) memory from 128M to 256M improve > L-L performance? Current exponent being tested is in range 9,xxx,xxx. The best way to find out is to profile your memory usage right now. With NT, it's as easy as bringing up Task Manager when your system is doing what it normally does. Look at the "Performance" tab, and pay attention to the Physical Memory (K) section. For instance, my system shows total 196148, and available as 117332 right now. Obviously, I have plenty of extra memory (this is with Windows 2000 Professional, by the way). Your load will definitely vary depending on what other programs you have loaded. If your free memory is still pretty high, adding more won't be much help most of the time. _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers -- Date: Thu, 20 Jan 2000 03:14:28 -0700 From: "Aaron Blosser" <[EMAIL PROTECTED]> Subject: Mersenne: Unusual request... I have a bit of an odd request, but one that is peripherally related to Mersenne Primes. Today (Thursday the 20th of January) at 2:00 PM Mountain time, I will be going in with my lawyer to meet someone from the Attorney General's Office. For those of you familiar with my plight, it would mean *a lot* to me if those of you who are religous would say a little prayer for me. If you're not religious, maybe just cross your fingers and hope for the best. I know it's an odd request, but I'm just a bit nervous about the meeting. Thanks all, Aaron Blosser _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers -- Date: Fri, 21 Jan 2000 09:55:03 +1300 (NZDT) From: Bill Rea <[EMAIL PROTECTED]> Subject: Mersenne: LL Test for M7 Gimpsters, A while ago someone posted a demonstration of the Lucas-Lehmer test for, I think, 2^7-1. Would that person be so kind as to email me another copy or point me to an archive if the posts on this list are saved somewhere. Thanks. Bill Rea, Information Technology Services, University of Canterbury \_ E-Mail b dot rea at its dot canterbury dot ac dot nz http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers -- Date: Thu, 20 Jan 2000 19:57:20 - From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Doubling PIII (500) Memory To Increase LL Performance On 20 Jan 00, at 0:36, Stefan Struiker wrote: > Would increasing PIII (500MHz) memory from 128M to 256M improve > L-L performance? Current exponent being tested is in range 9,xxx,xxx. Increasing the amount of memory will have _no effect whatsoever_ unless the system is short of memory. LL testing an exponent in the 9 million range uses less than 10 MBytes of memory in total. I don't know what else you're running on your system, but I'm running similar exponents in a system with 32 MBytes memory (running under linux), and it's just FINE. Windoze will need a tad more memory but 64 MBytes would be more than sufficient so far as running Prime95 is concerned. An easy way to see if you have sufficient memory - irrespective of OS etc - is to look at the disk access light. If it's off most of the time you probably have at least enough memory in the system. If it's constantly or almost constantly on, and you hear lots of clattering from the head actuators, you *may* be short of memory - but, alternatively, it could just be that whatever you're running is doing a lot of file access. Anyway, if the disk isn't being accessed much, it isn't even worth thinking about adding more memory. Regards Brian Beesley _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers -- Date: Fri, 21 Jan 2000 21:58:21 -0800 From: Spike Jones <[EMAIL PROTECTED]> Subject: Mersenne: 1E7 digit primes I did not find in the faq where one can reserve a number of 1E7 digit primes. I was able to sell the notion of running GIMPS to the IT people at my job, but only by offering the possibility of a monetary prize. Please, how may I reserve about 50 1E7 digit primes that have been prechecked for small factors? Thanks! spike _ Unsubscribe & list info -- http://ww
Re: Mersenne: Factoring Mersenne
Daniel Grace writes: > Anyway, any mersenne's factor can be written as 2kp+1 > 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 think what you are trying to say is M_p is composite for p a prime iff 1+2kp divides (2^(p-1)-1)/p - k for some k>0. If I am not mistaken factoring this using current methods is harder than factoring 2^p - 1. Yup, almost certainly, if only because k is needed twice. The current trial factoring method does not even use k per se. Remeber it is easy to trial divide 2^p - 1 using bit wise operators, because 2^p - 1=1+2+2^2+...+2^(p-1). Let u be a potential divisor (e.g. u=2kp+1) then let j be smallest int. such that 2^j-1>u then you can try dividing 2^p-1 using just j bits of storage. e.g. start with 1+2+2^2+...+2^(j-1), subtract u, shift to the left appending 1's at the start, until you get v>u, subtract u and so on. I think that the software stops if it gets a residue of 0 before all p bits have been eliminated - in this case u divides some smaller Mersenne. Not quite. My "reverse method" works that way, and will find the smallest Mersenne exponent which is a multiple of a given odd number, but the fastest-so-far trial factoring method actually squares and perhaps multiplies by two modulo the trial factor each loop, starting with two and looping over the _bits_ of the Mersenne exponent, making it quite fast. If the particular bit is one, the multiply by two occurs; if it's zero, it doesn't. That is, it calculates the Mersenne number (two to the exponent power) mod the trial factor. This algorithm is in Knuth, apparently, which I don't have a copy of. Before GIMPS, I was doing something slower; George Woltman told me about this method, speeding up my then-current trial factoring program by a factor of about three (in Jan. 1996 or so). Will _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Best chance to make a "real" contribution?
Hello, Mersenners; First of all, let me say that it is a thrill to be helping in the GIMPS. Getting more computing power for the search is the main reason my new linux system is a dual Celeron rather than a single. If all I ever do is LL tests of non-primes, that will be fine. That helps the cause, and I have no expectation of finding a prime. But finding a factor (or another factor) of a Mersenne number would seem more real. Is there any significant probability that two 500 MHz Celerons and one 333 MHz Celeron could accomplish such a feat in a couple of years? Just thought I'd ask. Thanks for any help, Gerry -- mailto:[EMAIL PROTECTED] Gerry Snyder, AIS Symposium Chair Region 15 Ass't RVP, JT Chair Member San Fernando Valley, Southern California Iris Societies in warm, winterless Los Angeles _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
