Apri il menu principale

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 FermatModifica

DefinizioneModifica

Alcuni teoremi, come il piccolo teorema di Fermat

 

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

Il più piccolo numero pseudoprimo con base   è il  . Quando un numero è pseudoprimo sotto tutte le basi, cioè qualunque sia il valore di  , prende il nome di numero di Carmichael.

ProprietàModifica

Sia   un intero dispari non primo, allora valgono le seguenti proprietà:

  1. Se   è pseudoprimo nelle basi   ed  , tali che   e  , allora   è pseudoprimo nelle basi   e  , dove   è l'inverso di   modulo  .
  2. Se esiste un intero  , con   e  , tale che   non è uno pseudoprimo in base  , allora   non è uno pseudoprimo in base   per almeno metà dei   tali che   e  .

Dimostriamo le proprietà precedenti:

  1. Se valgono   e  , allora   e  , poiché  ,  ,  ,   appartengono tutti al gruppo di  , ossia al gruppo degli elementi invertibili di  . Dobbiamo vedere quali risultati danno   e  . Partiamo dal primo. Sapendo che sia   sta in   sia   sta in   e che il loro ordine è un divisore di  , possiamo concludere che la composizione dei due abbia anch'essa come ordine un divisore di  , e, quindi, elevata ad   dia l'unità del gruppo   (ossia è congruo a   modulo  ). Per la seconda, anche   sta in   ed ha come ordine un divisore di  , infatti  . Quindi,   è pseudoprimo sia in base  , sia in base  .
  2. Consideriamo come a un elemento di  . Sia   il sottoinsieme di   costituito dalle classi il cui resto   modulo   è tale che   è pseudoprimo in base  . Per (1), vale che, se   sta in  , allora   non sta in   (altrimenti   apparterrebbe ad  ). Si ha, dunque, un'applicazione iniettiva  . Dunque, l'ordine di   non supera l'ordine di  .

Esempi e curiositàModifica

Il più piccolo pseudoprimo (di Fermat) in base   è  . Sappiamo che  , quindi   non è primo, ma esso soddisfa il piccolo teorema di Fermat, ossia

 

Un numero pseudoprimo in base   e non in base   è  , e sappiamo che  .

I numeri pseudoprimi in base   si dicono numeri di Poulet o numeri di Sarro o Fermatiani.

Data una base  , 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 EuleroModifica

 Lo stesso argomento in dettaglio: pseudoprimo di Eulero.

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

Sia   un intero, e sia   un intero dispari positivo, non primo, e tale che  . Il numero   è uno pseudoprimo di Eulero in base   se

 

UtilizzoModifica

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,   per i compositi non di Carmichael per il test di Fermat;   per il test di Miller-Rabin), allora la probabilità che un numero composito passi   volte il test è  . Questo non vuol dire che un numero che passi   test sia composito con probabilità  : per il teorema di Bayes, considerando che la probabilità che un numero   sia primo è   e supponendo   molto più grande di  , abbiamo che: la probabilità che un numero che passi   test sia composito è  

Voci correlateModifica

Collegamenti esterniModifica