Friday, December 23, 2016

[ehitzrcs] Prime generating sequence

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 :