Re: Mersenne: Re : Odd's on finding a factor (part 2)
Thus for the exponent 1165 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 1164 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=1165 (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^58250002^sqrt(1165)~=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
Mersenne: Re: Odd's on finding a factor (part 2)
Dave Mullin wrote: 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. Ubasic can indeed handle integers up to around 2600 digits, but modpow() needs to hold intermediate results, so will only work up to around 1300 digits input. Good luck anyway! Andy Steward _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Re : Odd's on finding a factor (part 2)
Sorry, I'm no mathematician, and new to the Mersenne field. No, in the x-y bit range (remember that n bit integers are about 2^n) thefirst factor could be x/2 to y/2 bits long (powers of a power multiply). What I was trying to say in my disjointed way was ... (Example) M11 = 2047 (11 bits long). Now 2047 has only 2 factors (23 x 89) and the square root of 2047 is approx 45. 45 is 6 bits long, therefore the factor lower than the square root must have = 6 bits, and the factor higher than the square root must have =6 bits. 23 is 5 bits long, and 89 is 7 bits long. Thus for the exponent 1165 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 1164 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) !! Abreviate! Use scientific notation... Ooops. Why are you only setting k==1 mod 2^16?(I'm probably missing something obvious) Yes, my failure to express myself properly - I meant I test each exponent with all k multipliers in the range 1 to 2^16. I think under windows that dos windows only run when they are up. Under Win 98, they chug along quite happily in the background, unless you're running some other DOS box in Full Screen mode (I think). You would probably get better results with Will Edgington's mersfacgmpprogram, 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.
