Vahva pseudoprime

Vakaa versio kirjattiin ulos 5.8.2022 . Malleissa tai malleissa on vahvistamattomia muutoksia .

Todennäköinen alkuluku on sellainen, joka läpäisee primaalisuustestin . Vahva todennäköinen alkuluku on luku, joka läpäisee primaalisuustestin vahvan version. Vahva pseudoalkuluku on yhdistelmäluku , joka läpäisee primaalisuustestin vahvan version.

Kaikki alkuluvut läpäisevät tämän testin, mutta pieni osa yhdistelmäluvuista myös läpäisee tämän testin, mikä tekee niistä " vääriä alkulukuja ".

Toisin kuin Fermat-pseudoalkuluvut , joille on lukuja, jotka ovat pseudoalkulukuja kaikissa emäksissä ( Carmichael-luvut ), ei ole yhdistelmälukuja, jotka ovat vahvoja pseudoalkulukuja kaikissa emäksissä.

Muodollinen määritelmä

Muodollisesti paritonta yhdistelmälukua n = d • 2 s + 1, jossa on pariton d , kutsutaan vahvaksi pseudoalkuluvuksi (Fermat) emäksessä a, jos jokin seuraavista ehdoista on tosi:

tai

joillekin

(Jos n täyttää yllä olevat ehdot, emmekä tiedä, onko se alkuluku vai ei, on tarkempaa kutsua sitä vahvaksi luultavasti alkuluvuksi kantaluvussa a . Jos tiedämme, että n ei ole alkuluku, voimme käyttää termiä vahva pseudoalkuluku. )

Määritelmä on triviaali, jos a ≡ ±1 mod n , joten nämä triviaalit tapaukset suljetaan usein pois.

Richard Guy antoi määritelmän virheellisesti vain ensimmäisellä ehdolla, mutta kaikki alkuluvut eivät täytä sitä [1] .

Vahvojen pseudoalkulukujen ominaisuudet

Vahva pseudoalkuluku a-perustalle on aina Euler-Jacobin pseudoalkuluku , Eulerin pseudoalkuluku [2] ja Fermat-pseudoalku tälle kantalle, mutta kaikki Euler- ja Fermat-pseudoalkuluvut eivät ole vahvoja pseudoalkulukuja. Carmichael-luvut voivat olla vahvoja pseudoalkulukuja joissakin emäksissä, esimerkiksi 561 on vahva pseudoalkuluku emäksessä 50, mutta ei kaikissa emäksissä.

Yhdistelmäluku n on vahva pseudoalkuluku korkeintaan neljännekselle kaikista alle n :n emäksistä [3] [4] . Siten ei ole olemassa "vahvoja Carmichael-lukuja", lukuja, jotka ovat vahvoja pseudoalkulukuja kaikille emäksille. Näin ollen, kun otetaan huomioon satunnainen kanta, todennäköisyys, että luku on vahva pseudoalkuluku kyseisessä emäksessä, ei ylitä 1/4, jota käytetään laajalti käytetyssä Miller-Rabin-testissä . Arnaud [5] on kuitenkin antanut 397-numeroisen yhdistelmäluvun, joka on vahva pseudoalkuluku mille tahansa alle 307:ää pienemmälle emäkselle. Yksi tapa välttää tällaisten lukujen julistaminen todennäköisiksi alkuluvuiksi on yhdistää vahva mahdollisesti alkulukutesti Lucasin pseudoprime- testiin . Bailey - Pomeranz-Selfridge-Wagstaff-testissä .

Jokaiselle tietylle emäkselle on äärettömän paljon vahvoja pseudoalkulukuja [2] .

Esimerkkejä

Ensimmäiset vahvat pseudoalkuluvut kantaan 2

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 80581, 85489, 880171S, 890715 , 890715 .

Pohja 3

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

Pohja 5

781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 40501, 44801, ... A20711, 539381 , 539381 .

Katso emäs 4 kohdasta A020230 ja emäkset 6 - 100, katso sekvenssit A020232 - A020326 .

Yllä olevien olosuhteiden testaaminen useita emäksiä vastaan ​​johtaa tehokkaampaan primaalisuustestiin kuin yhden emäksen testin käyttäminen. Esimerkiksi, on vain 13 numeroa, jotka ovat pienempiä kuin 25•10 9 , jotka ovat samanaikaisesti vahvoja pseudoalkulukuja emäksille 2, 3 ja 5. Ne on lueteltu taulukossa 7 teoksessa Pomerance and Selfridge [2] . Pienin tällainen luku on 25326001. Tämä tarkoittaa, että jos n on pienempi kuin 25326001, jos n on vahva mahdollisesti alkuluku kantaluvuissa 2, 3 ja 5, niin n on alkuluku.

Numero 3825123056546413051 on pienin luku, joka on myös vahva pseudoalkuluku yhdeksässä emäksessä 2, 3, 5, 7, 11, 13, 17, 19 ja 23 [6] [7] . Joten jos n on pienempi kuin 3825123056546413051, jos n on vahva todennäköinen alkuluku näistä 9 syystä, niin n on alkuluku.

Huolellisella valinnalla pohja, joka ei ole prime, voidaan rakentaa vielä parempia testejä. Esimerkiksi ei ole olemassa yhdistelmälukuja , jotka ovat vahvoja pseudoalkulukuja kaikissa seitsemässä emäksessä 2, 325, 9375, 28178, 450775, 9780504 ja 1795265022 [8] .

Pienin vahva pseudoalkuluku kantaan n

n Vähiten n Vähiten n Vähiten n Vähiten
yksi 9 33 545 65 33 97 49
2 2047 34 33 66 65 98 9
3 121 35 9 67 33 99 25
neljä 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
kahdeksan 9 40 39 72 85 104 viisitoista
9 91 41 21 73 9 105 451
kymmenen 9 42 451 74 viisitoista 106 viisitoista
yksitoista 133 43 21 75 91 107 9
12 91 44 9 76 viisitoista 108 91
13 85 45 481 77 39 109 9
neljätoista viisitoista 46 9 78 77 110 111
viisitoista 1687 47 65 79 39 111 55
16 viisitoista 48 49 80 9 112 65
17 9 49 25 81 91 113 57
kahdeksantoista 25 viisikymmentä 49 82 9 114 115
19 9 51 25 83 21 115 57
kaksikymmentä 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 viisitoista
24 25 56 55 88 87 120 91
25 217 57 25 89 9 121 viisitoista
26 9 58 57 90 91 122 65
27 121 59 viisitoista 91 9 123 85
28 9 60 481 92 91 124 25
29 viisitoista 61 viisitoista 93 25 125 9
kolmekymmentä 49 62 9 94 93 126 25
31 viisitoista 63 529 95 1891 127 9
32 25 64 9 96 95 128 49

Muistiinpanot

  1. ↑ Guy, 1994 , s. 27-30.
  2. ↑ 1 2 3 Pomerance, Selfridge, Wagstaff, 1980 , s. 1003–1026.
  3. ↑ Monier, 1980 , s. 97-108.
  4. ↑ Rabin, 1980 , s. 128-138.
  5. ↑ Arnault, 1995 , s. 151-161.
  6. ↑ Zhang, Tang, 2003 , s. 2085–2097
  7. ↑ Yupeng Jiang, Yingpu Deng (2012), Vahvat pseudoalkuluvut 9 ensimmäiseen alkukantaan, arΧiv : 1207.0063v1 [math.NT]. 
  8. ↑ SPRP Records . Haettu 3. kesäkuuta 2015. Arkistoitu alkuperäisestä 11. lokakuuta 2015.

Kirjallisuus