> Thus for the exponent 11650000 bits long, if it only has 2 factors , then the first
>factor must be between 2 and 3413 bits long, and the second factor must be between
>3413 and 11649999 bits long. Note that the bit lengths of the 2 factors added
>together must equal the bit length of the Prime (or bit length of the Prime + 1) !!
No, if the exponent=11650000 (I think this is what you mean), the mersenne
number must be this number of bits (as you know). The first factor must
be less than sqrt(M_p), not M_(sqrt(p)), which is what you were doing. The
first factor must therefore be less than 2^(p/2)=2^5825000>2^sqrt(11650000)~=2^3413.
> > You would probably get better results with Will Edgington's mersfacgmp
> program, and DJGPP (a port of g++ to dos).
>
> I'll check it out. I'm using UBASIC because for testing factors of large Mersenne, I
>don't need to actually represent the full Mersenne Prime. If you're familiar with
>UBASIC try ...
>
> Result = MODPOW(2,MersenneExponent,TrialFactor)
>
> where TrialFactor is the MersenneExponent * 2 * (some k in range 1 to 2^16) + 1.
>
> If Result = 1 then TrialFactor divides the Mersenne Prime. As UBASIC can handle
>around 2600 decimal digits, in theory (and with a lot of time), I could check all
>factors up to 2600 decimal digits for any given exponent. It's a damn sight faster
>than filling 16MB+ of memory with 1's and then trial dividing.
Will's program does this also (see Knuth volume II (I think 4.5.3, but I'm
not sure don't have my copy handy), or the mersenne FAQ at the bottom of this
message). Thinking on it in a slightly more awake state, I'm not sure how much
faster it would be, but try it anyway. You will need to download DJGPP (search
altavista for DJGPP), set it up, compile the GMP library
(ftp://metalab.unc.edu/gnu/gmp (I think), there is a dos batch file), and compile
Will's program
(I think it is in the links section of the mailling list FAQ). But, under
windows, would George's program be the fastest (or are you using very large
exponents?)
Have fun,
Lucas Wiman
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
