Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Maria De Falco » 13.Condizioni necessarie e condizioni sufficienti per la primalità; forme di pseudoprimalità


Definizione e proprietà del simbolo di Jacobi

Definizione 13.1 
Sia n un numero naturale dispari maggiore o uguale a 3, e sia n=p_1^{\beta _1} \dots p_t^{\beta _t} con p1 ,…, pt primi a due a due distinti e β1 ,…, βt numeri naturali maggiori o uguali a 1.
Se a è un qualunque numero intero, il simbolo di Jacobi (\frac{a}{n}) è definito da
(\frac{a}{n})=(\frac{a}{p_1})^{\beta _1} \dots (\frac{a}{p_t})^{\beta _t}
Proposizione 13.2 
Sia n un numero naturale dispari maggiore o uguale a 3.
Allora qualunque siano i numeri interi a e b, (\frac{ab}{n})=(\frac{a}{n})(\frac{b}{n}).

Definizione e proprietà del simbolo di Jacobi

Dimostrazione 
Segue dalla Definizione 13.1 e dalla Proposizione 12.5.

Proposizione 13.3 
Sia n un numero naturale dispari maggiore o uguale a 3.
Allora (\frac{2}{n})=(-1)^{\frac{n^2-1}{8}}

Dimostrazione

Segue dalla Definizione 13.1 e dalla Proposizione 12.7.

Proposizione 13.4  (Legge di reciprocità quadratica) (senza dimostrazione)
Siano m ed n due numeri naturali dispari maggiori o uguali a 3.
Allora (\frac{m}{n})=(-1)^{\frac{(m-1)(n-1)}{4}}(\frac{n}{m}).

Calcolo del simbolo di Jacobi

Proposizione 13.5  (senza dimostrazione)
Sia n un numero naturale dispari maggiore o uguale a 3.
Allora per ogni a appartenente all’insieme {0 ,…, n-1}, (\frac{a}{n}) può essere calcolato con complessità O((log n)3) senza fattorizzare n.
Sebbene non sia stata presentata la dimostrazione della Proposizione 13.5, si daranno ora dei cenni sul procedimento di calcolo del simbolo di Jacobi.
Sia (\frac{a}{n}) il simbolo di Jacobi da calcolare.
Sia r il resto della divisione euclidea di a per n; allora  (\frac{a}{n})=(\frac{r}{n}).
Si ragionerà su (\frac{r}{n})

Calcolo del simbolo di Jacobi

Se r è pari, e r=2sb con b dispari, allora
(\frac{r}{n})=(\frac{2}{n})^s(\frac{b}{n})=(-1)^{\frac{n^2-1}{8} \cdot s}(\frac{b}{n})
Si ragionerà su (\frac{b}{n}) , in cui b,n sono entrambi dispari e b<n
Per la Proposizione 13.2, (\frac{b}{n})=(-1)^{\frac{(b-1)(n-1)}{4}}(\frac{n}{b})
Si ragionerà su   (\frac{n}{b}) ripetendo tutti i passi fatti su  (\frac{a}{n}).
Proseguendo così, si arriva ad un simbolo di Jacobi in cui i termini sono sufficientemente piccoli da permettere un calcolo diretto.   

Un esempio di calcolo del simbolo di Jacobi

Si calcolerà il simbolo di Jacobi (\frac{66}{151})
(\frac{66}{151})=(\frac{2}{151})(\frac{33}{151})=1 \cdot (\frac{33}{151})
(\frac{33}{151})= 1 \cdot (\frac{151}{33})
Il resto della divisione euclidea di 151 per 33 è 19, e quindi (\frac{151}{33})= (\frac{19}{33})
(\frac{19}{33})= 1 \cdot (\frac{33}{19})
Il resto della divisione euclidea di 33 per 19 è 14, e quindi (\frac{33}{19})= (\frac{14}{19})
(\frac{14}{19})=(\frac{2}{19})(\frac{7}{19})=-1 \cdot (\frac{7}{19})
(\frac{7}{19})=-1 \cdot (\frac{19}{7}) e quindi -1 \cdot (\frac{7}{19}=(\frac{19}{7}))

