Talk:Lucas primality test
Appearance
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
[edit]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
[edit]Regarding 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)
Start a discussion about improving the Lucas primality test page
Talk pages are where people discuss how to make content on Wikipedia the best that it can be. You can use this page to start a discussion with others about how to improve the "Lucas primality test" page.