Pseudoprimo

În matematică , un număr pseudoprim este un număr care, deși nu este prim , îndeplinește unele proprietăți puternice care trebuie neapărat satisfăcute de primii, adică în ceea ce privește o serie de teste se comportă similar cu un număr prim. Definiția unui număr pseudoprim depinde, așadar, de context și de ceea ce se înțelege prin „comportarea ca un număr prim”.

Numerele pseudoprime apar adesea ca rezultatul algoritmilor care caută primii, folosind unele proprietăți puternice pe care trebuie să le satisfacă.

Pseudoprima lui Fermat

Definiție

Unele teoreme, cum ar fi teorema mică a lui Fermat

a^{N}\equiv a{\pmod {N}}

{\ displaystyle a ^ {N} \ echiv to {\ pmod {N}}}

{\ displaystyle a ^ {N} \ echiv to {\ pmod {N}}}

sunt valabile pentru fiecare $Nu.$ ${\ displaystyle N}$ $Nu.$ mai întâi și pentru fiecare $la$ ${\ displaystyle a}$ $la$ . În acest context, un număr $Nu.$ ${\ displaystyle N}$ $Nu.$ se numește pseudoprima lui Fermat în ceea ce privește $la$ ${\ displaystyle a}$ $la$ dacă relația afirmată de mica teoremă a lui Fermat este valabilă. Un număr care este pseudo-prim în raport cu fiecare $la$ ${\ displaystyle a}$ $la$ acoperim cu $Nu.$ ${\ displaystyle N}$ $Nu.$ este un număr Carmichael (pentru ca relația să apară, este necesar ca $la$ ${\ displaystyle a}$ $la$ o acoperim cu $Nu.$ ${\ displaystyle N}$ $Nu.$ ).

Cel mai mic număr de pseudoprime cu bază $a=2$ ${\ displaystyle a = 2}$ $a = 2$ si $341=11\cdot 31$ ${\ displaystyle 341 = 11 \ cdot 31}$ $341 = 11 \ cdot 31$ . Când un număr este pseudoprim sub toate bazele, adică indiferent de valoarea lui $la$ ${\ displaystyle a}$ $la$ , se numește numărul lui Carmichael .

Proprietate

Este $s>1$ ${\ displaystyle s> 1}$ ${\ displaystyle s> 1}$ un număr întreg ciudat nu este prim, atunci se mențin următoarele proprietăți:

De sine $s$ ${\ displaystyle s}$ $s$ este pseudoprime în elementele de bază $a_{1}$ ${\ displaystyle a_ {1}}$ $a_1$ și $a_{2}$ ${\ displaystyle a_ {2}}$ $a_2$ , astfel încât $MCD(a_{1},s)=1$ ${\ displaystyle MCD (a_ {1}, s) = 1}$ ${\ displaystyle MCD (a_ {1}, s) = 1}$ Și $MCD(a_{2},s)=1$ ${\ displaystyle MCD (a_ {2}, s) = 1}$ ${\ displaystyle MCD (a_ {2}, s) = 1}$ , asa de $s$ ${\ displaystyle s}$ $s$ este pseudoprime în elementele de bază $a_{1}a_{2}$ ${\ displaystyle a_ {1} a_ {2}}$ ${\ displaystyle a_ {1} a_ {2}}$ Și $a_{1}a_{2}^{-1}$ ${\ displaystyle a_ {1} a_ {2} ^ {- 1}}$ ${\ displaystyle a_ {1} a_ {2} ^ {- 1}}$ , unde este $a_{2}^{-1}$ ${\ displaystyle a_ {2} ^ {- 1}}$ ${\ displaystyle a_ {2} ^ {- 1}}$ este inversul $a_{2}$ ${\ displaystyle a_ {2}}$ $a_2$ modul $s$ ${\ displaystyle s}$ $s$ .
Dacă există un număr întreg $la$ ${\ displaystyle a}$ $la$ , cu $1<a<s$ ${\ displaystyle 1 <a <s}$ ${\ displaystyle 1 <a <s}$ Și $MCD(a,s)=1$ ${\ displaystyle MCD (a, s) = 1}$ ${\ displaystyle MCD (a, s) = 1}$ , astfel încât $s$ ${\ displaystyle s}$ $s$ nu este un pseudoprimo la bază $la$ ${\ displaystyle a}$ $la$ , asa de $s$ ${\ displaystyle s}$ $s$ nu este un pseudoprimo la bază $b$ ${\ displaystyle b}$ $b$ pentru cel puțin jumătate din $b$ ${\ displaystyle b}$ $b$ astfel încât $1<b<s$ ${\ displaystyle 1 <b <s}$ ${\ displaystyle 1 <b <s}$ Și $MCD(b,s)=1$ ${\ displaystyle MCD (b, s) = 1}$ ${\ displaystyle MCD (b, s) = 1}$ .