Un esempio di calcolo del simbolo di Jacobi

Esempio 13.6 

Il resto della divisione euclidea di 19 per 7 è 5, e quindi (\frac{19}{7})= (\frac{5}{7})
(\frac{5}{7})=1\cdot (\frac{7}{5})
Il resto della divisione euclidea di 7 per 5 è 2, e quindi (\frac{7}{5})= (\frac{2}{5})=-1
Quindi  (\frac{66}{151})= -1

Alcune proprietà dei numeri primi

Osservazione  
Sia p un numero primo dispari. Se a è un numero intero tale che a2≡1 (mod p), allora a≡±1 (mod p).
Dimostrazione 
L’asserto segue dal fatto che Zp* è ciclico di ordine pari, sicché [-1]p è il suo unico elemento di periodo 2.

Alcune proprietà dei numeri primi

Teorema 13.7 
Sia p un numero primo dispari. Allora
(1) per ogni numero intero b tale che p non divide b, si ha che bp-1≡1 (mod p).
(2) per ogni numero intero b, si ha che (\frac{b}{p})\equiv b^{\frac{p-1}{2}} \; (mod \; p).
(3) sia p-1=2s t con t dispari; per ogni numero intero b tale che p non divide b, si ha che bt ≡1 (mod p) oppure esiste r appartenente a {0 ,…, s-1} tale che b^{2^rt} ≡ -1 (mod p).
Dimostrazione 
(1) Segue dal Teorema di Fermat-Eulero.
(2) Cfr. Proposizione 12.3.
(3) Si supponga che sia b^t \not\equiv-1\; (mod\; p), e sia
X=\{ j\in  {0 ,..., s} \; \vert \;  b^{2^jt}\not\equiv 1 \;  (mod \; p) \}
⇒ 0єX e s∉X (perché b^{2^st}=b^{p-1}\equiv  1 \; (mod \; p)) .
Sia r=max X
⇒ (b^{2^rt})^2=b^{2^{r+1}t}\equiv 1 \; (mod \; p))
⇒ b^{2^rt} \equiv \pm 1 \; (mod \; p) (perché [-1]p è l’unico elemento di periodo 2 di Zp*)
⇒ b^{2^rt}\equiv -1 \; (mod \; p)

Una condizione necessaria e sufficiente per la primalità

