Go Back > Prime Search Projects > Prime Gap Searches

Thread Tools
Old 2021-09-23, 18:19   #56
Mar 2021

2×52 Posts

Originally Posted by Dr Sardonicus View Post
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.
CraigLo is online now   Reply With Quote
Old 2021-09-24, 02:22   #57
SethTro's Avatar
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
SethTro is offline   Reply With Quote
Old 2021-09-24, 06:10   #58
ATH's Avatar
Dec 2003

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 ?
ATH is online now   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Guess the next maximal prime gap. Bobby Jacobs Prime Gap Searches 6 2021-07-04 11:51
Gaps between maximal prime gaps Bobby Jacobs Prime Gap Searches 52 2020-08-22 15:20
Superprime gaps Bobby Jacobs Prime Gap Searches 5 2019-03-17 20:01
Top 50 gaps robert44444uk Prime Gap Searches 1 2018-07-10 20:50
Gaps and more gaps on <300 site 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.