Test di primalità

(Pywikibot v.2)
 
Riga 1: Riga 1:
Esistono dei test probabilistici per testare  se <math>n</math> è primo.
+
Esistono dei test probabilistici per testare  se <math>n</math> è primo.{{InizioDefinizione|titolo=394 Pseudo-primo}}
 
 
 
 
{{InizioDefinizione|titolo=394 Pseudo-primo}}
 
 
<math>n</math> si dice uno ''pseudo-primo'' rispetto alla base <math>b</math> se <math>b^{n-1} \equiv 1 \mod n</math>, dove <math>0<b<n</math>, e se <math>M.C.D.(b,n)=1</math>.
 
<math>n</math> si dice uno ''pseudo-primo'' rispetto alla base <math>b</math> se <math>b^{n-1} \equiv 1 \mod n</math>, dove <math>0<b<n</math>, e se <math>M.C.D.(b,n)=1</math>.
 
{{FineDefinizione}}
 
{{FineDefinizione}}
 
 
 
  
 
''Passi del test di primalità'':
 
''Passi del test di primalità'':
 
 
#Scegli <math>b</math> con <math>0<b<n</math> e calcola <math>d=M.C.D.(b,n)</math>.
 
#Scegli <math>b</math> con <math>0<b<n</math> e calcola <math>d=M.C.D.(b,n)</math>.
 
#Se <math>d</math> è diverso da 1, <math>n</math> non è primo (costo di <math>\log n</math> operazioni).
 
#Se <math>d</math> è diverso da 1, <math>n</math> non è primo (costo di <math>\log n</math> operazioni).
Riga 22: Riga 15:
 
Quindi se questo non avviene il numero non è primo. Tuttavia se si ha <math>b^{n-1} \equiv 1 \mod n</math>, non è detto che il numero sia primo.
 
Quindi se questo non avviene il numero non è primo. Tuttavia se si ha <math>b^{n-1} \equiv 1 \mod n</math>, non è detto che il numero sia primo.
  
 
+
Ci sono numeri che risultano pseudoprimi per qualsiasi base <math>b</math> anche se non sono numeri primi.{{InizioDefinizione|titolo=395 Primo di Carmichael}}
Ci sono numeri che risultano pseudoprimi per qualsiasi base <math>b</math> anche se non sono numeri primi.
 
 
 
 
 
{{InizioDefinizione|titolo=395 Primo di Carmichael}}
 
 
Un numero <math>n</math> si dice ''primo di Carmichael'' se <math>n</math> è pseudoprimo rispetto a ogni <math>b</math> con <math>0<b<n</math>.
 
Un numero <math>n</math> si dice ''primo di Carmichael'' se <math>n</math> è pseudoprimo rispetto a ogni <math>b</math> con <math>0<b<n</math>.
 
{{FineDefinizione}}
 
{{FineDefinizione}}
Riga 40: Riga 29:
 
{{InizioDimostrazione}}
 
{{InizioDimostrazione}}
 
Dimostro il punto 2 del lemma: Siano <math>b_1,\dots,b_t</math> tutte le basi per cui <math>n</math> è pseudoprimo, e sia <math>c</math> una base per cui <math>n</math> non è pseudoprimo. Allora
 
Dimostro il punto 2 del lemma: Siano <math>b_1,\dots,b_t</math> tutte le basi per cui <math>n</math> è pseudoprimo, e sia <math>c</math> una base per cui <math>n</math> non è pseudoprimo. Allora
<math display="block">b_i^{n-1} \equiv 1 \mod n.</math>
+
<math display="block">b_i^{n-1} \equiv 1 \mod n.</math>Considero i numeri <math>c b_1, c b_2, \dots, c b_t</math>, allora <math>n</math> non è pseudoprimo per nessuno di queste basi, che sono almeno <math>t</math>.
Considero i numeri <math>c b_1, c b_2, \dots, c b_t</math>, allora <math>n</math> non è pseudoprimo per nessuno di queste basi, che sono almeno <math>t</math>.
 
 
Questo mostra che il numero di basi per cui <math>n</math> non è pseudoprimo è almeno quanto il numero di basi per cui <math>n</math> è pseudoprimo.  
 
Questo mostra che il numero di basi per cui <math>n</math> non è pseudoprimo è almeno quanto il numero di basi per cui <math>n</math> è pseudoprimo.  
 
Sia <math>s</math> il numero di basi per cui <math>n</math> non è pseudoprimo. Allora <math>s \ge t</math>, inoltre <math>s+t = \phi(n)</math>, perché <math>s+t</math> è il numero totale di elementi  
 
Sia <math>s</math> il numero di basi per cui <math>n</math> non è pseudoprimo. Allora <math>s \ge t</math>, inoltre <math>s+t = \phi(n)</math>, perché <math>s+t</math> è il numero totale di elementi  

Versione delle 15:28, 17 feb 2017

Esistono dei test probabilistici per testare se è primo.
Definizione

si dice uno pseudo-primo rispetto alla base se , dove , e se .

 

Passi del test di primalità:

  1. Scegli con e calcola .
  2. Se è diverso da 1, non è primo (costo di operazioni).
  3. Se , calcolo .
  4. Se , restituisce " non primo".
  5. Se , restituisci " è pseudoprimo rispetto alla base ".


Questo test funziona perché, se fosse primo, si avrebbe . Per Eulero-Fermat, con coprimi, si avrebbe , quindi . Quindi se questo non avviene il numero non è primo. Tuttavia se si ha , non è detto che il numero sia primo.

Ci sono numeri che risultano pseudoprimi per qualsiasi base anche se non sono numeri primi.
Definizione

Un numero si dice primo di Carmichael se è pseudoprimo rispetto a ogni con .

 

Lemma sugli pseudoprimi

Lemma (396)

Sia un numero naturale, allora

  1. se è pseudoprimo rispetto alle basi , allora è pseudoprimo rispetto alla base
  2. se esiste una base per cui non è uno pseudoprimo, allora ce ne sono almeno con tale proprietà.
 
Dimostrazione

Dimostro il punto 2 del lemma: Siano tutte le basi per cui è pseudoprimo, e sia una base per cui non è pseudoprimo. Allora

Considero i numeri , allora non è pseudoprimo per nessuno di queste basi, che sono almeno . Questo mostra che il numero di basi per cui non è pseudoprimo è almeno quanto il numero di basi per cui è pseudoprimo. Sia il numero di basi per cui non è pseudoprimo. Allora , inoltre , perché è il numero totale di elementi coprimi con . Unendo le due equazioni e , si ha , cioè .

 


Lemma (397)
  1. Se è primo di Carmichael, allora è senza quadrati (come i numeri utilizzati nel protocollo RSA).
  2. è primo di Carmichael se e solo se per ogni divisore primo di ;
  3. se è primo di Carmichael, allora è divisibile per almeno tre primi.
 


Esempio

. . I divisori primi di sono , e si ha che dividono , cioè per ogni divisore , e quindi è il più piccolo primo di Carmichael. Senza conoscere la fattorizzazione di , basta estrarne la radice cubica e verificare se ha divisori.

 
 PrecedenteSuccessivo