Talk:Lucas primality test

Similarity to the Pratt's ceritificate

Am I the only man to notice that this test is VERY similar to the Pratt's certificate?! 89.176.110.147 (talk) 21:04, 16 March 2008 (UTC)

Uh, I do believe Pratts certificate is based on Lucas' primality test. More broadly, a Pratt certificate is any statement that can be used to verify the compositeness or primality of a number, deterministically, and in polynomial time. — Preceding unsigned comment added by 50.34.32.46 (talk) 15:32, 24 July 2022 (UTC)

Curious about generalizations

Regarding the primes q that divides n-1. I have two questions on generalizability of this method.

1. In practice does q necessarily have to be prime? Do we gain any value employing Lucas' test knowing only that q is a probable prime? Or are we wasting our time? If we know all the q's are either prime or probable primes (Fermat or Miller-Rabin), does this add confidence to our results? I accept that this would make Lucas a probabilistic test, but Im curious if its significantly stronger or weaker than a series of Miller Rabin tests. What if its run in conjunction with Miller Rabin? Suppose n was a M-R strong probable prime, and I then run Lucas, finding a base a and a series of prime and (Fermat or MR) probable primes q that passes Lucas. Never mind computational expense, Im curious about the strength of the condition.
2. In practice do we have to run "ALL" the q values? I understand the theorem statement just fine; I know it HAS to pass all in order to give deterministic results. But suppose Id be happy, again, reducing Lucas to a probabilistic primality test. Suppose I cant factor n-1 all the way, but have a fairly large list of factors nonetheless. Do I get probabilistic results passing the Lucas with the prime factors I DO have? — Preceding unsigned comment added by 50.34.32.46 (talk) 15:49, 24 July 2022 (UTC)