On 19 Jul 99, at 22:21, David M Einstein wrote:
> You will want to do P-1 in addition to, and after seiving. It would be
> foolish to use p-1 to discover a 30 bit factor.
Not half - trial factoring with numbers that small, and _very_
heavily constrained, is _extremely_ fast. I tested 159,975 exponents
(the prime numbers between 33219278 and 36000000) for factors up to
2^32 in less than 20 seconds on a PII-350.
> If you are doing stage
> 1 only I believe that I had looked at a b1 of at least 100K which would
> translate to about 140K (I'm trusting your numbers) squarings. I think
> that that is still less than 5% of the number of squarings for a current
> LL test, and would reap factors for about 5% of the numbers so would at
> least break even.
Interesting ...
There is obviously a breakeven point between trial factoring (which
will _definitely_ find any factors up to the limit specified) and P-1
(which might not). So, are we in any sort of position to estimate
where that breakeven point might be, for exponents say around 10
million? What about smaller exponents, say around 5 million, which
have (mostly) already been LL tested but haven't been double checked
yet? (Finding a factor saves running the double check)
The fact that we would still be running trial factoring up to some
limit (though maybe a little lower than we are at present) would to
some extent remove the objection that an exhaustive search of at
least part of the range of possible factors is useful.
There is going to be another breakeven point between P-1 factoring
and LL testing - if we run a LL test, then (barring accidents) we get
a definitive result in a predictable time, whereas we could run P-1
"for ever" on even quite a small exponent without arriving at a
definite result.
>
> Not exactly. With a reasonable B1 I doubt that it would be the most
> time consuming part, but a straight euclidean or lehmer algorithm would
> be quite slow. A divide and conquer algorithm would be much faster, but
> extremely memory hungry (Violating GIMPS's unstated (but very positive)
> invisibility constraint (No noticable effect on the host systems
> operation).
Can we speculate on approximately how much memory would be needed, as
a design exercise? In any case, it needn't rule the scheme out
altogether if we find that some systems aren't able to contribute
usefully by reason of limited memory. After all, not all systems can
contribute usefully to some other tasks, e.g. it's a bit pointless to
try to run a LL test on a 7 million range exponent on a 486, though
the program _will_ try, if you ask it to!
> I believe that one of the reasons that the next version of
> prime95 will contain a straight FFT multiply is to support a divide and
> conquer GCD, but that is supposition on my part.
I thought maybe it was something to do with making more efficient use
of the L2 cache by keeping FFT data size reasonable & using a
recursive method to break large numbers down into small operations
that would "fit". Implementing this would require a general m * n bit
multiprecision multiplication function.
> I think that a P-1 would probably be neccessary. There may be enough
> room for ECM to have overcome P-1's free factor of P, but I dont think
> so.
ECM actually has a moderate memory load even for small exponents, you
need to keep _lots_ of n bit work vectors lying about. Though you
don't need to access all of them all that often, so it doesn't hurt
_too_ badly if some of them are forced out to a paging file. c.f. LL
test becomes _impossibly_ slow if you run out of physical memory &
the system starts paging on you.
I wonder if we already have the data we need to make some of the
estimates I've indicated above, or whether someone will have to go &
try to make them - &, if so, whether we actually need to code
anything, or whether it would be possible to use George's existing
P-1 factoring program to make them.
Regards
Brian Beesley
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
