Re: Mersenne: Trial-factorers
Brian Beesley wrote: >On 27 Oct 99, at 17:23, Eric Hahn wrote: >> >> I'm looking for program(s) capable of trial-factoring >> prime exponent Mersenne numbers (using 2kp+1) meeting >> the following requirements: >> >> [...requirements...] > >Well, I'm prepared to have a go. Could we tighten up the spec a bit? Wow!! I was going to post a message with regard to the fact that it looked like I was going to have write some code to produce my own program. While the programs that were suggested are well written, perform their designed functions, etc., they were either not capable of the tasks required or too slow to be useful. Now, look. I even have a volunteer to write some code!! :) >(a) There's also been some interest in something else that Prime95 >doesn't do - trial factoring 2^p+1. > >(b) I assume we're only interested in 2kp+1 factors. This means that >we will miss any factors which are not of this form. (Applies to >Mersenne numbers with composite exponents, and all 2^p+1 numbers - >though I believe that the "missed" exponents are easy to derive >analytically.) I'm not opposed or take exception to any possible additional capabilities... It just might require a little extra effort for the coding. >(c) I presume we're looking for a program optimized for IA32 >architecture. The mersfac* programs are available but are unlikely to >be optimally efficient on any particular hardware platform. Optimized for IA32 would be beneficial (which processor architechure runs >80% of PCs?). If possible, the ability to modify so as to optimize for other architectures would be a plus, however. One big concern is speed though! >Given that, I suggest limits on exponent < 2^62 and on factor < 2^95 >(these are convenient for the architecture). After waking up several nights ago with some pretty *scary* thoughts, I realized a couple of things. As such, exponents through 2^62 should do fine. Anything that might be necessary above 4.6 x 10^18 could probably be extrapolated (not that I can think of any reason, currently, that would cause it to be necessary). Factors, however, would be slightly different. I suppose 2^95 would be acceptable for a base level (or default), especially if testing an entire bit depth (or a large range of factors). However, if testing a small and specific range of K, say K=2^143 to K=2^143+500, it might need to go considerable higher. I'm willing to make a few sacrifices for this to be possible... Admittedly, I'm not "in the loop" regarding the division of the massive numbers for which I'm talking. I'm sure somebody is, however (and maybe could explain it). >It's probably sensible to go for an application which runs in a "DOS >box" rather than a proper windowed application. This makes it a bit >easier (for me) to write & also makes deriving a linux variant almost >trivial. (Does anyone know for sure whether or not there's a DOS box >in "Millenium"? I heard a nasty rumour...) I heard the same nasty rumor... Actually, I've heard several, including ones about the floppy and Win16 support, among others. Eric _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Trial-factorers
> Well, I'm prepared to have a go. Could we tighten up the spec a bit? > > (a) There's also been some interest in something else that Prime95 > doesn't do - trial factoring 2^p+1. (Note that this form also form also has factors of the form k*p+1.) > (b) I assume we're only interested in 2kp+1 factors. This means that > we will miss any factors which are not of this form. (Applies to > Mersenne numbers with composite exponents, and all 2^p+1 numbers - > though I believe that the "missed" exponents are easy to derive > analytically.) Yes, those mersenne numbers with composite exponents have factors of the form 2^d-1 where d|p, but the remaining unfactored portion must have factors of the form k*p+1. (I believe that is Legendre's theorem) (or rather a consequence of it) > It's probably sensible to go for an application which runs in a "DOS > box" rather than a proper windowed application. This makes it a bit > easier (for me) to write & also makes deriving a linux variant almost > trivial. (Does anyone know for sure whether or not there's a DOS box > in "Millenium"? I heard a nasty rumour...) Egad! If true then it would be added to the long list of complaints I have with microsoft. > If we can agree on that, then I have a basis to begin coding. Will > certainly take a month or two to produce even a pre-pre-release as I > am very pushed for time at the moment. No need to rush, I wouldn't call the need for such a program urgent. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Trial-factorers
On 27 Oct 99, at 17:23, Eric Hahn wrote: > > I'm looking for program(s) capable of trial-factoring > prime exponent Mersenne numbers (using 2kp+1) meeting > the following requirements: > > 1) Capable of trial-factoring any exponent > 1 >(at least to some considerably large number, > say 1 trillion?) > > As I recall, Brian [Beesley] mentioned something once > about having a program that could test an exponent > of an arbitrary size... Brian?? Umm - I did write a "quick hack" which could handle exponents up to 1/6 * 2^32, but I never got round to putting a usable front end on it. Actually I thought that the release of the Prime95 v19 beta made it pretty redundant, and I was having a hard time with kidney stones. > > 2) Capable of testing a factor of any size. >(even over the 2^76 limit of Prime95). > > I just know somebody is going to have to mention the > time involved in testing factors of such a large size. > Let me just say, I realize *exactly* how much time > would be required... > > 3) Capable of trial-factoring a range of k's. >(example: from k=1000 to k=2500) Well, I'm prepared to have a go. Could we tighten up the spec a bit? (a) There's also been some interest in something else that Prime95 doesn't do - trial factoring 2^p+1. (b) I assume we're only interested in 2kp+1 factors. This means that we will miss any factors which are not of this form. (Applies to Mersenne numbers with composite exponents, and all 2^p+1 numbers - though I believe that the "missed" exponents are easy to derive analytically.) (c) I presume we're looking for a program optimized for IA32 architecture. The mersfac* programs are available but are unlikely to be optimally efficient on any particular hardware platform. Given that, I suggest limits on exponent < 2^62 and on factor < 2^95 (these are convenient for the architecture). It's probably sensible to go for an application which runs in a "DOS box" rather than a proper windowed application. This makes it a bit easier (for me) to write & also makes deriving a linux variant almost trivial. (Does anyone know for sure whether or not there's a DOS box in "Millenium"? I heard a nasty rumour...) If we can agree on that, then I have a basis to begin coding. Will certainly take a month or two to produce even a pre-pre-release as I am very pushed for time at the moment. Regards Brian Beesley _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Trial-factorers
Eric Hahn writes: I'm looking for program(s) capable of trial-factoring prime exponent Mersenne numbers (using 2kp+1) meeting the following requirements: 1) Capable of trial-factoring any exponent > 1 (at least to some considerably large number, say 1 trillion?) If your C compiler supports a 64 bit integer type, the mers package factorers mersfacgmp and mersfaclip can use that for the exponent, allowing exponents to about 2^64/24 (about 768 quadrillion, ~7e17). The '/24' can be reduced to '/2' by using a lower number of sieve passes. If you don't have a 64 bit integer type, then you're limited to 2^32/24 or so (about 178 million). See setup.h for the #define's of BIG_LONG. As I recall, Brian [Beesley] mentioned something once about having a program that could test an exponent of an arbitrary size... Brian?? The mersfac* code could be modified to allow arbitrary exponents without a lot of work, but it wouldn't be trivial to do either. I do intend on doing it someday, however, to support the factoring of the M(M(p))'s, as the sieving of trial factors in mmtrial is not as good as that in mersfac*. 2) Capable of testing a factor of any size. (even over the 2^76 limit of Prime95). Mersfacgmp and mersfaclip use the FSF's libgmp and A. Lenstra's freeLIP libraries, respectively, for the trial factors. 3) Capable of trial-factoring a range of k's. (example: from k=1000 to k=2500) As Alexander Kruppa noted, this is not supported directly, but could be done fairly easily with bc. And it could be added to mersfac* directly without a lot of effort; see rw.c where it reads the command line and the input file(s), especially the -m flag. The -a flag is probably also of interest; without it, mersfac* will stop when it finds a factor rather than looking for all the factors in a range. The simplest way to do it with bc would be to create 'G' (gap) lines like: M( )G: where '' is the exponent and '' and '' are the first and last trial factors to test. In any case, part of the output will be 'J' (join) lines, that show exactly what range of trial factors were actually tested; please include them in any output of mersfac* that you send to me. Will http://www.garlic.com/~wedgingt/mersenne.html mers.tar.gz mers.tgz mers.zip ` _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Trial-factorers
Eric Hahn wrote: > > I'm looking for program(s) capable of trial-factoring > prime exponent Mersenne numbers (using 2kp+1) meeting > the following requirements: > > [factors and exponents of arbitrary size] > mersfacgmp from the Will Edgingtons mers package uses gmp's mpz type for factors (thus the size of the factor is only limited by your available memory) and long ints for the exponent. If you have a 64 bit cpu, that should allow exponentes up to 18446744 trillion. > I just know somebody is going to have to mention the > time involved in testing factors of such a large size. > Let me just say, I realize *exactly* how much time > would be required... Ok, but know that gmp is not particulary efficient on "small" number of only a few dozend decimals, the time required might be what you expect and then some. > 3) Capable of trial-factoring a range of k's. >(example: from k=1000 to k=2500) Hmmm, I dont think mersfacgmp can process this directly, but it would be easy to compute the proper factoring limits with a shell script that calls bc. The mers package can be found on Will's home page, http://www.garlic.com/~wedgingt/mersenne.html Ciao, Alex. _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Trial-factorers
I'm looking for program(s) capable of trial-factoring prime exponent Mersenne numbers (using 2kp+1) meeting the following requirements: 1) Capable of trial-factoring any exponent > 1 (at least to some considerably large number, say 1 trillion?) As I recall, Brian [Beesley] mentioned something once about having a program that could test an exponent of an arbitrary size... Brian?? 2) Capable of testing a factor of any size. (even over the 2^76 limit of Prime95). I just know somebody is going to have to mention the time involved in testing factors of such a large size. Let me just say, I realize *exactly* how much time would be required... 3) Capable of trial-factoring a range of k's. (example: from k=1000 to k=2500) It would be best if all three of the requirements could be fulfilled by a single program... Can anybody be of some help??? Eric Hahn _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