Să dovedim proprietățile anterioare:

Dacă merită $MCD(a_{1},s)=1$ ${\ displaystyle MCD (a_ {1}, s) = 1}$ ${\ displaystyle MCD (a_ {1}, s) = 1}$ Și $MCD(a_{2},s)=1$ ${\ displaystyle MCD (a_ {2}, s) = 1}$ ${\ displaystyle MCD (a_ {2}, s) = 1}$ , asa de $MCD(a_{1}a_{2},s)=1$ ${\ displaystyle MCD (a_ {1} a_ {2}, s) = 1}$ ${\ displaystyle MCD (a_ {1} a_ {2}, s) = 1}$ Și $MCD(a_{1}a_{2}^{-1},s)=1$ ${\ displaystyle MCD (a_ {1} a_ {2} ^ {- 1}, s) = 1}$ ${\ displaystyle MCD (a_ {1} a_ {2} ^ {- 1}, s) = 1}$ , atâta timp cât $a_{1}$ ${\ displaystyle a_ {1}}$ $a_1$ , $a_{2}$ ${\ displaystyle a_ {2}}$ $a_2$ , $a_{1}a_{2}$ ${\ displaystyle a_ {1} a_ {2}}$ ${\ displaystyle a_ {1} a_ {2}}$ , $a_{1}a_{2}^{-1}$ ${\ displaystyle a_ {1} a_ {2} ^ {- 1}}$ ${\ displaystyle a_ {1} a_ {2} ^ {- 1}}$ toate aparțin grupului de $\mathbb {Z} _{s}^{*}$ ${\ displaystyle \ mathbb {Z} _ {s} ^ {*}}$ ${\ displaystyle \ mathbb {Z} _ {s} ^ {*}}$ , adică grupului de elemente inversabile ale $\mathbb {Z} _{s}$ ${\ displaystyle \ mathbb {Z} _ {s}}$ ${\ displaystyle \ mathbb {Z} _ {s}}$ . Trebuie să vedem ce rezultate dau $(a_{1}a_{2})^{s-1}$ ${\ displaystyle (a_ {1} a_ {2}) ^ {s-1}}$ ${\ displaystyle (a_ {1} a_ {2}) ^ {s-1}}$ Și $(a_{1}a_{2}^{-1})^{s-1}$ ${\ displaystyle (a_ {1} a_ {2} ^ {- 1}) ^ {s-1}}$ ${\ displaystyle (a_ {1} a_ {2} ^ {- 1}) ^ {s-1}}$ . Să începem cu primul. Știind că este $a_{1}$ ${\ displaystyle a_ {1}}$ $a_1$ stă în $\mathbb {Z} _{s}^{*}$ ${\ displaystyle \ mathbb {Z} _ {s} ^ {*}}$ ${\ displaystyle \ mathbb {Z} _ {s} ^ {*}}$ este $a_{2}$ ${\ displaystyle a_ {2}}$ $a_2$ stă în $\mathbb {Z} _{s}^{*}$ ${\ displaystyle \ mathbb {Z} _ {s} ^ {*}}$ ${\ displaystyle \ mathbb {Z} _ {s} ^ {*}}$ și că ordinea lor este un divizor al $s-1$ ${\ displaystyle s-1}$ ${\ displaystyle s-1}$ , putem concluziona că compoziția celor două are și ca ordin un divizor de $s-1$ ${\ displaystyle s-1}$ ${\ displaystyle s-1}$ , și, prin urmare, ridicat la $s-1$ ${\ displaystyle s-1}$ ${\ displaystyle s-1}$ da unitate grupului $\mathbb {Z} _{s}^{*}$ ${\ displaystyle \ mathbb {Z} _ {s} ^ {*}}$ ${\ displaystyle \ mathbb {Z} _ {s} ^ {*}}$ (adică este congruent cu $1$ ${\ displaystyle 1}$ $1$ modul $s$ ${\ displaystyle s}$ $s$ ). Și pentru al doilea $a_{2}^{-1}$ ${\ displaystyle a_ {2} ^ {- 1}}$ ${\ displaystyle a_ {2} ^ {- 1}}$ stă în $\mathbb {Z} _{s}^{*}$ ${\ displaystyle \ mathbb {Z} _ {s} ^ {*}}$ ${\ displaystyle \ mathbb {Z} _ {s} ^ {*}}$ și are ca ordine un divizor de $s-1$ ${\ displaystyle s-1}$ ${\ displaystyle s-1}$ , intr-adevar $1=(a_{2}^{-1})^{s-1}a_{2}^{s-1}\equiv (a_{2}^{-1})^{s-1}\cdot 1=(a_{2}^{-1})^{s-1}$ ${\ displaystyle 1 = (a_ {2} ^ {- 1}) ^ {s-1} a_ {2} ^ {s-1} \ equiv (a_ {2} ^ {- 1}) ^ {s-1 } \ cdot 1 = (a_ {2} ^ {- 1}) ^ {s-1}}$ ${\ displaystyle 1 = (a_ {2} ^ {- 1}) ^ {s-1} a_ {2} ^ {s-1} \ equiv (a_ {2} ^ {- 1}) ^ {s-1 } \ cdot 1 = (a_ {2} ^ {- 1}) ^ {s-1}}$ . Prin urmare, $s$ ${\ displaystyle s}$ $s$ este pseudoprimo pe ambele baze $a_{1}a_{2}$ ${\ displaystyle a_ {1} a_ {2}}$ ${\ displaystyle a_ {1} a_ {2}}$ , ambele la bază $a_{1}a_{2}^{-1}$ ${\ displaystyle a_ {1} a_ {2} ^ {- 1}}$ ${\ displaystyle a_ {1} a_ {2} ^ {- 1}}$ .
Să considerăm ca un element al $\mathbb {Z} _{s}^{*}$ ${\ displaystyle \ mathbb {Z} _ {s} ^ {*}}$ ${\ displaystyle \ mathbb {Z} _ {s} ^ {*}}$ . Este $LA$ ${\ displaystyle A}$ $LA$ subsetul de $\mathbb {Z} _{s}^{*}$ ${\ displaystyle \ mathbb {Z} _ {s} ^ {*}}$ ${\ displaystyle \ mathbb {Z} _ {s} ^ {*}}$ format din clasele al căror rest $b$ ${\ displaystyle b}$ $b$ modul $s$ ${\ displaystyle s}$ $s$ este astfel încât $n$ ${\ displaystyle n}$ $n$ este pseudoprimo în bază $b$ ${\ displaystyle b}$ $b$ . Pentru (1), consideră că, dacă $b$ ${\ displaystyle b}$ $b$ stă în $LA$ ${\ displaystyle A}$ $LA$ , asa de $la b$ ${\ displaystyle ab}$ $ab$ nu se potrivește $LA$ ${\ displaystyle A}$ $LA$ (in caz contrar $a=abb^{-1}$ ${\ displaystyle a = abb ^ {- 1}}$ ${\ displaystyle a = abb ^ {- 1}}$ ar aparține $LA$ ${\ displaystyle A}$ $LA$ ). Prin urmare, avem o aplicație injectivă $\varphi \colon b\in A\to \mathbb {Z} _{s}^{*}\setminus A$ ${\ displaystyle \ varphi \ colon b \ in A \ to \ mathbb {Z} _ {s} ^ {*} \ setminus A}$ ${\ displaystyle \ varphi \ colon b \ in A \ to \ mathbb {Z} _ {s} ^ {*} \ setminus A}$ . Prin urmare, ordinea $P.$ ${\ displaystyle P}$ $P.$ nu depășește ordinea $\mathbb {Z} _{s}^{*}\setminus A$ ${\ displaystyle \ mathbb {Z} _ {s} ^ {*} \ setminus A}$ ${\ displaystyle \ mathbb {Z} _ {s} ^ {*} \ setminus A}$ .

