Pseudoprimo

In matematica, un numero pseudoprimo è un numero che, pur non essendo primo, soddisfa alcune proprietà forti che devono essere necessariamente soddisfatte dai primi, ovvero rispetto a una serie di test si comporta analogamente ad un numero primo. La definizione di numero pseudoprimo dipende quindi dal contesto, e da cosa si intende per "comportarsi come un numero primo".

I numeri pseudoprimi appaiono spesso come output di algoritmi che ricercano numeri primi, usando alcune proprietà forti che questi devono soddisfare.

Pseudoprimo di Fermat

Definizione

Alcuni teoremi, come il piccolo teorema di Fermat

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

sono validi per ogni ${\displaystyle N}$ primo, e per ogni ${\displaystyle a}$. In questo contesto, un numero ${\displaystyle N}$ è detto pseudoprimo di Fermat rispetto ad ${\displaystyle a}$ se vale la relazione enunciata dal piccolo teorema di Fermat. Un numero che è pseudoprimo rispetto ad ogni ${\displaystyle a}$ coprimo con ${\displaystyle N}$ è un numero di Carmichael (affinché la relazione si verifichi, è necessario che ${\displaystyle a}$ sia coprimo con ${\displaystyle N}$).

Il più piccolo numero pseudoprimo con base ${\displaystyle a=2}$ è il ${\displaystyle 341=11\cdot 31}$. Quando un numero è pseudoprimo sotto tutte le basi, cioè qualunque sia il valore di ${\displaystyle a}$, prende il nome di numero di Carmichael.

Proprietà

Sia ${\displaystyle s>1}$ un intero dispari non primo, allora valgono le seguenti proprietà:

1. Se ${\displaystyle s}$ è pseudoprimo nelle basi ${\displaystyle a_{1}}$ ed ${\displaystyle a_{2}}$, tali che ${\displaystyle MCD(a_{1},s)=1}$ e ${\displaystyle MCD(a_{2},s)=1}$, allora ${\displaystyle s}$ è pseudoprimo nelle basi ${\displaystyle a_{1}a_{2}}$ e ${\displaystyle a_{1}a_{2}^{-1}}$, dove ${\displaystyle a_{2}^{-1}}$ è l'inverso di ${\displaystyle a_{2}}$ modulo ${\displaystyle s}$.
2. Se esiste un intero ${\displaystyle a}$, con ${\displaystyle 1<a<s}$ e ${\displaystyle MCD(a,s)=1}$, tale che ${\displaystyle s}$ non è uno pseudoprimo in base ${\displaystyle a}$, allora ${\displaystyle s}$ non è uno pseudoprimo in base ${\displaystyle b}$ per almeno metà dei ${\displaystyle b}$ tali che ${\displaystyle 1<b<s}$ e ${\displaystyle MCD(b,s)=1}$.

Dimostriamo le proprietà precedenti:

1. Se valgono ${\displaystyle MCD(a_{1},s)=1}$ e ${\displaystyle MCD(a_{2},s)=1}$, allora ${\displaystyle MCD(a_{1}a_{2},s)=1}$ e ${\displaystyle MCD(a_{1}a_{2}^{-1},s)=1}$, poiché ${\displaystyle a_{1}}$, ${\displaystyle a_{2}}$, ${\displaystyle a_{1}a_{2}}$, ${\displaystyle a_{1}a_{2}^{-1}}$ appartengono tutti al gruppo di ${\displaystyle \mathbb {Z} _{s}^{*}}$, ossia al gruppo degli elementi invertibili di ${\displaystyle \mathbb {Z} _{s}}$. Dobbiamo vedere quali risultati danno ${\displaystyle (a_{1}a_{2})^{s-1}}$ e ${\displaystyle (a_{1}a_{2}^{-1})^{s-1}}$. Partiamo dal primo. Sapendo che sia ${\displaystyle a_{1}}$ sta in ${\displaystyle \mathbb {Z} _{s}^{*}}$ sia ${\displaystyle a_{2}}$ sta in ${\displaystyle \mathbb {Z} _{s}^{*}}$ e che il loro ordine è un divisore di ${\displaystyle s-1}$, possiamo concludere che la composizione dei due abbia anch'essa come ordine un divisore di ${\displaystyle s-1}$, e, quindi, elevata ad ${\displaystyle s-1}$ dia l'unità del gruppo ${\displaystyle \mathbb {Z} _{s}^{*}}$ (ossia è congruo a ${\displaystyle 1}$ modulo ${\displaystyle s}$). Per la seconda, anche ${\displaystyle a_{2}^{-1}}$ sta in ${\displaystyle \mathbb {Z} _{s}^{*}}$ ed ha come ordine un divisore di ${\displaystyle s-1}$, infatti ${\displaystyle 1=(a_{2}^{-1})^{s-1}a_{2}^{s-1}\equiv (a_{2}^{-1})^{s-1}\cdot 1=(a_{2}^{-1})^{s-1}}$. Quindi, ${\displaystyle s}$ è pseudoprimo sia in base ${\displaystyle a_{1}a_{2}}$, sia in base ${\displaystyle a_{1}a_{2}^{-1}}$.
2. Consideriamo come a un elemento di ${\displaystyle \mathbb {Z} _{s}^{*}}$. Sia ${\displaystyle A}$ il sottoinsieme di ${\displaystyle \mathbb {Z} _{s}^{*}}$ costituito dalle classi il cui resto ${\displaystyle b}$ modulo ${\displaystyle s}$ è tale che ${\displaystyle n}$ è pseudoprimo in base ${\displaystyle b}$. Per (1), vale che, se ${\displaystyle b}$ sta in ${\displaystyle A}$, allora ${\displaystyle ab}$ non sta in ${\displaystyle A}$ (altrimenti ${\displaystyle a=abb^{-1}}$ apparterrebbe ad ${\displaystyle A}$). Si ha, dunque, un'applicazione iniettiva ${\displaystyle \varphi \colon b\in A\to \mathbb {Z} _{s}^{*}\setminus A}$. Dunque, l'ordine di ${\displaystyle P}$ non supera l'ordine di ${\displaystyle \mathbb {Z} _{s}^{*}\setminus A}$.

