Bailey-Pomeranian-Selfridge-Wagstaff test

Bailey-Pomeranz-Selfridge-Wagstaff-testen ( BPSW , BPSW ) er en probabilistisk primalitetstest , der afgør, om et tal er sammensat eller sandsynligvis primtal . Det er opkaldt efter dets opfindere - Robert Bailey, Karl Pomeranz , John Selfridge, Samuel Wagstaff.

Testen kombinerer Fermats test for stærk pseudosimplicitet med base 2 og Lukes test for stærk pseudosenkelhed . For Fermat- og Luke-testene er der separate lister over pseudoprimer, det vil sige sammensatte tal, der består primaalitetstesten. For eksempel er de første ti stærke pseudoprimer til Fermats base 2-forsøg:

De første ti pseudoprimer i Lucas-testen (med parametre ):

Testens styrke er, at der ikke er nogen kendte skæringspunkter mellem Fermats lister over pseudoprimer og Lucas' pseudoprimer. Der er grund til at tro, at der som regel er forskellige typer numre på disse lister. For eksempel har base-2 pseudoprimer en tendens til at falde ind i restklassen 1 modulo m for mange små m, mens Lucas pseudoprimer har tendens til at falde ind i restklassen −1 modulo [3] : §6 [4 ] :Tabel 2 & §5 . Som et resultat heraf er et tal, der består både den stærke Fermat-test og den stærke Luke-test, meget sandsynligt, at være prime.

Intet sammensat tal mindre end 2 64 (hvilket er omtrent lig med 1,845 10 19 ) består BPSV-testen [5] . Denne test kan således betragtes som en deterministisk primalitetstest for tal mindre end den angivne grænse. Der kendes heller ikke endnu noget sammensat tal, større end grænsen, som består testen.

I 1980 tilbød Pomeranz, Selfridge og Wagstaff en belønning på $30 til enhver, der kunne finde et modeksempel, det vil sige finde et sammensat tal, der bestod denne test. Richard Guy troede fejlagtigt, at belønningen var $620, men han blandede Luke- og Fibonacci-sekvenserne , og hans bemærkninger viste sig kun at gælde for én af Selfridges formodninger [6] . Fra juni 2014 er præmien ikke blevet gjort krav på. Pomeranz' heuristiske argument indikerer dog, at der er uendeligt mange sådanne modeksempler [7] . Derudover konstruerede Chen og Green [8] [9] et sæt S bestående af 1248 primtal, således at der blandt de 21248 produkter af forskellige primtal i S kan være omkring 740 modeksempler. De overvejede dog en svagere BPSV-test, der bruger Fibonacci-testen i stedet for Luke-testen.

Algoritme

Lad være  et ulige naturligt tal, der skal kontrolleres for prime.

1. Valgfri[ afklar ] gentag over primtal divisorer mindre end en given øvre grænse og kontroller, om tallet er et perfekt kvadrat. Hvis der findes en primfaktor, eller tallet er et perfekt kvadrat, er testen afsluttet - tallet er ikke primtal.
2. Udfør en stærk test for primeness i base 2. Hvis det ikke er stærkt sandsynligt prime i base 2, så er det sammensat; dette afslutter kontrollen.
3. Find den første i rækkefølgen 5, −7, 9, −11, 13, −15, ... hvor Jacobi-symbolet er −1. Lad os sætte og .
4. Kør Lukes stærke primalitetstest med . Hvis ikke stærkt sandsynligt primtal, så er det sammensat; dette afslutter kontrollen. Ellers med stor sandsynlighed er prime.

Kommentarer:

1. Den første fase øger kun effektiviteten. BPSV-testen fungerer uden dette trin, men hvis den har små prime divisorer, så er den hurtigste måde at vise, hvad der er sammensat, at finde sådan en divisor ved en række tests.
2. På anden fase anvendes Miller-Rabin-primalitetstesten én gang . Valget af base påvirker ikke effektiviteten af ​​en bestemt test. Men talrige undersøgelser har vist, at kombinationen af ​​en stærk base 2-primalitetstest og en stærk Luke-primalitetstest klarer sig godt i at teste tal for primalitet.
3. Bailey og Wagstaff beviste [4] , at det gennemsnitlige antal , der skal sorteres fra, er cirka 3,147755149.
4. Hvis er et perfekt kvadrat, så vil der i trin 3 aldrig være , sådan at ; dette vil dog ikke være et problem, da perfekte kvadrater let findes ved hjælp af Newtons kvadratrodsmetode. Hvis det ikke lykkes at finde trin 3 på kort tid, så tjek om det er en perfekt firkant.
5. For en given , er der andre metoder til at vælge koefficienter [4] :1401, 1409 . Det vigtige er, at Jacobi-symbolet skal være lig med −1. Bresson og Wagon beviste, at for at testen skal være effektiv, skal Jacobi-symbolet være lig med -1 og værdien af ​​[10] :266-269 .

Fejl ved brug af Fermats test adskilt fra Lukes test

