View Single Post
Old 2021-09-23, 18:19   #56
Mar 2021

59 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 offline   Reply With Quote