Exemple și curiozități

Cel mai mic pseudoprime (al lui Fermat) în bază $2$ ${\ displaystyle 2}$ $2$ Și $341$ ${\ displaystyle 341}$ ${\ displaystyle 341}$ . Noi stim aia $341=11\cdot 31$ ${\ displaystyle 341 = 11 \ cdot 31}$ $341 = 11 \ cdot 31$ , asa de $341$ ${\ displaystyle 341}$ ${\ displaystyle 341}$ nu este prim, dar satisface mica teoremă a lui Fermat , adică

2^{340}\equiv 1{\pmod {341}}.

{\ displaystyle 2 ^ {340} \ equiv 1 {\ pmod {341}}.}

{\ displaystyle 2 ^ {340} \ equiv 1 {\ pmod {341}}.}

Un număr pseudoprim în bază $3$ ${\ displaystyle 3}$ $3$ și nu în bază $2$ ${\ displaystyle 2}$ $2$ Și $91$ ${\ displaystyle 91}$ ${\ displaystyle 91}$ , și știm asta $91=7\cdot 13$ ${\ displaystyle 91 = 7 \ cdot 13}$ ${\ displaystyle 91 = 7 \ cdot 13}$ .

Numerele pseudoprime din bază $2$ ${\ displaystyle 2}$ $2$ se numesc numere Poulet sau numere Sarrus sau Fermatian.

