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
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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

(4a3+27b2,n)=1  e  [v]n2=[u]n3+[a]n[u]n+[b]n

(2) Si pone E={(σ,τ) є Zn2 | τ23+[a]nσ+[b]n}U{Ω}, dove Ω è un ente non appartenente a Zn2

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  q1=q ,…, qt tali che per ciascun qi esistono numeri naturali ai ,bi ,mi ,ui ,vi tali che:

(a) ai ,bi ,mi ,qi+1, ui ,vi verificano le condizioni (1)-(3) del Teorema 18.4

(b) |mi-(qi+1)|≤2\sqrt {q_i}

(c)  qt è sufficientemente piccolo da poter verificare che qt è certamente primo

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

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

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

(15) i numeri ai , bi , mi , qi , ui , vi 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≤log2n , n^{\frac{1}{h}}
(2) Se per qualche  h≤log2n , n^{\frac{1}{h}} è un numero intero, allora n non è primo
se per ogni h≤log2n , 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((log2n)5), tale che r è il minimo intero positivo per il quale il periodo di [n]r in Zr* è maggiore di  (log2n)2.

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) = xj + 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)n appartenente all’anello quoziente Z[x]/I, dove I è l’ideale generato dal polinomio xr − 1 (si tenga presente che ((x + a) + I)n 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) = (xr − 1)h(x) + ng(x); se
ciò accade, la stessa condizione è verificata dalla differenza (x + a)n − (xn + 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≤log2n , n^{\frac{1}{h}}

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

Si supponga allora che per ogni h≤log2n , 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 4a3+27b2 è multiplo di n, allora si sceglie una nuova coppia (a,b).
  • Si supponga che 4a3+27b2 non sia multiplo di n.
  • Se (4a3+27b2 ,n) è diverso da 1, allora si è individuato un divisore non banale di n.

Si supponga allora che sia (4a3+27b2 ,n)=1,

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

y2=x3+[a]px+[b]p

definisce una curva ellittica su Zp , che indicheremo con Ep .

Si tenga inoltre presente che l’equazione

y2=x3+ax+b

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

Un esempio di fattorizzazione con le curve ellittiche

Si sceglie ora una coppia Q=(u,v) di numeri razionali che verifichino le seguenti condizioni:

(1) Q appartiene ad E (sicchè  Qp =([u]p ,[v]p) è un punto di Ep)

(2) i denominatori di u e v sono coprimi con n.

Si sceglie poi un numero k che sia prodotto di “potenze piccole” di “primi piccoli” e si calcola il multiplo kQ di Q in E.

Per ogni divisore h di k, dopo aver calcolato il multiplo hQ, si applica l’algoritmo delle divisioni successive per calcolare il massimo

comun divisore tra n e ciascuno dei denominatori delle coordinate di hQ.

 

La speranza è che esista un primo p divisore di n tale che k sia multiplo del periodo m di Qp ; se ciò accade, il multiplo mQp di Ep è

l’elemento neutro di Ep , e quindi calcolando  il massimo comun divisore tra n e ciascuno dei denominatori delle coordinate di mQ, si

troverà un divisore non banale di n.

Un esempio di fattorizzazione con le curve ellittiche

Cerchiamo, ad esempio di fattorizzare con questo metodo il numero 39.

Proviamo con a=1 e b=-1.

Si ha (4a3+27b2 ,n)=(31,39)=1

Si userà la curva ellittica E sul campo razionale di equazione y2=x3+x-1.

Si sceglierà il punto Q=(1,1).

Si proverà a fattorizzarlo con k=4.

2Q=2∙(1,1)=(2,-3)

4Q=2(2Q)=2∙(2,-3)=(25/36 , 37/216)

Si calcola il massimo comun divisore tra 39 e 36, che è 3: si è dunque trovato un divisore non banale di 39.

Il risultato ottenuto dipende dal fatto che nella curva ellittica E3, il punto ([2]3 , [-3]3 )=([2]3 , [0]3 ) ha periodo 2.

I materiali di supporto della lezione

Algoritmo di Agrawal-Kayal-Saxena

  • 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