Erős pszeudoprím

A stabil verziót 2022. augusztus 5-én nézték meg . Ellenőrizetlen változtatások vannak a sablonokban vagy a .

Valószínű prímszám az, amelyik megfelel a primalitásteszten . Az erős valószínűségi prím olyan szám, amely megfelel az elsődlegességi teszt erős változatának. Az erős pszeudoprím olyan összetett szám , amely megfelel az elsődlegességi teszt erős változatának.

Minden prímszám átmegy ezen a teszten, de az összetett számok egy kis része is átmegy ezen a teszten, így " hamis prímek " lesznek.

Ellentétben a Fermat-álprímekkel , amelyeknél vannak olyan számok, amelyek minden koprímbázisban álprímek ( Carmichael -számok ), nincsenek olyan összetett számok, amelyek minden bázisban erős pszeudoprímek.

Formális definíció

Formálisan egy páratlan összetett számot n = d • 2 s + 1 páratlan d -vel erős pszeudoprímnek (Fermat) nevezünk az a bázisban , ha az alábbi feltételek egyike teljesül:

vagy

néhány

(Ha n teljesíti a fenti feltételeket, és nem tudjuk, hogy prím-e vagy sem, akkor pontosabb erős valószínűleg prímnek nevezni az a bázisban . Ha tudjuk, hogy n nem prím, használhatjuk az erős pszeudoprím kifejezést. )

A definíció triviális, ha a ≡ ±1 mod n , ezért ezek a triviális esetek gyakran kizártak.

Richard Guy hibásan csak az első feltétellel adta meg a definíciót, de nem minden prímszám felel meg [1] .

Az erős pszeudoprímek tulajdonságai

Egy erős pszeudoprím a bázishoz mindig egy Euler -Jacobi pszeudoprím , Euler pszeudoprím [2] , és egy Fermat pszeudoprím ehhez az alaphoz, de nem minden Euler és Fermat pszeudoprím erős pszeudoprím. A Carmichael-számok bizonyos bázisokban erős pszeudoprímek lehetnek , például az 561 erős pszeudoprím az 50-es bázisban, de nem minden bázisban.

Az n összetett szám erős pszeudoprím az n -nél kisebb bázisok legfeljebb egynegyedére [3] [4] . Így nincsenek "erős Carmichael-számok", olyan számok, amelyek minden bázisra erős pszeudoprímek. Ezért egy véletlen bázis mellett annak a valószínűsége, hogy egy szám erős pszeudoprím ebben a bázisban, nem haladja meg az 1/4-et, amit a széles körben használt Miller-Rabin tesztben használnak . Azonban Arnaud [5] adott egy 397 számjegyű összetett számot, amely erős pszeudoprím minden 307-nél kisebb bázisra. Az egyik módja annak, hogy elkerüljük az ilyen számok valószínű prímnek nyilvánítását, ha az erős esetleg prím tesztet kombináljuk a Lucas pszeudoprím teszttel . a Bailey-Pomeranz-Selfridge-Wagstaff tesztben .

Bármely bázishoz végtelenül sok erős pszeudoprím létezik [2] .

Példák

Az első erős pszeudoprímek a 2. alaphoz

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 80581, 85489, 8801EI579, 8801EI57S , 8801715 .

3. alap

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513 . OEIS ).

5. alap

781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 40501, 44801, 539381, 539381 ( O2371 ) A 15751 .

A 4. bázishoz lásd az A020230 -at, a 6-tól 100-ig terjedő bázisokat pedig lásd az A020232 - A020326 szekvenciákat .

A fenti feltételek több bázissal szembeni tesztelése erősebb primalitástesztet eredményez, mint egyetlen bázis teszt használata. Például csak 13 25•10 9 -nél kisebb szám van , amely egyszerre erős pszeudoprímek a 2., 3. és 5. bázishoz. A Pomerance és Selfridge [2] 7. táblázatában találhatók . A legkisebb ilyen szám a 25326001. Ez azt jelenti, hogy ha n kisebb, mint 25326001, ha n erős, esetleg prímszám a 2., 3. és 5. bázisban, akkor n prímszám.

A 3825123056546413051 szám a legkisebb szám, amely szintén erős pszeudoprím 9 bázisban, 2, 3, 5, 7, 11, 13, 17, 19 és 23 [6] [7] . Tehát ha n kisebb, mint 3825123056546413051, ha n erős valószínűségi prím e 9 ok miatt, akkor n prím.

A nem primer alap gondos megválasztásával még jobb tesztek készíthetők. Például nincsenek olyan összetett számok , amelyek erős pszeudoprímek lennének mind a hét 2., 325, 9375, 28178, 450775, 9780504 és 1795265022 bázisban [8] .

A legkisebb erős pszeudoprím az n -es alapig

n Legkevésbé n Legkevésbé n Legkevésbé n Legkevésbé
egy 9 33 545 65 33 97 49
2 2047 34 33 66 65 98 9
3 121 35 9 67 33 99 25
négy 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
nyolc 9 40 39 72 85 104 tizenöt
9 91 41 21 73 9 105 451
tíz 9 42 451 74 tizenöt 106 tizenöt
tizenegy 133 43 21 75 91 107 9
12 91 44 9 76 tizenöt 108 91
13 85 45 481 77 39 109 9
tizennégy tizenöt 46 9 78 77 110 111
tizenöt 1687 47 65 79 39 111 55
16 tizenöt 48 49 80 9 112 65
17 9 49 25 81 91 113 57
tizennyolc 25 ötven 49 82 9 114 115
19 9 51 25 83 21 115 57
húsz 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 tizenöt
24 25 56 55 88 87 120 91
25 217 57 25 89 9 121 tizenöt
26 9 58 57 90 91 122 65
27 121 59 tizenöt 91 9 123 85
28 9 60 481 92 91 124 25
29 tizenöt 61 tizenöt 93 25 125 9
harminc 49 62 9 94 93 126 25
31 tizenöt 63 529 95 1891 127 9
32 25 64 9 96 95 128 49

Jegyzetek

  1. ↑ Guy, 1994 , p. 27-30.
  2. ↑ 1 2 3 Pomerance, Selfridge, Wagstaff, 1980 , p. 1003–1026.
  3. ↑ Monier, 1980 , p. 97-108.
  4. ↑ Rabin, 1980 , p. 128-138.
  5. ↑ Arnault, 1995 , p. 151–161.
  6. ↑ Zhang, Tang, 2003 , p. 2085–2097
  7. ↑ Yupeng Jiang, Yingpu Deng (2012), Erős pszeudoprímek az első 9 prímbázishoz, arΧiv : 1207.0063v1 [math.NT]. 
  8. ↑ SPRP Records . Letöltve: 2015. június 3. Az eredetiből archiválva : 2015. október 11.

Irodalom