Il Teorema 13.7 fornisce delle condizioni necessarie perché un numero dispari sia primo. Si enuncerà ora un teorema che fornisce una condizione necessaria e sufficiente.
Teorema 13.8 (Teorema di Wilson
Sia n un numero naturale maggiore o uguale a 2.
Allora n è primo se e solo se (n-1)!+1 ≡0 (mod n).
Dimostrazione
Sia n un numero primo, e si supponga che sia n≥5; allora, l’insieme costituito dalle n-3 classi di congruenza [n-2]n ,[n-3]n ,…,[2]n contiene per ogni classe il suo inverso in Zn*
⇒ [n-2]n∙[n-3]n∙…∙[2]n =[1]n  e quindi [(n-1)!]n =[n-1]n cioè (n-1)! ≡(n-1) (mod n)
⇒ (n-1)!+1 ≡0 (mod n).
Viceversa si supponga che (n-1)!+1 ≡0 (mod n)⇒ (n-1)!+1 è un multiplo di n.
Se n non fosse primo, avrebbe un divisore d tale che 1<d<n, e d dividerebbe sia (n-1)!+1  che  (n-1)!, una contraddizione.

Una condizione sufficiente per la primalità

Si enuncerà ora un teorema che fornisce una condizione sufficiente, legata alla teoria della curve ellittiche, perché un numero dispari sia primo.
Teorema 13.9 (senza dimostrazione
Sia n un numero naturale positivo dispari.
Si supponga che esistano numeri naturali a,b,m,q,u,v che verifichino le seguenti condizioni:
(1) (4a3+27b2,n)=1
(2) q è un numero primo che divide m e tale che
q>(n^{\frac{1}{4}}+1)^2
(3) Posto E={(σ,τ) є Zn2 | τ23+[a]nσ+[b]n}U{Ω}, dove Ω è un ente non appartenente a Zn2, si ha che P=([u]n,[v]n) è un elemento di E e, utilizzando le formule per il calcolo dei multipli nelle curve ellittiche, si ottiene  mP=Ω e \frac{m}{q}P ben definito e diverso da Ω.
Allora n è primo.

Una condizione necessaria e sufficiente per la primalità (AKS)

Teorema 13.10 
Sia n un numero naturale maggiore o uguale a 2, e sia a un numero coprimo con n.
Allora n è primo se e solo se in Zn[x] si ha (x+[a]n)n=xn+[a]n .
Dimostrazione 
Se n è primo, allora, per il Piccolo Teorema di Fermat, an ≡a (mod n)
⇒ (x+[a]n)n = xn+([a]n)n = xn+[a]n
Viceversa si supponga che (x+[a]n )n=xn+[a]n .
Si tenga presente che
\left(x+[a]_n\right)^n= \sum _{j=0, \dots ,n}\left(\begin{array}{c}n \\ j\end{array}\right)([a]_n)^{n-j}x^j.

Una condizione necessaria e sufficiente per la primalità (AKS)

Si supponga per assurdo che n non sia primo, e sia q un primo che divide n

⇒ 1<q<n ⇒ \left(\begin{array}{c}n \\ q\end{array}\right) \left([a]_n\right)^{n-q}=[0]_n
⇒ n divide \left(\begin{array}{c}n \\ q \end{array}\right)a^{n-q}
⇒ n divide \left(\begin{array}{c}n \\ q\end{array}\right)=\frac{n(n-1) \dots (n-(q-1))}{q!}.
Sia qk la massima potenza di q che divide n⇒ qk+1 divide n(n-1)…(n-(q-1))
⇒ esiste i tale che 1≤i≤q-1 e q divide n-i: questa contraddizione prova l’asserto.

Il Teorema di Agrawal, Kayal, Saxena

Teorema 13.10 (Agrawal, Kayal, Saxena, 2003) (senza dimostrazione)
Sia n un numero naturale maggiore o uguale a 3, e sia r un numero naturale coprimo con n tale che il periodo di [n]r in Zr* sia maggiore di (log2 n)2.
Allora n è primo se e solo se valgono le seguenti condizioni:
(1) n non è una “potenza perfetta”
(2) n non ha divisori primi minori o uguali ad r
(3) per ogni intero positivo a tale che a< \sqrt r log_2 n, esistono polinomi g(x),h(x) appartenenti a Z[x] tali che (x+a)n-(xn+a)=(xr-1)h(x)+ng(x)  

Pseudoprimalità

Definizione 13.11  
Sia n un numero composto dispari, e sia b un numero intero coprimo con n. Allora
(1) Si dice che n è uno pseudoprimo rispetto (alla base) b se bn-1 ≡1 (mod n).
(2) Si dice che n è uno pseudoprimo di Eulero rispetto (alla base) b se (\frac{b}{n})\equiv b^{\frac{n-1}{2}} (mod n).
(3) Si dice che n è uno pseudoprimo forte rispetto (alla base) b se, posto n-1=2s t con t dispari, si ha che bt ≡1 (mod n) oppure esiste r appartenente a {0 ,…, s-1} tale che b^{2^rt} ≡ -1 (mod n).
Si noti che è immediato verificare che sia la condizione di pseudoprimalità di Eulero che la condizione di pseudoprimalità forte implicano la condizione di pseudoprimalità.
Vale la seguente proposizione:
Proposizione 13.12 (senza dimostrazione)
Sia n un numero composto dispari, e sia b un numero intero coprimo con n. Se n è pseudoprimo forte rispetto alla base b, allora n è pseudoprimo di Eulero rispetto alla base b.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion