Silný pseudoprim

Stabilní verze byla zkontrolována 5. srpna 2022 . Existují neověřené změny v šablonách nebo .

Pravděpodobné prvočíslo je takové, které projde testem prvočíselnosti . Silné pravděpodobné prvočíslo je číslo, které projde silnou verzí testu primality. Silné pseudoprvočíslo je složené číslo , které projde silnou verzí testu primality.

Tímto testem projdou všechna prvočísla, ale malá část složených čísel tímto testem také projde, což z nich činí „ falešná prvočísla “.

Na rozdíl od Fermatových pseudoprvočísel , pro která existují čísla, která jsou pseudoprvočísla ve všech základech koprimých ( Carmichaelova čísla ), neexistují žádná složená čísla, která jsou silná pseudoprvočísla ve všech základech.

Formální definice

Formálně se liché složené číslo n = d • 2 s + 1 s lichým d nazývá silné pseudoprvo (Fermat) v bázi a, pokud platí jedna z následujících podmínek:

nebo

pro některé

(Pokud n splňuje výše uvedené podmínky a nevíme, zda je prvočíslo nebo ne, je přesnější ho nazývat silné pravděpodobně prvočíslo v základu a . Pokud víme, že n není prvočíslo, můžeme použít výraz silné pseudoprvo. )

Definice je triviální, pokud a ≡ ±1 mod n , takže tyto triviální případy jsou často vyloučeny.

Richard Guy chybně uvedl definici pouze s první podmínkou, ale ne všechna prvočísla ji splňují [1] .

Vlastnosti silných pseudoprimes

Silné pseudoprvo k základu a je vždy Eulerovo-Jacobiho pseudoprvo , Eulerovo pseudoprvo [2] a Fermatovo pseudoprvo k tomuto základu, ale ne všechna Eulerova a Fermatova pseudoprima jsou silná pseudoprima. Carmichaelova čísla mohou být silná pseudoprvá v některých základech, například 561 je silná pseudoprvá v základu 50, ale ne ve všech základech.

Složené číslo n je silné pseudoprvo pro nejvýše čtvrtinu všech bází menších než n [3] [4] . Neexistují tedy žádná „silná Carmichaelova čísla“, čísla, která jsou silnými pseudoprimy pro všechny základy. Proto, daný náhodný základ, pravděpodobnost, že číslo je silné pseudoprime v tomto základu, nepřekročí 1/4, který je používán v široce používaném Miller-Rabin testu . Arnaud [5] však přiřadil 397místné složené číslo, které je silné pseudoprvojakémukoli základu menšímu než 307. Jedním ze způsobů, jak se vyhnout prohlášení takových čísel za pravděpodobná prvočísla, je zkombinovat test silných možných prvočísel s Lucasovým pseudoprvočíslem . v testu Bailey-Pomeranz-Selfridge-Wagstaff .

Existuje nekonečně mnoho silných pseudoprimes pro nějakou konkrétní bázi [2] .

Příklady

První silné pseudoprimery k základně 2

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85452, 89836, sekvence A2551 , 8017 ).

Základ 3

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621 , 44281 OEIS ).

Základ 5

781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 40501, 44801, 57937 A1 ( sekvence A1IS21 , 57937 ).

Pro bázi 4 viz A020230 a pro báze 6 až 100 viz sekvence A020232 až A020326 .

Testování výše uvedených podmínek proti více bázím má za následek výkonnější test primality než použití testu s jedinou bází. Například existuje pouze 13 čísel menších než 25•10 9 , která jsou současně silnými pseudoprvočísly k základům 2, 3 a 5. Jsou uvedeny v tabulce 7 v Pomerance and Selfridge [2] . Nejmenší takové číslo je 25326001. To znamená, že pro n menší než 25326001, je-li n silné možné prvočíslo v základech 2, 3 a 5, pak n je prvočíslo.

Číslo 3825123056546413051 je nejmenší číslo, které je zároveň silné pseudoprvo v 9 bázích 2, 3, 5, 7, 11, 13, 17, 19 a 23 [6] [7] . Takže pro n menší než 3825123056546413051, pokud n je silné pravděpodobné prvočíslo z těchto 9 důvodů, pak n je prvočíslo.

Pečlivým výběrem základny, která není prvotřídní, lze zkonstruovat ještě lepší testy. Například neexistují žádná složená čísla , která jsou silnými pseudoprvočísly ve všech sedmi základech 2, 325, 9375, 28178, 450775, 9780504 a 1795265022 [8] .

Nejmenší silné pseudoprvo k základu n

n Nejméně n Nejméně n Nejméně n Nejméně
jeden 9 33 545 65 33 97 49
2 2047 34 33 66 65 98 9
3 121 35 9 67 33 99 25
čtyři 341 36 35 68 25 100 9
5 781 37 9 69 35 101 25
6 217 38 39 70 69 102 133
7 25 39 133 71 9 103 51
osm 9 40 39 72 85 104 patnáct
9 91 41 21 73 9 105 451
deset 9 42 451 74 patnáct 106 patnáct
jedenáct 133 43 21 75 91 107 9
12 91 44 9 76 patnáct 108 91
13 85 45 481 77 39 109 9
čtrnáct patnáct 46 9 78 77 110 111
patnáct 1687 47 65 79 39 111 55
16 patnáct 48 49 80 9 112 65
17 9 49 25 81 91 113 57
osmnáct 25 padesáti 49 82 9 114 115
19 9 51 25 83 21 115 57
dvacet 21 52 51 84 85 116 9
21 221 53 9 85 21 117 49
22 21 54 55 86 85 118 9
23 169 55 9 87 247 119 patnáct
24 25 56 55 88 87 120 91
25 217 57 25 89 9 121 patnáct
26 9 58 57 90 91 122 65
27 121 59 patnáct 91 9 123 85
28 9 60 481 92 91 124 25
29 patnáct 61 patnáct 93 25 125 9
třicet 49 62 9 94 93 126 25
31 patnáct 63 529 95 1891 127 9
32 25 64 9 96 95 128 49

Poznámky

  1. ↑ Chlap, 1994 , str. 27-30.
  2. ↑ 1 2 3 Pomerance, Selfridge, Wagstaff, 1980 , str. 1003–1026.
  3. ↑ Monier, 1980 , str. 97-108.
  4. ↑ Rabin, 1980 , str. 128-138.
  5. ↑ Arnault, 1995 , s. 151–161.
  6. ↑ Zhang, Tang, 2003 , str. 2085–2097
  7. ↑ Yupeng Jiang, Yingpu Deng (2012), Silná pseudoprimes k prvním 9 prvočíslům, arΧiv : 1207.0063v1 [math.NT]. 
  8. ↑ Záznamy SPRP . Získáno 3. června 2015. Archivováno z originálu 11. října 2015.

Literatura