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
------------- ---------------
71000000 2^72
57020000 2^71
44150000 2^70
35100000 2^69
28130000 2^68
21590000 2^67
17850000 2^66
13380000 2^65
8250000 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
