Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Baillie–PSW_primality_test> ?p ?o }
Showing triples 1 to 61 of
61
with 100 triples per page.
- Baillie–PSW_primality_test abstract "The Baillie–PSW primality test is a probabilistic primality testing algorithm that determines if a number is composite or a probable prime. It is named after Robert Baillie, Carl Pomerance, John Selfridge, and Samuel Wagstaff.The Baillie-PSW test is a combination of a strong Fermat probable prime test to base 2 and a strong Lucas probable prime test.The Fermat and Lucas test each has its own list of pseudoprimes, that is, composite numbers that pass the primality test.For example, the first ten strong pseudoprimes to base 2 are 2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, and 52633 (sequence A001262 in OEIS).The first ten strong Lucas pseudoprimes (with Lucas parameters P = 1, Q = -1) are 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, and 58519 (sequence A217255 in OEIS).The power of the Baillie-PSW test comes from the fact that these lists of strong Fermat pseudoprimes and strong Lucas pseudoprimes have no known overlap.There is even evidence that the numbers in these lists tend to be different kinds of numbers.For example, pseudoprimes base 2 tend to fall into the residue class 1 (mod m) for many small m, whereas Lucas pseudoprimes tend to fall into the residue class −1 (mod m).As a result, a number that passes both a strong Fermat and a strong Lucas test is very likely to be prime.No composite number below 264 (approximately 1.845·1019) passes the Baillie-PSW test. Consequently, this can be considered a deterministic primality test on numbers below that bound. There are also no known composite numbers above that bound that pass the test.In 1980 the authors Pomerance, Selfridge, and Wagstaff offered $30 for the discovery of a counterexample, that is, a composite number that passed this test. Richard Guy incorrectly stated that the value of this prize had been raised to $620, but he was confusing the Lucas sequence with the Fibonacci sequence, and his remarks really apply only to a Conjecture of Selfridge's. As of June 2014 the prize remains unclaimed. However, a heuristic argument by Pomerance suggests that there are infinitely many counterexamples.Moreover, Chen and Greenehave constructed a set S of 1248 primes such that, among the nearly 21248products of distinct primes in S, there may be about 740 counterexamples. However, they are talking about a weaker Baillie-PSW test that substitutes a Fibonacci test for the Lucas one.".
- Baillie–PSW_primality_test wikiPageID "3609890".
- Baillie–PSW_primality_test wikiPageLength "15874".
- Baillie–PSW_primality_test wikiPageOutDegree "35".
- Baillie–PSW_primality_test wikiPageRevisionID "683574579".
- Baillie–PSW_primality_test wikiPageWikiLink Carl_Pomerance.
- Baillie–PSW_primality_test wikiPageWikiLink Carmichael_number.
- Baillie–PSW_primality_test wikiPageWikiLink Category:Primality_tests.
- Baillie–PSW_primality_test wikiPageWikiLink Composite_number.
- Baillie–PSW_primality_test wikiPageWikiLink Fast_Library_for_Number_Theory.
- Baillie–PSW_primality_test wikiPageWikiLink Fibonacci_number.
- Baillie–PSW_primality_test wikiPageWikiLink Fibonacci_sequence.
- Baillie–PSW_primality_test wikiPageWikiLink GNU_Multiple_Precision_Arithmetic_Library.
- Baillie–PSW_primality_test wikiPageWikiLink Jacobi_symbol.
- Baillie–PSW_primality_test wikiPageWikiLink Java_(software_platform).
- Baillie–PSW_primality_test wikiPageWikiLink John_Selfridge.
- Baillie–PSW_primality_test wikiPageWikiLink Lucas_pseudoprime.
- Baillie–PSW_primality_test wikiPageWikiLink Lucas_sequence.
- Baillie–PSW_primality_test wikiPageWikiLink Magma_(computer_algebra_system).
- Baillie–PSW_primality_test wikiPageWikiLink Magma_computer_algebra_system.
- Baillie–PSW_primality_test wikiPageWikiLink Maple_(software).
- Baillie–PSW_primality_test wikiPageWikiLink Mathematica.
- Baillie–PSW_primality_test wikiPageWikiLink Maxima_(software).
- Baillie–PSW_primality_test wikiPageWikiLink Miller-Rabin_primality_test.
- Baillie–PSW_primality_test wikiPageWikiLink Miller–Rabin_primality_test.
- Baillie–PSW_primality_test wikiPageWikiLink Newtons_method.
- Baillie–PSW_primality_test wikiPageWikiLink OpenJDK.
- Baillie–PSW_primality_test wikiPageWikiLink GP.
- Baillie–PSW_primality_test wikiPageWikiLink Perl.
- Baillie–PSW_primality_test wikiPageWikiLink Primality_test.
- Baillie–PSW_primality_test wikiPageWikiLink Prime_number.
- Baillie–PSW_primality_test wikiPageWikiLink Probable_prime.
- Baillie–PSW_primality_test wikiPageWikiLink Python_(programming_language).
- Baillie–PSW_primality_test wikiPageWikiLink Randomized_algorithm.
- Baillie–PSW_primality_test wikiPageWikiLink Richard_K._Guy.
- Baillie–PSW_primality_test wikiPageWikiLink SageMath.
- Baillie–PSW_primality_test wikiPageWikiLink Sage_(mathematics_software).
- Baillie–PSW_primality_test wikiPageWikiLink Samuel_S._Wagstaff,_Jr..
- Baillie–PSW_primality_test wikiPageWikiLink Samuel_Wagstaff.
- Baillie–PSW_primality_test wikiPageWikiLink Strong_pseudoprime.
- Baillie–PSW_primality_test wikiPageWikiLink Trial_division.
- Baillie–PSW_primality_test wikiPageWikiLinkText "Baillie–PSW primality test".
- Baillie–PSW_primality_test wikiPageWikiLinkText "Baillie–PSW".
- Baillie–PSW_primality_test hasPhotoCollection Baillie–PSW_primality_test.
- Baillie–PSW_primality_test title "Baillie-PSW Primality Test".
- Baillie–PSW_primality_test urlname "Baillie-PSWPrimalityTest".
- Baillie–PSW_primality_test wikiPageUsesTemplate Template:Citation.
- Baillie–PSW_primality_test wikiPageUsesTemplate Template:MathWorld.
- Baillie–PSW_primality_test wikiPageUsesTemplate Template:Number_theoretic_algorithms.
- Baillie–PSW_primality_test wikiPageUsesTemplate Template:OEIS.
- Baillie–PSW_primality_test wikiPageUsesTemplate Template:R.
- Baillie–PSW_primality_test wikiPageUsesTemplate Template:Reflist.
- Baillie–PSW_primality_test wikiPageUsesTemplate Template:Rp.
- Baillie–PSW_primality_test subject Category:Primality_tests.
- Baillie–PSW_primality_test comment "The Baillie–PSW primality test is a probabilistic primality testing algorithm that determines if a number is composite or a probable prime.".
- Baillie–PSW_primality_test label "Baillie–PSW primality test".
- Baillie–PSW_primality_test sameAs m.09prj4.
- Baillie–PSW_primality_test sameAs Q4848469.
- Baillie–PSW_primality_test sameAs Q4848469.
- Baillie–PSW_primality_test wasDerivedFrom Baillie–PSW_primality_test?oldid=683574579.
- Baillie–PSW_primality_test isPrimaryTopicOf Baillie–PSW_primality_test.