Având o bază $h$ ${\ displaystyle h}$ $h$ , există pseudoprime infinite în acea bază, dar știm, de asemenea, că sunt foarte „rarefiate” în numerele întregi (sunt infinite, dar dacă luăm în considerare orice interval de un milion de numere întregi consecutive, găsim cel mult câteva sute).

Pseudoprima lui Euler

Același subiect în detaliu: pseudoprima lui Euler .

Pseudoprimile lui Euler prezintă multe asemănări cu cele ale lui Fermat.

Este $b$ ${\ displaystyle b}$ $b$ un întreg, și așa să fie $n$ ${\ displaystyle n}$ $n$ un număr impar pozitiv, nu prim, și astfel încât $MCD(n,b)=1$ ${\ displaystyle MCD (n, b) = 1}$ ${\ displaystyle MCD (n, b) = 1}$ . Numarul $n$ ${\ displaystyle n}$ $n$ este un pseudoprime al lui Euler în bază $b$ ${\ displaystyle b}$ $b$ de sine

b^{(n-1)/2}\equiv \pm 1{\pmod {n}}.

{\ displaystyle b ^ {(n-1) / 2} \ equiv \ pm 1 {\ pmod {n}}.}

{\ displaystyle b ^ {(n-1) / 2} \ equiv \ pm 1 {\ pmod {n}}.}

Utilizare

Una dintre cele mai importante aplicații ale numerelor pseudoprime se găsește în algoritmii de „ criptografie cu cheie publică ”, unul dintre cele mai utilizate tipuri de criptografie din timpul nostru. Un algoritm criptografic cu cheie publică foarte popular care utilizează numere prime mari este RSA . În acești algoritmi este esențial să se genereze numere prime foarte mari: întrucât testele de primalitate deterministe, cum ar fi cea Agrawal-Kayal-Saxena, sunt lente (ca să nu mai vorbim de testul Wilson ), suntem mulțumiți de unul pseudoprimo, adică dintr-un număr care este foarte probabil prim. ^{[ Pseudoprima este un număr compus care trece mai întâi, un algoritm probabilist va da în multe alte cazuri un prim real ]}

Dacă α este probabilitatea ca un număr compus să treacă un test (de exemplu, $\alpha =1/2$ ${\ displaystyle \ alpha = 1/2}$ ${\ displaystyle \ alpha = 1/2}$ pentru compozite non- Carmichael pentru testul lui Fermat ; $\alpha =1/4$ ${\ displaystyle \ alpha = 1/4}$ ${\ displaystyle \ alpha = 1/4}$ pentru testul Miller-Rabin ), atunci probabilitatea ca un număr compus să treacă $n$ ${\ displaystyle n}$ $n$ ori testul este $\alpha ^{n}$ ${\ displaystyle \ alpha ^ {n}}$ ${\ displaystyle \ alpha ^ {n}}$ . Acest lucru nu înseamnă că un număr care trece $n$ ${\ displaystyle n}$ $n$ testul este compus cu probabilitate $\alpha ^{n}$ ${\ displaystyle \ alpha ^ {n}}$ ${\ displaystyle \ alpha ^ {n}}$ : după teorema lui Bayes , considerând că probabilitatea ca un număr $X$ ${\ displaystyle x}$ $X$ fi prim este $1/\ln {x}$ ${\ displaystyle 1 / \ ln {x}}$ ${\ displaystyle 1 / \ ln {x}}$ și presupunând $\alpha ^{n}$ ${\ displaystyle \ alpha ^ {n}}$ ${\ displaystyle \ alpha ^ {n}}$ mult mai mare decât $\ln {x}$ ${\ displaystyle \ ln {x}}$ ${\ displaystyle \ ln {x}}$ , avem asta: probabilitatea ca un număr să treacă $n$ ${\ displaystyle n}$ $n$ testul este compozit este $\ln {x}/\alpha ^{n}$ ${\ displaystyle \ ln {x} / \ alpha ^ {n}}$ ${\ displaystyle \ ln {x} / \ alpha ^ {n}}$

Elemente conexe

linkuri externe

( EN ) Pseudoprimo , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.

Portal de criptografie

Portalul de matematică