Der er betydelig overlapning i listerne over pseudoprimer af forskellige årsager.

Hvis  er pseudoprime af en eller anden grund , så er det sandsynligvis pseudoprime af mange andre grunde [11] .

For eksempel pseudosimple til base 2. Bailey og Wagstaff beviste [4] , at der er 100 værdier (modulo 341), for hvilke 341 pseudosimple at basere . (De første ti af dem er: 1, 2, 4, 8, 15, 16, 23, 27, 29 og 30). Antallet af sådanne sammenlignet med normalt meget mindre.

Derfor, hvis  - pseudo-simple i form af , er der stor sandsynlighed for, at det er pseudo-simpelt i form af en anden årsag. For eksempel er der 21853 base 2 pseudoprimer fra 0 til 25· 109 . Dette er kun omkring to tal pr. million af alle de ulige tal i dette segment. Imidlertid:

• 4.709 af disse 21.853 tal (over 21 procent) er også pseudoprime i base 3; (og over alt 3 glatte baser )
• 2.522 af disse 4.709 tal (over 53 procent) er pseudoprime i base 2, 3 og 5; (og over alt 5 glatte baser )
• 1.770 af disse 2.522 tal (over 70 procent) er pseudoprime i base 2, 3, 5 og 7. (og i alle 7-glatte baser )

29341 er den mindste pseudoprime i base 2 til 10 (og i alle 7-glatte baser ). Dette indikerer, at probabilistiske primalitetstests ikke er uafhængige af forskellige årsager, så at køre en Fermat-test på flere og flere resultater vil luge ud færre og færre pseudoprimer hver gang. På den anden side tyder beregningerne op til 2 64 nævnt ovenfor på, at Fermat- og Luke-testene er uafhængige, så kombinationen af ​​disse tests er en kraftfuld primatitetstest, især når man bruger disse tests stærke former.

Der er også skæringspunkter mellem stærke pseudoprimer på forskellige grunde. For eksempel er 1373653 den mindste stærke pseudoprime i alle baser fra 2 til 4 (og i alt 3-glatte ), og 3215031751 er den mindste stærke pseudoprime i alle baser fra 2 til 10 (og i alt 7-glatte ). Arnold [12] præsenterer et 397-cifret sammensat tal N, som er stærkt pseudoprime i alle baser mindre end 307 (og i alle 293-glatte ). Da N er et Carmichael tal , vil N også være (ikke nødvendigvis stærkt) pseudo-primtal i alle baser mindre end p, hvor p er den mindste 131-cifrede primtal divisor af N. Samtidig viser en hurtig optælling, at N er ikke et pseudo-primtal Lucas-tal, hvis D, P, Q blev valgt ved metoden beskrevet ovenfor, så BPSV-testen vil afgøre, at dette tal er sammensat.

Anvendelser af en kombination af Fermat- og Luke-primalitetstestene

Følgende computersystemer og softwarepakker bruger forskellige versioner af BPEP-testen.

Funktionerne IsPrimei Maple [13] , Mathematica [14] , Sage [15] og funktioner og PrimeQi PARI/GP [ 16] bruger en kombination af Miller-Rabin-testen (stærk Fermat-test) og Luke-testen. En funktion i Maxima bruger en sådan test for tal større end 341550071728321 [17] . is_pseudoprimeisprimeispseudoprimePrimep

FLINT - biblioteket indeholder funktioner , der bruger den kombinerede test, samt andre funktioner, der bruger Fermat- og Luc-testene separat 18] . n_is_probabprimen_is_probabprime_BPSW

En klasse BigIntegeri standardversioner af Java og i open source-versioner såsom OpenJDK har en isProbablePrime. Denne metode udfører en eller flere Miller-Rabin-tests tilfældigt. Hvis antallet, der testes, er 100 eller flere bits, udfører denne metode også Luke-testen, som kontrollerer, at [19] [20] . Brugen af ​​tilfældige baser i Miller-Rabin-tests har både fordele og ulemper sammenlignet med kun at teste base 2, som i BPSV-testen. Fordelen ved at bruge tilfældige baser er, at man kan få et sandsynlighedsestimat på, at n er sammensat. Ulempen er, at det i modsætning til BPSV-testen ikke kan siges med sikkerhed, at hvis n er mindre end en fast binding, såsom 2 64 , så er n primtal.

I Perl indeholder modulerne Math::Primality[21] og Math::Prime::Util[22] [23] funktioner til at udføre den stærke BPSS-test, samt separate funktioner til den stærke pseudoprimalitetstest og den stærke Luke-test. Python -biblioteket NZMATH [24] indeholder en stærk pseudoprimalitetstest og en stærk Luke-test, men indeholder ikke en kombination af begge.

Funktionen mpz_probab_prime_pfra GNU Multiple Precision Arithmetic Library bruger Miller-Rabin-testen, men bruger ikke Luke-testen [25] . Funktionerne IsProbablePrimeog IsProbablyPrimefra Magma udfører 20 Miller-Rabin-tests for tal større end 34·10 13 , men bruger ikke deres kombination med Lucas-testen [26] .

