> Take 2 Mersenne numbers, m1 and m2 (m1 < m2).
> Do the usual LL series, but use as the modulus m1*m2.
> At the appropriate step, check if the remainder is
> divisible by m1. If so, then m1 is prime.
> At the end, check if the remainder is divisible by
> m2. If so, then m2 is prime.
> This allows us to do two (or more) tests for the price
> of one. What is the obvious reason we don't do this?
This would require more than double time.
Think about it like this:
Take two mersenne numbers 2^p-1, and 2^n-1 with p~=n
(For the purpose of clarity we will assume they are
close enough to be considered equal)
Now, an LL test requires O(p*(p*log(p))) time.
(~p multiplications of O(p*log(p)) time)
Hence the time required to perform them on
p and n is O(2*p^2*log(p)).
But, the test you suggest would be require
O(p*((2*p)*log(2*p)))=O(2*p^2*(log(p)+log(2)))
Thus, your suggestion adds on O(2*p^2*log(2)) time.
Hope that helps,
-Lucas Wiman
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
