Talk:Lucas primality test
Latest comment: 2 years ago by 50.34.32.46 in topic Curious about generalizations
 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
|
This page has archives. Sections older than 365 days may be automatically archived by Lowercase sigmabot III when more than 3 sections are present. |
Similarity to the Pratt's ceritificate
editAm 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
editRegarding the primes q that divides n-1. I have two questions on generalizability of this method.
- 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.
- 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)