Stark pseudoprime

Den stabila versionen checkades ut den 5 augusti 2022 . Det finns overifierade ändringar i mallar eller .

Ett troligt primtal är ett som klarar primalitetstestet . Ett starkt troligt primtal är ett tal som klarar den starka versionen av primalitetstestet. En stark pseudoprim är ett sammansatt tal som klarar den starka versionen av primalitetstestet.

Alla primtal klarar detta test, men en liten del av sammansatta tal klarar också detta test, vilket gör dem till " falska primtal ".

Till skillnad från Fermat-pseudoprimerna , för vilka det finns tal som är pseudoprime i alla coprime- baser ( Carmichael-tal ), finns det inga sammansatta tal som är starka pseudoprime i alla baser.

Formell definition

Formellt kallas ett udda sammansatt tal n = d • 2 s + 1 med udda d ett starkt pseudoprimtal (Fermat) i bas a om något av följande villkor är sant:

eller

för vissa

(Om n uppfyller ovanstående villkor och vi inte vet om det är primtal eller inte, är det mer korrekt att kalla det starkt förmodligen primtal i bas a . Om vi ​​vet att n inte är primtal kan vi använda termen starkt pseudoprimtal. )

Definitionen är trivial om a ≡ ±1 mod n , så dessa triviala fall är ofta uteslutna.

Richard Guy gav felaktigt definitionen med endast det första villkoret, men inte alla primtal uppfyller det [1] .

Egenskaper för starka pseudoprimer

En stark pseudoprime till bas a är alltid en Euler-Jacobi pseudoprime , Euler pseudoprime [2] , och en Fermat pseudoprime till den basen, men inte alla Euler och Fermat pseudoprimer är starka pseudoprimer. Carmichael-tal kan vara starka pseudoprime i vissa baser, till exempel är 561 stark pseudoprime i bas 50, men inte i alla baser.

Det sammansatta talet n är ett starkt pseudoprimtal för högst en fjärdedel av alla baser mindre än n [3] [4] . Det finns alltså inga "starka Carmichael-tal", tal som är starka pseudoprimer för alla baser. Därför, givet en slumpmässig bas, överstiger sannolikheten att ett tal är starkt pseudoprim i den basen inte 1/4, vilket används i det mycket använda Miller-Rabin-testet . Arnaud [5] har dock gett ett 397-siffrigt sammansatt tal som är starkt pseudoprimtal till vilken bas som helst mindre än 307. Ett sätt att undvika att deklarera sådana tal som troligt primtal är att kombinera det starka möjligen primtalstestet med Lucas pseudoprimtest . , som i Bailey-Pomeranz-Selfridge-Wagstaff-testet .

Det finns oändligt många starka pseudoprimer för någon speciell bas [2] .

Exempel

Första starka pseudoprimer till bas 2

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

Bas 3

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567. sequence A020229 in the OEIS ).

Bas 5

781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351 , 29539 .

För bas 4, se A020230 , och för baser 6 till 100, se sekvenserna A020232 till A020326 .

Att testa ovanstående förhållanden mot flera baser resulterar i ett kraftfullare primalitetstest än att använda ett enda bastest. Till exempel finns det bara 13 tal mindre än 25•10 9 som är starka pseudoprimer till baserna 2, 3 och 5 samtidigt. De är listade i tabell 7 i Pomerance och Selfridge [2] . Det minsta talet är 25326001. Detta betyder att för n mindre än 25326001, om n är ett starkt möjligen primtal i baserna 2, 3 och 5, så är n primtal.

Talet 3825123056546413051 är det minsta talet som också är starkt pseudoprimtal i 9 baser 2, 3, 5, 7, 11, 13, 17, 19 och 23 [6] [7] . Så för n mindre än 3825123056546413051, om n är starkt troligt primtal av dessa 9 skäl, då är n primtal.

Genom noggrant val av en bas som inte är prima kan ännu bättre tester konstrueras. Till exempel finns det inga sammansatta tal som är starka pseudoprimer i alla sju baserna 2, 325, 9375, 28178, 450775, 9780504 och 1795265022 [8] .

Den minsta starka pseudoprimen till bas n

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

Anteckningar

  1. ↑ Guy, 1994 , sid. 27-30.
  2. ↑ 1 2 3 Pomerance, Selfridge, Wagstaff, 1980 , sid. 1003–1026.
  3. ↑ Monier, 1980 , sid. 97-108.
  4. ↑ Rabin, 1980 , sid. 128-138.
  5. ↑ Arnault, 1995 , sid. 151–161.
  6. ↑ Zhang, Tang, 2003 , sid. 2085–2097
  7. ↑ Yupeng Jiang, Yingpu Deng (2012), Starka pseudoprimer till de första 9 primbaserna, arΧiv : 1207.0063v1 [math.NT]. 
  8. ↑ SPRP-rekord . Hämtad 3 juni 2015. Arkiverad från originalet 11 oktober 2015.

Litteratur