Home

Federica EU

1/14

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 p₁ ,…, p_t primi a due a due distinti e β₁ ,…, β_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)³) 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=2^sb 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 a²≡1 (mod p), allora a≡±1 (mod p).
Dimostrazione
L’asserto segue dal fatto che Z_p* è 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 b^p^-¹≡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=2^st con t dispari; per ogni numero intero b tale che p non divide b, si ha che b^t ≡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 Z_p*)
⇒ $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 Z_n*
⇒ [n-2]_n∙[n-3]_n∙…∙[2]_n=[1]_n e quindi [(n-1)!]_n=[n-1]_ncioè (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) (4a³+27b²,n)=1
(2) q è un numero primo che divide m e tale che
$q>(n^{\frac{1}{4}}+1)^2$
(3) Posto E={(σ,τ) є Z_n² | τ²=σ³+[a]_nσ+[b]_n}U{Ω}, dove Ω è un ente non appartenente a Z_n², 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 Z_n[x] si ha (x+[a]_n)ⁿ=xⁿ+[a]_n .
Dimostrazione
Se n è primo, allora, per il Piccolo Teorema di Fermat, aⁿ≡a (mod n)
⇒ (x+[a]_n)ⁿ= xⁿ+([a]_n)ⁿ = xⁿ+[a]_n
Viceversa si supponga che (x+[a]_n)ⁿ=xⁿ+[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 q^k la massima potenza di q che divide n⇒ q^k+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 Z_r* sia maggiore di (log₂n)².
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)ⁿ-(xⁿ+a)=(x^r-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 b^n-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=2^st con t dispari, si ha che b^t ≡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.