Home

Federica EU

1/10

Maria De Falco » 16.Test di primalità basato sulle curve ellittiche e test AKS

Test di primalità ECPP

Test di primalità basato sulle curve ellittiche (ECPP)

Sia n un numero naturale dispari maggiore di 3.

(1) Si scelgono dei numeri naturali a,b, u , v tali che

(4a³+27b²,n)=1 e [v]_n²=[u]_n³+[a]_n[u]_n+[b]_n

(2) Si pone E={(σ,τ) є Z_n² | τ²=σ³+[a]_nσ+[b]_n}U{Ω}, dove Ω è un ente non appartenente a Z_n²

Si tenga a questo punto presente che se n è primo, allora l’insieme E e’ una curva ellittica, e quindi tutti gli algoritmi applicabili ad una curva ellittica, se applicati all’insieme E, devono giungere a termine e dare risultati compatibili con la teoria delle curve ellittiche.

Test di primalità ECPP

(3) Si applica all’insieme E un algoritmo che permette di calcolare l’ordine di una curva ellittica.

(4) Se l’algoritmo di cui al punto (3) non giunge a termine, n non è primo

Se l’algoritmo di cui al punto (3) dà come risultato un numero m che non verifica la condizione

$\vert m-(n+1) \vert \leq 2\sqrt n$ , n non è primo

Se l’algoritmo di cui al punto (3) dà come risultato un numero m che verifica la condizione $\vert m-(n+1) \vert \leq 2\sqrt n$ , si procede con il

punto (5)

(5) Si applicano le formule che permettono di calcolare i multipli dei punti di una curva ellittica per calcolare m([u]_n,[v]_n)

Test di primalità ECPP

(6) Se il calcolo di cui al punto (5) non giunge a termine, n non è primo

Se il calcolo di cui al punto (5) dà come risultato un elemento di E diverso da Ω, n non è primo

Se il calcolo di cui al punto (5) dà come risultato Ω, si procede con il punto (7)

(7) Per andare avanti, bisogna trovare un numero “probabilmente primo” che divide m ed è maggiore di $(n^{\frac{1}{4}}+1)^2$
(8) Si supponga di aver trovato un numero q “probabilmente primo” che divide m ed è maggiore di $(n^{\frac{1}{4}}+1)^2$ . Allora si applicano le

formule che permettono di calcolare i multipli dei punti di una curva ellittica per calcolare $\frac{m}{q} ([u]_n ,[v]_n )$

(9) Se il calcolo di cui al punto (8) non giunge a termine, n non è primo

Se il calcolo di cui al punto (8) dà come risultato Ω, bisogna cercare un altro valore di q

Se il calcolo di cui al punto (8) dà come risultato un elemento di E diverso da Ω, si procede con il punto (10)

(10) Per il Teorema 18.4 la risposta è: SE q E’ PRIMO, ALLORA ANCHE n E’ PRIMO

(11) Si applica a q lo stesso algoritmo applicato ad n (cioè i passi da (1) a (10)): si tenga presente che si sta operando su un numero

q che ha le seguenti caratteristiche:

$q \leq \frac{m}{2}$ , mentre $\vert m-(n+1)\vert \leq \sqrt n$

Test di primalità ECPP

Conclusioni

(12) Applicando ripetutamente i passi da (1) a (11), se l’algoritmo giunge a conclusione, si riescono a determinare dei numeri q₁=q ,…, q_t tali che per ciascun q_i esistono numeri naturali a_i ,b_i ,m_i ,u_i ,v_i tali che:

(a) a_i ,b_i ,m_i ,q_i+1, u_i ,v_i verificano le condizioni (1)-(3) del Teorema 18.4

(b) |m_i-(q_i+1)|≤2 $\sqrt {q_i}$

(13) Dalla condizione (a) segue che per ciascun i, se q_i+1 è primo, allora è primo anche q_i ;

dalla condizione (c) segue quindi che n è primo;

(14) si può dimostrare che t=O(log n).

(15) i numeri a_i, b_i , m_i , q_i , u_i , v_i costituiscono un certificato di primalità per n.

