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 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: Suggestions for Prime95 v19
- A menu item that forces the program to write intermediate data to disk. It is useful, when the user wants to install a new program or Doesn't stopping work with the escape key or Test/Stop already do this? You could simply stop and restart work in order to commit results to the disk. - A function which prvents writing to disk for some time. When the user writes a CDr, it sometimes is dangerous, when prime95 writes intermediate results to disk during that time. If this is a problem on your system, then you could increase the interval between disk writes to some large value, and then stop and restart work as above to commit results. I've burned three CD-R discs at quad speed with my new drive recently, and I haven't had any problems. It is nice not to have to stop Prime95 for this. Of course this will depend on how well your computer keeps up with the stream of data required by the CD-R drive. On a slower computer, a disk write from Prime95 could theoretically cause a buffer underrun. The best way to find out is with a test burn. I doubt that Prime95 will cause many problems in this regard. - Extended status information -relative speed of the system (e.g. using rolling average) -hours in use -# flops done (calculated) -# iterations done (total of all exponents) -history: all tested iterations on this machine -processor usage (compared with the unused system This sounds a little more involved (from a programming standpoint) that it is worth. But I could be wrong. 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: Re: Merced Assemblers
On Sat, 21 Aug 1999 00:15:57 -0400, you wrote: (No, I won't buy an assember. An assembLer, on the other hand ;-) ) What month comes after Assember? I think it's Dectembruary. (Or is that just on the Julian calendar?) 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: SETI on ABC News last night
The GIMPS project may be in for some serious competition for America's CPU time now, as ABC news did a story last night on the SETI project and the impending release of software for Mac and Wintel systems. Which do you suppose will sound more appealing to the average person--"the search for enormous prime numbers" or "the search for alien life forms"--especially now that SETI has such high-profile exposure? GIMPS has a big disadvantage in that area. Would anyone care to comment on the appeal of SETI? Personally speaking, it doesn't interest me at all. I don't consider its goals to be terribly useful or important, and I don't think that it has a reasonable chance of accomplishing anything. But as number theory enthusiast I find something intrinsically interesting and worthwhile about finding factors and searching for Mersenne primes. I am probably in a minority of the general population in this regard. Let's just hope we don't lose too many existing GIMPS accounts. ___ Get Free Email and Do More On The Web. Visit http://www.msn.com Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: ECM question
At Paul Zimmerman's ECM page, http://www.loria.fr/~zimmerma/records/ecmnet.html the optimal B1 value listed for finding 50-digit factors is 4300, but George's ECM factoring page uses 4400 for the same purpose. Is one of them wrong, or is there a reason for the difference? ___ Get Free Email and Do More On The Web. Visit http://www.msn.com Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Update on using Prime95 as a windows shell
Don't think I didn't try this (and a number of similar ideas). The problem was that the forked copy of Prime95 doesn't seem to start executing until ReCache completes. Either that or ReCache suspends itself until Prime95 completes - *most* unsatisfactory to hog all that memory long-term... That's interesting; I haven't been getting that problem. When pass 2b starts, Prime95 launches, and ReCache continues until the pass finishes, and then it terminates, leaving Prime95 running at peak performance. I'm running Windows 98, and I compiled your code with Borland C++ Builder 4. Could one of these factors make a difference? (If you're interested in trying out my compiled executable, I'd be glad to send it to you.) As you've found out, running ReCache to completion then starting Prime95 does have a good effect (it forces DLLs etc. which aren't currently active to be dumped, for a start). However, I certainly get more consistent results using the manual start procedure. The automatic method has been completely consistent for me. Strange... ___ Get Free Email and Do More On The Web. Visit http://www.msn.com Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Update on using Prime95 as a windows shell
Thanks for the responses to my suggestion on this topic. Brian Beesley's ReCache code was very helpful. It doesn't lower the best possible iteration time attainable on my machine, but it does provide a reliable way to get it. In fact, I found that there is only a marginal difference between the performance of ReCache+Prime95 under the Explorer GUI versus using Prime95 as a system shell. With the former, my pII-400 gets 0.188sec/iteration on an exponent around 6.39 million (320K FFT); with the later, it gets either 0.188 or 0.187 sec/iter. I made one small but useful enhancement to Brian's code: at the beginning of pass 2b, I added a call to the system() function using argv[2] as the argument. This saves the user from having to manually start Prime95 at the precise moment that Brian specified. On my desktop I have a shortcut with the command line c:\stuff\recache 64 c:\stuff\prime\prime95.exe which starts prime95 using the modified ReCache program. Now when I leave my computer for the day or go to bed, I can close Prime95 and then restart it with this shortcut in order to insure optimal performance while I'm gone. ___ Get Free Email and Do More On The Web. Visit http://www.msn.com Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Idea for running Prime95
When I first got Windows 95 almost four years ago, I discovered by accident that command.com, the DOS command processor, can be used as the Windows GUI shell. When I remembered this recently, I realized that it could be useful for some people running Prime95 on machines that otherwise go unattended and do nothing else. In the file \windows\system.ini, go to the [Boot] section and change shell=Explorer.exe to read shell=command.com /c c:\prime\prime95.exe substituting the appropriate path for Prime95. The next time the system is restarted, command.com will launch Prime95 and quit, and then Prime95 will be the only non-idle task running. In this setup, not even Explorer or the command processor will be taking up CPU time. The disadvantage is that the only way to interact with the system is to type Ctrl-Alt-Del, which brings up the task list and gives you the option to shut down the system. This method eliminates the slim share of CPU time being consumed by the usual GUI shell and other Windows processes. For a system that must frequently be used for other work, it is not useful. But for systems that sit unattended for days at a time doing absolutely nothing but Prime95 (or some other computational program), this method lets you squeeze out a little extra performance. Any comments? Does anyone else have experience doing this? ___ Get Free Email and Do More On The Web. Visit http://www.msn.com Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
RE: Mersenne: Re: Factoring bugs
From: Paul Leyland [EMAIL PROTECTED] You are merely restating a law of nature. After a point, everything becomes useless. I am reminded of a quote from Homer Simpson: "Trying is the first step toward failure." :) A question for George (and Scott): Is there any chance that Prime95's ECM factoring will ever become automated as a part of PrimeNet? Even if it is never given as a default type of assignment, it would still be useful to dedicated number theory enthusiasts who want to run it on more machines than they can manage manually. ___ Get Free Email and Do More On The Web. Visit http://www.msn.com Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Questions answered on v17 bug
George Woltman wrote:
The bug was in the routine mulmod which was supposed to compute a * b
mod c
The implementation was a rather sloppy:
unsigned long tmp;
tmp = a * (b 0x3FF);
tmp += ((a 10) % c) * (b 10);
return (tmp % c);
You can see in the first computation of tmp there will be an overflow
if
a exceeds 2^22 or 4194304. The new implementation is:
double tmp;
unsigned long q;
tmp = (double) a * (double) b;
q = (unsigned long) (tmp / (double) c);
return ((unsigned long) (tmp - (double) q * (double) c));
This implementation isn't perfect, but will work as long as a * b does
not exceed 53 bits.
This got me thinking, since I've had a use for modular multiplication in
some of the little programs that I've bee writing. Based on your code, I
wrote the following:
unsigned long mulmod(unsigned long a, unsigned long b, unsigned long n)
{
long double tmp, q;
tmp = a * (long double)b;
q = floorl(a * (long double)b / n);
return tmp - q * n;
}
In my testing, this appears to give the correct result for any 32-bit
values of a, b, and n, thanks to the 64-bit precision of Intel's 80-bit
floating point type. Is there anything wrong with this approach? It
depends on having a long double version of the floor function, which is
available on my Borland compiler.
Get Your Private, Free Email at http://www.hotmail.com
Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Re-ordering work?
I recently received an unusually small assignment--around 4.8 million--and I'm wondering if it would be okay to start it sooner by moving the relevant entry in worktodo.ini to the second line, right after the current test in progress. Is there anything wrong with this? __ Get Your Private, Free Email at http://www.hotmail.com Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Basic question: Working modulo 2^n-1
Chris Caldwell's web page on Mersenne numbers descirbes the Lucas-Lehmer test briefly and mentions that it is quick on binary computers because they can quickly perform division by 2^n-1. I know how to find integer quotients and remainders modulo 2^n with shifting and masking, but I don't understand how it is done quickly modulo 2^n-1. Would anyone care to explain? __ Get Your Private, Free Email at http://www.hotmail.com
Re: Mersenne: Prime95, Prime Server and ECM factoring
From: Paul Leyland [EMAIL PROTECTED] My home box is on the web only very intermittently. It finished a LL test several days ago and did not have another exponent ready to test, so I set it going on some ECM factoring. I run ECM with a separate copy of Prime95, stored in its own directory. This ends to reduce complications. I can also run ECM simultaneously with LL testing this way, and keep separate results files for both kinds of work. This brings me to a couple of questions: 1. Is it okay to add a mark to the ECM copy's results.txt file to remind myself which results entries I have sent to George? I don't want to change the file manually if the program ever reads it and depends on its being in a certain format. 2. Is it less efficient to run two copies of Prime95 simultaneously one a single-processor machine than to run them sequentially? They share processor time (as reported by WinTop) equally when both are working, but perhaps something is lost in the need to time-share two FPU-intensive programs. [Oddly enough, I have noticed that sometimes when I start the ECM copy of Prime95, it gets 70% to 75% of CPU time instead of the usual share of just under 50%. Can anyone explain why this happens?] __ Get Your Private, Free Email at http://www.hotmail.com
Re: Mersenne: 128 floatingpoint operations
The library gmp (GNU multi-precision) uses this algorithm although it is much slower than FFT-like methods. Maybe because it only involves integers, and there is no danger at all of rounding errors. I once wrote a gmp-based program to perform LL tests: for low exponents it worked fine but for the prime 65537 it already took much longer that mprime. Could you tell me how to find this gmp library? I searched gnu.org site for it, but I couldn't find anything. __ Get Your Private, Free Email at http://www.hotmail.com
Mersenne: Misc. things
First, I have noticed that recent versions of Prime 95 append an entry to the results file when iteration 500 of an LL test is reached. Why is this? Second, I see that there are now some composite exponents in the ECM factoring page. Why are none of them even? Is there a technical reason that makes them less interesting? Third, I'd like to suggest that a "connect now" option be included in Prime95. This would be a menu option that, when selected, causes the program to try to contact the server immediately. This would eliminate the inconvenience of having to reduce the retry interval and then raise it back to the old value whenever the user is establishing a modem connection for a short time and wants the program to send in its results during that period. __ Get Your Private, Free Email at http://www.hotmail.com
