mersenneforum.org New Maximal Gaps
 Register FAQ Search Today's Posts Mark Forums Read

2021-09-23, 18:19   #56
CraigLo

Mar 2021

2×52 Posts

Quote:
 Originally Posted by Dr Sardonicus I don't know about the approach in its entirety, but I can confirm the congruence.
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.

 2021-09-24, 02:22 #57 SethTro     "Seth" Apr 2019 5508 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 2021-09-24 at 02:22
 2021-09-24, 06:10 #58 ATH 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 2-spsp 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) = p-1, but I guess every time p>sqrt(n) then ord(p) < p-1, I guess that is why they are 2-spsp ?

 Similar Threads Thread Thread Starter Forum Replies Last Post Bobby Jacobs Prime Gap Searches 6 2021-07-04 11:51 Bobby Jacobs Prime Gap Searches 52 2020-08-22 15:20 Bobby Jacobs Prime Gap Searches 5 2019-03-17 20:01 robert44444uk Prime Gap Searches 1 2018-07-10 20:50 gd_barnes Riesel Prime Search 11 2007-06-27 04:12

All times are UTC. The time now is 06:27.

Fri Sep 24 06:27:11 UTC 2021 up 63 days, 56 mins, 0 users, load averages: 1.64, 1.82, 1.63