Pseudoprim puternic

Versiunea stabilă a fost verificată pe 5 august 2022 . Există modificări neverificate în șabloane sau .

Un număr prim probabil este unul care trece testul de primalitate . Un prim probabil puternic este un număr care trece versiunea puternică a testului de primalitate. Un pseudoprim puternic este un număr compus care trece versiunea puternică a testului de primalitate.

Toate numerele prime trec acest test, dar o mică parte din numerele compuse trec de asemenea acest test, făcându-le „ prime false ”.

Spre deosebire de pseudoprimele Fermat , pentru care există numere care sunt pseudoprime în toate bazele coprime ( numerele Carmichael ), nu există numere compuse care sunt pseudoprime puternice în toate bazele.

Definiție formală

Formal, un număr compus impar n = d • 2 s + 1 cu d impar se numește pseudoprim puternic (Fermat) în baza a dacă una dintre următoarele condiții este adevărată:

sau

pentru unii

(Dacă n îndeplinește condițiile de mai sus și nu știm dacă este prim sau nu, este mai corect să-l numim probabil prim puternic în baza a . Dacă știm că n nu este prim, putem folosi termenul pseudoprim puternic. )

Definiția este banală dacă a ≡ ±1 mod n , astfel încât aceste cazuri triviale sunt adesea excluse.

Richard Guy a dat în mod eronat definiția doar cu prima condiție, dar nu toate numerele prime o satisfac [1] .

Proprietățile pseudoprimelor puternice

Un pseudoprim puternic la baza a este întotdeauna un pseudoprim Euler-Jacobi , Euler pseudoprim [2] , și un pseudoprim Fermat la acea bază, dar nu toate pseudoprimele Euler și Fermat sunt pseudoprime puternice. Numerele Carmichael pot fi pseudoprim puternice în unele baze, de exemplu, 561 este pseudoprim puternic în baza 50, dar nu în toate bazele.

Numărul compus n este un pseudoprim puternic pentru cel mult un sfert din bazele mai mici decât n [3] [4] . Astfel, nu există „numere Carmichael puternice”, numere care sunt pseudoprime puternice pentru toate bazele. Prin urmare, având în vedere o bază aleatorie, probabilitatea ca un număr să fie pseudoprim puternic în acea bază nu depășește 1/4, care este utilizat în testul Miller-Rabin , utilizat pe scară largă . Cu toate acestea, Arnaud [5] a dat un număr compus de 397 de cifre care este pseudoprim puternic oricărei baze mai mici de 307. O modalitate de a evita declararea unor astfel de numere prime probabile este să combinați testul probabil prim puternic cu testul pseudoprim Lucas . în testul Bailey-Pomeranz-Selfridge-Wagstaff .

Există infinit de multe pseudoprime puternice pentru orice bază particulară [2] .

Exemple

Primele pseudoprime puternice la baza 2

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

Baza 3

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

Baza 5

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

Pentru baza 4, vezi A020230 , iar pentru bazele 6 până la 100, vezi secvențele A020232 până la A020326 .

Testarea condițiilor de mai sus față de mai multe baze are ca rezultat un test de primalitate mai puternic decât utilizarea unui singur test de bază. De exemplu, există doar 13 numere mai mici decât 25•10 9 care sunt pseudoprime puternice pentru bazele 2, 3 și 5 în același timp. Ele sunt enumerate în Tabelul 7 din Pomerance și Selfridge [2] . Cel mai mic astfel de număr este 25326001. Aceasta înseamnă că pentru n mai mic decât 25326001, dacă n este un număr prim, posibil, puternic în bazele 2, 3 și 5, atunci n este prim.

Numărul 3825123056546413051 este cel mai mic număr care este și pseudoprim puternic în 9 baze 2, 3, 5, 7, 11, 13, 17, 19 și 23 [6] [7] . Deci, pentru n mai mic decât 3825123056546413051, dacă n este prim probabil puternic din aceste 9 motive, atunci n este prim.

Prin alegerea atentă a unei baze care nu este primară, pot fi construite teste și mai bune. De exemplu, nu există numere compuse care să fie pseudoprime puternice în toate cele șapte baze 2, 325, 9375, 28178, 450775, 9780504 și 1795265022 [8] .

Cel mai mic pseudoprim puternic la baza n

n Cel mai puţin n Cel mai puţin n Cel mai puţin n Cel mai puţin
unu 9 33 545 65 33 97 49
2 2047 34 33 66 65 98 9
3 121 35 9 67 33 99 25
patru 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
opt 9 40 39 72 85 104 cincisprezece
9 91 41 21 73 9 105 451
zece 9 42 451 74 cincisprezece 106 cincisprezece
unsprezece 133 43 21 75 91 107 9
12 91 44 9 76 cincisprezece 108 91
13 85 45 481 77 39 109 9
paisprezece cincisprezece 46 9 78 77 110 111
cincisprezece 1687 47 65 79 39 111 55
16 cincisprezece 48 49 80 9 112 65
17 9 49 25 81 91 113 57
optsprezece 25 cincizeci 49 82 9 114 115
19 9 51 25 83 21 115 57
douăzeci 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 cincisprezece
24 25 56 55 88 87 120 91
25 217 57 25 89 9 121 cincisprezece
26 9 58 57 90 91 122 65
27 121 59 cincisprezece 91 9 123 85
28 9 60 481 92 91 124 25
29 cincisprezece 61 cincisprezece 93 25 125 9
treizeci 49 62 9 94 93 126 25
31 cincisprezece 63 529 95 1891 127 9
32 25 64 9 96 95 128 49

Note

  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), Pseudoprime puternice la primele 9 baze prime, arΧiv : 1207.0063v1 [math.NT]. 
  8. ↑ Înregistrări SPRP . Preluat la 3 iunie 2015. Arhivat din original la 11 octombrie 2015.

Literatură