Noter

1. ↑ OEIS -sekvens A001262 _
2. ↑ OEIS -sekvens A217255 _
3. ↑ Carl Pomerance ; John L. Selfridge ; Samuel S. Wagstaff, Jr.  Pseudoprimerne til 25 10 9  // Mathematics of Computation : journal. - 1980. - Juli ( bind 35 , nr. 151 ). - S. 1003-1026 . - doi : 10.1090/S0025-5718-1980-0572872-7 . Arkiveret fra originalen den 19. oktober 2014.
4. ↑ 1 2 3 4 Robert Baillie; Samuel Wagstaff . Lucas Pseudoprimes  // Mathematics of  Computation : journal. - 1980. - Oktober ( bind 35 , nr. 152 ). - S. 1391-1417 . - doi : 10.1090/S0025-5718-1980-0583518-6 . Arkiveret fra originalen den 4. marts 2016.
5. ↑ Baillie-PSW Primality Test (link utilgængeligt) . Thomas R. Pænt. Hentet 5. december 2015. Arkiveret fra originalen 28. august 2013. (ubestemt) 
6. ↑ Guy, R. (1994). "Pseudoprimer. Euler pseudoprimer. Stærke Pseudoprimer. §A12 i uløste problemer i talteori . 2. udg., s. 28, New York: Springer-Verlag. ISBN 0-387-20860-7 .
7. ↑ Pomerance, C. (1984), Are There Counterexamples to the Baillie-PSW Primality Test? , < http://www.pseudoprime.com/dopo.pdf > Arkiveret 4. marts 2016 på Wayback Machine 
8. ↑ Baillie-PSW Arkiveret 24. december 2015 på Wayback Machine John R. Greenes hjemmeside.
9. ↑ Zhuo Chen; John Greene. Nogle kommentarer til Baillie-PSW Pseudoprimes  //  The Fibonacci Quarterly : journal. - 2003. - August ( bind 41 , nr. 4 ). - S. 334-344 . Arkiveret fra originalen den 28. august 2011.
10. ↑ David Bressoud ; Stan WagonEt kursus i beregningsmæssig talteori  (ubestemt) . - New York: Key College Publishing i samarbejde med Springer, 2000. - ISBN 978-1-930190-10-8 .
11. ↑ Samuel S. Wagstaff, Jr. Pseudoprimer og en generalisering af Artins formodning  //  Acta Arithmetica : journal. - 1982. - Bd. 41 , nr. 2 . - S. 141-150 .
12. ↑ F. Arnault. Konstruktion af Carmichael-tal, som er stærke pseudoprimtal til flere baser  //  Journal of Symbolic Computation  : tidsskrift. - 1995. - August ( bind 20 , nr. 2 ). - S. 151-161 . - doi : 10.1006/jsco.1995.1042 . Arkiveret fra originalen den 1. december 2018.
13. ↑ isprime - Maple Hjælp Arkiveret 30. september 2012 i Wayback Machine -dokumentationen på maplesoft.com .
14. ↑ Nogle bemærkninger om intern implementering-Wolfram Mathematica 9-dokumentation Arkiveret 13. april 2014 på Wayback Machine wolfram.com-dokumentationen.
15. ↑ Sage Reference Manual Release 5.7 Arkiveret 18. januar 2013 i Wayback Machine Sage-dokumentationen.
16. ↑ Brugervejledning til PARI/GP (version 2.5.1) Arkiveret 4. marts 2016 på Wayback Machine PARI/GP-dokumentationen.
17. ↑ Maxima Manual Ver. 5.28.0 Arkiveret 9. juli 2014 Wayback Machine Maxima-dokumentation.
18. ↑ FLINT: Fast Library for Number Theory Arkiveret 8. december 2015 på Wayback Machine FLINT 2.3.0 dokumentation.
19. ↑ BigInteger.java Arkiveret 8. december 2015 på Wayback Machine DocJar: Search Open Source Java API.
20. ↑ BigInteger.java Arkiveret 8. december 2015 på Wayback Machine OpenJDK-dokumentationen.
21. ↑ Math::Primality Perl-modul med BPSV-test
22. ↑ Math::Prime::Util Arkiveret 3. september 2013 på Wayback Machine Perl-modulet med primalitetstest, inklusive BPSV
23. ↑ Math::Prime::Util::GMP Arkiveret 3. september 2013 på Wayback Machine Perl-modulet med primalitetstest, inklusive BPSV ved hjælp af C+GMP
24. ↑ NZMATH Arkiveret fra originalen den 17. januar 2013. system til at arbejde med problemer relateret til talteori i Python
25. ↑ Prime Testing Algorithm - GNU MP 5.1.1 Arkiveret 24. oktober 2015 på Wayback Machine GMPLIB-dokumentationen
26. ↑ Magma Computational Algebra System - Primes and Primality Testing Arkiveret 3. oktober 2015 på Wayback Machine Magma-dokumentationen.