On 12 Oct 99, at 15:30, Jukka Santala wrote:
> Is it just me, or does factoring smaller Mersenne numbers take
> propotionally much longer? I would expect M727 to be much faster than
> the 33M range to a fixed depth, yet the opposite _seems_ to be true.
Yes, it _does_ take _much_ longer.
The time to test one factor is proportional to the logarithm to base
2 of the exponent, rounded up to the next integer. So each trial
takes 10T for M727, but 25T for M33219281 - 2.5 times as long. But,
since factors of Mp are of the form 2kp+1, there are almost 50,000
times as many candidate factors of M727 in any given interval. So
trial factoring M727 over a given interval takes almost 20,000 times
as long as trial factoring M33219281 over the same interval.
Note - T above is fixed only for numbers which fit neatly into the
same number of words.
>
> Ofcourse, I can't be sure about this, because the real complaint I have
> is that factoring numbers to depths beyond the "default" seems nearly
> impossible. The manual factoring assignment seems like the only
> possibility to force these, yet it doesn't work like the normal
> factoring (Doing one bit depth at time) and is a pain on a dual-CPU
> machine. Is it possible we'd get a third parameter to the Factor=
> work-line specifying the intended depth for the factorization?
I guess it would be possible, but it might be a waste of time (in the
long run). The factoring depth limit for each range of has been
chosen carefully to balance the chance of finding a "small" factor
(this saving running a LL test), which increases only slowly (less
than linearly) with factoring depth, against the time spent trial
factoring, which increases exponentially (doubling with each extra
bit of factoring depth).
> Also,
> usually for some reason Prime95 seems to reject most (all?) Factor=
> statements I've tried, could we get some more detailed instructions on
> this?
Prime95 will kick out factoring assignments when it considers that
the exponent has already been factored far enough.
There are definitely exponents in the database which have been LL
tested (some even double-checked) but have not been trial factored as
deeply as v19 would do. Suggest you pull down the database files
nofactor.zip (which now needs a program called decomp.zip to decode
it) & lucasv.zip. Make a list of exponents which have been double-
checked & have been factored less than the v19 limits. Construct
Factor= lines for these exponents. Should keep your system busy for a
while!
If you do decide to do this, you're on your own - don't be surprised
if someone else does the same thing independently - there's no
mechanism for coordination to avoid wasted effort.
Of course, you could try ECM or P-1 factoring instead ... there is
some coordination in this area, & in any case there's so much work to
do that it's easy not to tread on anyone else's toes!
Regards
Brian Beesley
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
