20210923, 18:19  #56 
Mar 2021
2×5^{2} Posts 
Thanks. The goal is to check primality with a single Fermat test. The problem is handling pseudoprimes. If a number is a pseudoprime then there is some prime p that divides it. As you have shown, this pseudoprime has the form n == p (mod mp). If we remove all possible pseudoprimes by sieving for numbers of this form with primes up to sqrt(N) then I think a single Fermat test should be sufficient to test the remaining numbers.

20210924, 02:22  #57 
"Seth"
Apr 2019
550_{8} Posts 
Thinking through details out loud more time.
1. Sieve with small primes (<10K) marking off all numbers that are composite. 2. Perform Fermat (base 2) primality test The set of numbers that are composite after 1. and 2. are PSP(2), each N will have at least one factor p < sqrt(N) for which N % (p * ord2(p)) = p. 3. So we augment the first sieve by marking off mark off `i * (p * ord2(p)) + p` for large primes, up to sqrt(limit), this is faster than sieving with these numbers because ord2(p) ~ p. Any number that passes that would pass 2. (e.g. PSP(2)) has some factor p and we've marked off all multiples that would fail 2. so we should be good!  I tried to understand what the saving in runtime of sieving by p=10,000 vs sieving all primes and I got a counter intuitive result. From Mertens' 2nd theorem I believe the runtime to sieve number less than limit up to P is `limit * (0.577 + log(log(P))` When I evaluate this with limit=2^65 and P=10,000 vs limit=2^65 and P=2^32.5 2^65 * (0.577 + log(log(10,000)) = 4.3e19 2^65 * (0.577 + log(log(2^32.5)) = 5.7e19 It says it's only 30% harder to sieve all the numbers (at which point we can skip the Fermat test completely). Maybe this doesn't work in the real world because of cache behavior? Or because the sieve is segmented? Or am I missing something else? Last fiddled with by SethTro on 20210924 at 02:22 
20210924, 06:10  #58 
Einyen
Dec 2003
Denmark
3·5·211 Posts 
If n=p (mod p*ord(p)) then p*ord(p) < n even when p > sqrt(n), which I find a bit strange.
For example from the 2spsp list: 6589845341971 = 485131 * 13583641 ord(13583641) = 485130 and 485130*13583641 = 6589831758330 < 6589845341971 But ord(13583641) could have easily have been bigger, because often ord(p) = p1, but I guess every time p>sqrt(n) then ord(p) < p1, I guess that is why they are 2spsp ? 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Guess the next maximal prime gap.  Bobby Jacobs  Prime Gap Searches  6  20210704 11:51 
Gaps between maximal prime gaps  Bobby Jacobs  Prime Gap Searches  52  20200822 15:20 
Superprime gaps  Bobby Jacobs  Prime Gap Searches  5  20190317 20:01 
Top 50 gaps  robert44444uk  Prime Gap Searches  1  20180710 20:50 
Gaps and more gaps on <300 site  gd_barnes  Riesel Prime Search  11  20070627 04:12 