Test di primalità AKS

Questo test di primalità è basato sull’applicazione del Teorema 13.6.

AKS sono le iniziali dei cognomi di Manindra Agrawal, Neeraj Kayal, Nitin Saxena, i tre studiosi indiani che nell’estate del 2002

pubblicarono l’algoritmo che stiamo per descrivere.

Sia n un numero naturale dispari maggiore di 3.
(1) Si calcola (e ciò richiede un tempo polinomiale) per ogni h≤log₂n , $n^{\frac{1}{h}}$
(2) Se per qualche h≤log₂n , $n^{\frac{1}{h}}$ è un numero intero, allora n non è primo
se per ogni h≤log₂n , $n^{\frac{1}{h}}$ non è un numero intero, allora n non è una “potenza perfetta”, e si procede con il punto (3)
(3) Si trova un numero r=O((log₂n)⁵), tale che r è il minimo intero positivo per il quale il periodo di [n]_r in Z_r* è maggiore di (log₂n)².

Qui non si descrive il procedimento attraverso il quale si realizza lo step (3), ma è opportuno menzionare il fatto che esso richiede

un tempo polinomiale.

(4) Per ogni numero naturale ≤r si controlla che sia coprimo con n (altrimenti n non è primo).

Test di primalità AKS

(5) Per ogni intero positivo $a < \sqrt{r\log_2 n}$ si opera nel seguente modo: si considerano i polinomi f(x) e k(x) tali che f(x) = x^j + a, dove j è il resto della divisione euclidea di n per r, e k(x) è il polinomio di grado minore di r che si ottiene come rappresentante del laterale ((x + a) + I)ⁿ appartenente all’anello quoziente Z[x]/I, dove I è l’ideale generato dal polinomio x^r − 1 (si tenga presente che ((x + a) + I)ⁿ si calcola con il metodo dei quadrati ripetuti).
Si verifica se esistono polinomi h(x), g(x) ∈ Z[x] tali che k(x) − f(x) = (x^r − 1)h(x) + ng(x); se
ciò accade, la stessa condizione è verificata dalla differenza (x + a)ⁿ − (xⁿ + a), e quindi n è primo per il Teorema 13.10.

La divulgazione dell’algoritmo AKS suscitò subito grande interesse; negli anni successivi sono stati realizzate, allo scopo di

migliorarne l’efficienza, diverse variazioni, alcune delle quali ad opera degli stessi Agrawal, Kayal e Saxena.

Per un approfondimento su questo punto, si veda l’algoritmo di Agrawal-Kayal-Saxena.

Un esempio di fattorizzazione con le curve ellittiche

Le curve ellittiche possono essere utilizzate anche per cercare di fattorizzare un numero che si sa non essere primo.

Sia n un numero composto dispari, del quale si sta cercando un divisore non banale d.

Si supponga che n non sia divisibile né per 2 né per 3.

Si calcola (e ciò richiede un tempo polinomiale) per ogni h≤log₂n , $n^{\frac{1}{h}}$

Se per qualche h≤log₂n , $n^{\frac{1}{h}}$ è un numero intero, allora si è individuato un divisore non banale di n.

Si supponga allora che per ogni h≤log₂n , $n^{\frac{1}{h}}$ non è un numero intero, cioè che n non sia una “potenza perfetta”.

Un esempio di fattorizzazione con le curve ellittiche

Si scelgano ora due numeri interi a e b.

Se 4a³+27b² è multiplo di n, allora si sceglie una nuova coppia (a,b).
Si supponga che 4a³+27b² non sia multiplo di n.
Se (4a³+27b² ,n) è diverso da 1, allora si è individuato un divisore non banale di n.

Si supponga allora che sia (4a³+27b² ,n)=1,

ne segue che per ogni divisore primo p di n, l’equazione

y²=x³+[a]_px+[b]_p

definisce una curva ellittica su Z_p , che indicheremo con E_p .

Si tenga inoltre presente che l’equazione

y²=x³+ax+b

definisce una curva ellittica sul campo razionale, che indicheremo con E.