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) the
first 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 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) !!
> 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 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.
|
- Re: Mersenne: Re : Odd's on finding a factor (part 2) Dave Mullen
- Re: Mersenne: Re : Odd's on finding a factor (part 2) Lucas Wiman
- Mersenne: Re: Odd's on finding a factor (part 2) Andy Steward