Two questions about prime numbers

Primes, divisors, arithmetic, number properties, ...
Post Reply
haroldgparker
Posts: 9
Joined: Sat Apr 24, 2021 1:19 am

Two questions about prime numbers

Post by haroldgparker »

(1) Consider the Lucas primality test (https://en.wikipedia.org/wiki/Lucas_primality_test). If applied to a Carmichael number, is it the case that the test is worst-case O(n)? It seems to me that it is, but I wanted to be sure.

(2) I've been trying to improve my generic isPrime method. Right now it's trial division below a certain bound, and Miller-Rabin with preselected bases otherwise. However, is there some range of numbers for which the Fermat primality test is the fastest option?
Post Reply