| rdfs:comment
| - El test de primalidad de Baillie-PSW es una prueba que emplea un algoritmo probabilístico que determina si un número es compuesto o probable primo. Lleva el nombre de Robert Baillie, Carl Pomerance, John Selfridge y Samuel S. Wagstaff, Jr.. Es una combinación de una prueba de probable primo de Fermat fuerte de base 2 y una prueba de probable primo de Lucas fuerte. (es)
- 베일리-PSW 소수판별법은 어떤 수가 소수인지 합성수인지를 확인할 수 있는 확률론적 알고리즘이다. (ko)
- Der Baillie-PSW-Primzahltest (benannt nach , PSW steht für die Co-Autoren Carl Pomerance, John Selfridge und Samuel Wagstaff) ist ein effizienter, heuristischer Test, um zu bestimmen, ob eine natürliche Zahl prim ist. Es handelt sich um keine eigene Kategorie von Test, sondern stattdessen um eine Kombination des Miller-Rabin-Tests zur Basis 2 mit einem starken Primzahltest auf Basis einer Lucas-Folge, deren Parameter nach einem Algorithmus von John Selfridge bestimmt werden (für die zu testende Zahl ): (de)
- The Baillie–PSW primality test is a probabilistic primality testing algorithm that determines whether a number is composite or is 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 have their own list of pseudoprimes, that is, composite numbers that pass the test. For example, the first ten strong pseudoprimes to base 2 are (en)
- Тест Бейли — Померанца — Селфриджа — Уогстаффа (БПСВ, BPSW) — вероятностный алгоритм проверки на простоту, который определяет, является число составным или вероятно простым. Назван по фамилиям его изобретателей — Роберта Бэйли, Карла Померанца, Джона Селфриджа, Сэмюэля Вагстаффа. 2047, 3277, 4033, 4681, 8321, 15 841, 29 341, 42 799, 49 141 и 52 633 Первые десять псевдопростых чисел теста Люка (с параметрами ): 5459, 5777, 10 877, 16 109, 18 971, 22 499, 24 569, 25 199, 40 309 и 58 519. (ru)
|
| has abstract
| - The Baillie–PSW primality test is a probabilistic primality testing algorithm that determines whether a number is composite or is 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 have their own list of pseudoprimes, that is, composite numbers that pass the test. For example, the first ten strong pseudoprimes to base 2 are 2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, and 52633 (sequence in the OEIS). The first ten strong Lucas pseudoprimes (with Lucas parameters (P, Q) defined by Selfridge's Method A) are 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, and 58519 (sequence in the OEIS). There is no known overlap between these lists of strong Fermat pseudoprimes and strong Lucas pseudoprimes, and there is even evidence that the numbers in these lists tend to be different kinds of numbers. For example, Fermat pseudoprimes to 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 test is a deterministic primality test on numbers below that bound. There are also no known composite numbers above that bound that pass the test, in other words, there are no known Baillie–PSW pseudoprimes. Despite this, there are conjectured to be infinitely many. 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 21248 products of distinct primes in S, there may be about 740 counterexamples. However, they are talking about the weaker PSW test that substitutes a Fibonacci test for the Lucas one. (en)
- El test de primalidad de Baillie-PSW es una prueba que emplea un algoritmo probabilístico que determina si un número es compuesto o probable primo. Lleva el nombre de Robert Baillie, Carl Pomerance, John Selfridge y Samuel S. Wagstaff, Jr.. Es una combinación de una prueba de probable primo de Fermat fuerte de base 2 y una prueba de probable primo de Lucas fuerte. (es)
- Der Baillie-PSW-Primzahltest (benannt nach , PSW steht für die Co-Autoren Carl Pomerance, John Selfridge und Samuel Wagstaff) ist ein effizienter, heuristischer Test, um zu bestimmen, ob eine natürliche Zahl prim ist. Es handelt sich um keine eigene Kategorie von Test, sondern stattdessen um eine Kombination des Miller-Rabin-Tests zur Basis 2 mit einem starken Primzahltest auf Basis einer Lucas-Folge, deren Parameter nach einem Algorithmus von John Selfridge bestimmt werden (für die zu testende Zahl ): 1.
* Bestimme das erste in der Folge 5, -7, 9, -11, …, so dass (Jacobi-Symbol). 2.
* Setze und (Parameter für die Lucas-Folge, siehe dort). Bei der Implementierung sollte beachtet werden, dass kein solches existiert, falls eine Quadratzahl ist. Schlägt die Suche also wiederholt fehl, muss zunächst durch Ziehen der Quadratwurzel von geprüft werden, ob dies der Fall ist. Außerdem sind gewisse Optimierungen möglich, z. B. muss nicht geprüft werden, da 9 selbst eine Quadratzahl ist, und das Jacobi-Symbol deswegen nur 0 oder 1 sein kann. Beide Einzeltests haben viele bekannte Pseudoprimzahlen, jedoch wurde bisher keine zusammengesetzte Zahl veröffentlicht, die beide Einzeltests gleichzeitig besteht. Speziell wurde auch anhand einer kompletten, computergenerierten Liste der Fermatsche Pseudoprimzahlen zur Basis 2 (eine Obermenge der Miller-Rabin-Pseudoprimzahlen zur gleichen Basis) bis verifiziert, dass der Baillie-PSW-Test bis mindestens zu dieser Grenze frei von Pseudoprimzahlen ist. Auf das Auffinden einer Pseudoprimzahl, die bestimmte zusätzliche Bedingungen erfüllt, ist eine Belohnung mehrerer Autoren von insgesamt 620 Dollar ausgesetzt, ebenso wie für den Beweis, dass keine Pseudoprimzahlen existieren. Jedoch gibt es ein heuristisches Argument von Pomerance selbst, nach dem der Test unendlich viele Pseudoprimzahlen habe. Der Baillie-PSW-Test ist heuristisch, da nicht bewiesen ist, dass es für ihn keine Pseudoprimzahlen gibt. Er sollte nicht mit einem probabilistischen Test verwechselt werden, da die Parameterauswahl fest vorgegeben und nicht zufällig ist, und eine Wiederholung mit anderen Parametern zur Erhöhung der Konfidenz ebenfalls nicht vorgesehen ist – auch wenn eine solche Wiederholung relativ leicht umzusetzen ist. (de)
- 베일리-PSW 소수판별법은 어떤 수가 소수인지 합성수인지를 확인할 수 있는 확률론적 알고리즘이다. (ko)
- Тест Бейли — Померанца — Селфриджа — Уогстаффа (БПСВ, BPSW) — вероятностный алгоритм проверки на простоту, который определяет, является число составным или вероятно простым. Назван по фамилиям его изобретателей — Роберта Бэйли, Карла Померанца, Джона Селфриджа, Сэмюэля Вагстаффа. Тест сочетает тест Ферма на сильную псевдопростоту по основанию 2 и тест Люка на сильную псевдопростоту. Для тестов Ферма и Люка существуют отдельные списки псевдопростых чисел, то есть составных чисел, которые проходят испытание на простоту. Например, первые десять сильных псевдопростых чисел для испытания Ферма по основанию 2: 2047, 3277, 4033, 4681, 8321, 15 841, 29 341, 42 799, 49 141 и 52 633 Первые десять псевдопростых чисел теста Люка (с параметрами ): 5459, 5777, 10 877, 16 109, 18 971, 22 499, 24 569, 25 199, 40 309 и 58 519. Мощность теста состоит в том, что не существует известных пересечений списков псевдопростых чисел Ферма и псевдопростых чисел Люка. Существуют основания полагать, что в эти списки попадают, как правило, различные типы чисел. Например, псевдопростые по основанию 2, как правило, попадают в класс вычетов 1 по модулю m для многих малых m, в то время как псевдопростые числа Люка, как правило, попадают в класс вычетов −1 по модулю .В результате число, которое проходит как сильный тест Ферма, так и сильное испытание Люка, с большой вероятностью будет простым. Ни одно составное число, меньшее 264 (что примерно равно 1,845 · 1019), не проходит тест БПСВ. Таким образом, этот тест можно считать детерминированным тестом простоты для чисел, меньших указанной границы. Также пока не известно ни одно составное число, большее границы, которое проходит тест. В 1980 году Померанц, Селфридж и Вагстафф предложили вознаграждение в размере $30 тому, кто отыщет контрпример, то есть найдет составное число, которое проходит этот тест. Ричард Гай ошибочно полагал, что размер вознаграждения составляет $620, но он перепутал последовательности Люка и Фибоначчи, и его замечания оказались применимы лишь к одной гипотезе Селфриджа. По состоянию на июнь 2014 года приз так и не был востребован. Тем не менее, эвристический аргумент Померанца указывает на то, что таких контрпримеров существует бесконечно много. Кроме того, Чен и Грин построили множество S, состоящее из 1248 таких простых чисел, что среди 21248 произведений различных простых чисел из S может быть около 740 контрпримеров. Однако, они рассматривали более слабый БПСВ-тест, который вместо теста Люка использует тест Фибоначчи. (ru)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)