Esempi e curiosità

Il più piccolo pseudoprimo (di Fermat) in base ${\displaystyle 2}$ è ${\displaystyle 341}$. Sappiamo che ${\displaystyle 341=11\cdot 31}$, quindi ${\displaystyle 341}$ non è primo, ma esso soddisfa il piccolo teorema di Fermat, ossia

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

Un numero pseudoprimo in base ${\displaystyle 3}$ e non in base ${\displaystyle 2}$ è ${\displaystyle 91}$, e sappiamo che ${\displaystyle 91=7\cdot 13}$.

I numeri pseudoprimi in base ${\displaystyle 2}$ si dicono numeri di Poulet o numeri di Sarrus o Fermatiani.

Data una base ${\displaystyle h}$, vi sono infiniti pseudoprimi in quella base, ma sappiamo anche che sono molto “rarefatti” negli interi (sono infiniti, ma se si considera un qualsiasi intervallo di un milione di interi consecutivi, ne troviamo al massimo qualche centinaia).

Pseudoprimo di Eulero

Gli pseudoprimi di Eulero hanno molte somiglianze con quelli di Fermat.

Sia ${\displaystyle b}$ un intero, e sia ${\displaystyle n}$ un intero dispari positivo, non primo, e tale che ${\displaystyle MCD(n,b)=1}$. Il numero ${\displaystyle n}$ è uno pseudoprimo di Eulero in base ${\displaystyle b}$ se

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

Utilizzo

Una delle applicazioni più importanti dei numeri pseudoprimi si trova negli algoritmi di “crittografia a chiave pubblica”, uno dei tipi di crittografia più utilizzati nel nostro tempo. Un algoritmo di crittografia a chiave pubblica molto famoso che utilizza grandi numeri primi è RSA. In questi algoritmi è fondamentale generare dei numeri primi molto grandi: poiché test di primalità deterministici come quello di Agrawal-Kayal-Saxena sono lenti (per non parlare del test di Wilson), ci si accontenta di uno pseudoprimo, cioè di un numero che con grande probabilità è primo.^[Lo pseudoprimo è un numero composto che passa per primo, un algoritmo probabilistico darà in molti più casi un primo reale]

Se α è la probabilità che un numero composito passi un test (ad esempio, ${\displaystyle \alpha =1/2}$ per i compositi non di Carmichael per il test di Fermat; ${\displaystyle \alpha =1/4}$ per il test di Miller-Rabin), allora la probabilità che un numero composito passi ${\displaystyle n}$ volte il test è ${\displaystyle \alpha ^{n}}$. Questo non vuol dire che un numero che passi ${\displaystyle n}$ test sia composito con probabilità ${\displaystyle \alpha ^{n}}$: per il teorema di Bayes, considerando che la probabilità che un numero ${\displaystyle x}$ sia primo è ${\displaystyle 1/\ln {x}}$ e supponendo ${\displaystyle \alpha ^{n}}$ molto più grande di ${\displaystyle \ln {x}}$, abbiamo che: la probabilità che un numero che passi ${\displaystyle n}$ test sia composito è ${\displaystyle \ln {x}/\alpha ^{n}}$

Voci correlate

• Numero di Carmichael
• Piccolo teorema di Fermat
• Numero primo
• Pseudoprimo di Eulero
• Pseudoprimo di Fibonacci
• Pseudoprimo forte
• Test di Wilson
• Test di Lucas-Lehmer
• Test di Miller-Rabin

Collegamenti esterni

• Numero pseudoprimo, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) William L. Hosch, pseudoprime, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Pseudoprime, su MathWorld, Wolfram Research.
• (EN) Denis Howe, pseudoprime, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL