Is the computationally most efficient way to find a prime number of a given (large) size to search either for a Mersenne prime (Lucas-Lehmer) or test random numbers with some other well-known general prime number test (probably slower than LL by only a constant factor)? (Consider trying to win the EFF Cooperative Computing Award.) Can this be proven?
A counterexample might be an easy-to-compute sequence that is significantly denser in primes than simply the integers filtered by sieving. Prove no such sequences exist.
No comments :
Post a Comment