Re: Mersenne: RE: Factoring more

[Lucas Wiman]

 Numbers above   are factored to
 -   ---
 71002^72
 57022^71
 44152^70
 35102^69
 28132^68
 21592^67
 17852^66
 13382^65
 825 2^64

Isn't this the "optimal" configuration if all computers in GIMPS
were identical?

There are a number of 486's that are doing only factoring, does
it take these into account?  Think about it, there are a number of
computers which should be factoring numbers faster than LL
tests can be performed.  Call this "factoring profit."  Wouldn't
it make sense to keep factoring profit as low as possible, as this
could speed up the more immediate consern of sooner-to-be-performed
LL tests?

As an example, I just recieved the factoring assignment of 10258511,
but I should think that we wouldn't even start these tests for some time.
Why not go back and factor some 8M exponents further so as to save a
few current LL tests?  Wouldn't this actually get us to the next prime
quicker?

Or do I need to get more sleep :)?

-Lucas
_
Unsubscribe  list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ  -- http://www.tasam.com/~lrwiman/FAQ-mers

Mersenne: RE: Factoring more

[George Woltman]

Hi,

At 09:05 AM 8/5/99 -0700, Eric Hahn wrote:

I think as the time increases for each LL test, there
would be much more time savings in attempting to do
higher trial-factoring.

In version 19, now being QA'ed, prime95 will factor as follows:

Numbers above   are factored to
-   ---
71002^72
57022^71
44152^70
35102^69
28132^68
21592^67
17852^66
13382^65
825 2^64

Note the new lower limit for 2^64 factoring.  Previously, prime95
balanced the "chance of finding a factor" times "cost of factoring"
against the "cost of one LL test".   Prime95 now balances this against
the cost of two LL tests.

What's coming in version 20:

1) Optimized factoring above 2^64.  The present factoring code is not
optimized.  This will lower factoring limits even further.
2) P-1 factoring.  I already know that P-1 factoring will be beneficial
for exponents above 10 million or so.  This means there will be a new
work type!  I need to optimize the P-1 code further and implement a
faster GCD.

Extra credit:  Can someone tell me the probability that P-1 factoring
will find an n-bit factor?  This is but one piece of the puzzle in
determining the best trial factoring limits and P-1 bounds.  To compute
this probability the k in the 2kp+1 factor must be "smooth", that is
all factors must be less than bound #1 except for one factor that
must be less than bound #2.  I'm sure I have the info around here somewhere,
but everyone might be interested in the math behind deriving trial factoring
limits and P-1 bounds. 

Regards,
George

_
Unsubscribe  list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ  -- http://www.tasam.com/~lrwiman/FAQ-mers