Utente:Francesco.morerio/Test

I Test di primalità con curve ellittiche sono tra le tecniche attualmente più utilizzate per determinare se un numero è primo. L’idea originale è contenuta in un articolo di Shafi Goldwasser e Joe Kilian del 1986. L’algoritmo è stato poi migliorato da Atkin e Morain nel 1992, aggirando il problema di determinare la cardinalità della curva ellittica utilizzata. A differenza di molti test probabilistici, quelli su curve ellittiche dimostrano l’effettiva primalità o compositezza di un dato numero. Rappresentano inoltre una valida alternativa al test di primalità di Pocklington, che ha il difetto di essere difficilmente implementabile in pratica. In effetti i test si basano su un criterio analogo al test di Pocklington, con la differenza che il gruppo $(\mathbb {Z} /n\mathbb {Z} )^{*}$ è sostituito da $E(\mathbb {Z} /n\mathbb {Z} )$, dove E è un’opportuna curva ellittica.

Test di Pocklington

Sia N un intero positivo. Sia q un primo che divide N - 1 tale che $q>N^{1/2}-1$. Se esiste un intero a tale che:

1. $a^{N-1}\equiv 1(modN)$
2. $\gcd {(a^{(N-1)/q}-1,N)}=1$

Allora N è primo.

Dimostrazione

Se per assurdo N non fosse primo, esisterebbe un primo p che divide N tale da risultare $p\leq {\sqrt {N}}$.
Dato che $q>p-1$ segue che q e p-1 sono coprimi e quindi dall’Identità di Bézout deduciamo l'esistenza di un intero u tale che $uq\equiv 1\ mod(p-1)$.
Segue che

$a^{(N-1)/q}\equiv a^{uq(N-1)/q}\equiv a^{u(N-1)}\equiv 1\ mod(p)$

per la condizione 1. Questo però contraddice la 2. Assurdo.

La prossima proposizione è l’analogo del criterio di Pocklington per le curve ellittiche e costituisce la base per l'algoritmo nella forma di Goldwasser-Kilian.

Proposizione

Sia N un intero positivo, ed E l'insieme dei punti definito dall’equazione: $y^{2}=x^{3}+ax+b$ tale che la cubica a destra non abbia radici multiple. Si consideri poi E modulo N, cioè su $\mathbb {Z} /N\mathbb {Z}$, in cui definiamo l'operazione di gruppo (in notazione additiva) nel modo usuale.
Sia inoltre $O$ l’elemento neutro (o punto all’infinito) di E.
Sia m un intero.
Se esiste un primo q che divide m, e tale che $m>(N^{1/4}+1)^{2}$ ed esiste un punto P su E tale che:

1. $mP=O$
2. $(m/q)P\neq O$ (oltre che definito).

Allora N è primo.

Dimostrazione

Se per assurdo N non fosse primo, allora esisterebbe un primo

$p\leq {\sqrt {N}}$ che divide N.

Sia $E^{\prime }$ la curva ellittica definita tramite la stessa equazione di E ma considerata modulo p invece che modulo N. Sia $m^{\prime }$ l’ordine del gruppo $E^{\prime }$. Dal teorema di Hasse sappiamo che:

$m^{\prime }\leq p+1+2{\sqrt {p}}=({\sqrt {p}}+1)^{2}\leq (N^{1/4}+1)^{2}<q$

e quindi

$\gcd {(q,m^{\prime })}=1$.

Dall’Identità di Bézout deduciamo l’invertibilità di q modulo $m\prime$ ovvero l’esistenza di un u tale che:

$uq\equiv 1{\pmod {m^{\prime }}}$.

Sia $P^{\prime }\in E^{\prime }$ il punto P preso modulo p. Allora su $E^{\prime }$ si ha:

$(m/q)P^{\prime }=uq(m/q)P^{\prime }=umP^{\prime }=O\,$.

per la (1), dato che $mP^{\prime }$ è ottenuto nello stesso modo di $mP$, solo modulo p al posto che modulo N (e per l’ipotesi d’assurdo p divide N).

Ma questo è assurdo perchè deve valere (2): se (m/q)P è definito e diverso da O (mod N), allora lo stesso procedimento ma modulo p invece che modulo N dovrebbe dare come risultato $(m/q)P^{\prime }\neq O$.

Algoritmo Goldwasser–Kilian

Dall'ultima proposizione segue un algoritmo per determinare se un numero N è primo.

• Per prima cosa si scelgono tre interi casuali, a, x, y e si pone

$b\equiv y^{2}-x^{3}-ax{\pmod {N}}$

• P = (x,y) è un punto su E, dove E è definita da $y^{2}=x^{3}+ax+b$.

• Abbiamo bisogno di un algoritmo per determinare il numero di punti di E. Applicato ad E, questo algoritmo (ad esempio l'algoritmo di Schoof) produce un numero m che corrisponde effettivamente al numero di punti di E, a patto che N sia primo.
• Successivamente si applica un criterio per decidere se la curva ellittica che abbiamo scelto è accettabile. Se si può scrivere m nella forma $m=kq$ dove $k\geq 2$ è un intero piccolo e q è probabilmente primo (nel senso che ha superato con successo qualche altro test di primalità), allora teniamo la curva E. Se invece non fosse possibile scrivere m in questa particolare forma, allora dovremmo scegliere (a, x, y) casuali e ricominciare dall’inizio l’algoritmo.
• Posto che siamo in grado di scegliere una curva che soddisfa il criterio appena esposto, si procede calcolando mP and kP. Se a un certo punto del calcolo si incontra un espressione non definita (nella formula per i multipli di P o durante l’algoritmo di Schoof per contare i punti di E), allora immediatamente avremmo un fattore non banale di N (cioè avremmo risposta negativa al test di primalità).
• Se $mP\neq O$ allora è chiaro che N non è primo, perché se N fosse primo allora E avrebbe ordine m e quindi ogni elemento di E darebbe O se moltiplicato per m. Se kP = O, cosa molto improbabile, dobbiamo cominciare da capo con un’altra tripla (a, x, y).
• Ora se $mP=O$ e $kP\neq O$ la proposizione ci dice che N è primo, ammesso che q lo sia. La primalità di q si può verificare con lo stesso algoritmo: si innesta così una procedura ricorsiva dove la primalità di N può essere provata tramite la primalità di q e probabili primi sempre più piccoli finché non si raggiungono dei primi certi.

Problemi nell’implementazione

Secondo Atkine Morain il problema Goldwasser–Kilian è che l’algoritmo di Schoof sembra quasi impossibile da implementare . In effetti l’algoritmo originale di Schoof non è abbastanza efficiente per fornire il numero di punti in un tempo breve. Una variante di questo metodo è stata sviluppata da A. O. L. Atkin e sfrutta il fatto che su opportune curve ellittiche con moltiplicazione complessa è molto più facile calcolare il numero di punti.

Un secondo problema, più teorico, è la difficoltà di trovare E il cui numero di punti è della forma kq, come prescritto dall'algoritmo. Non c’è nessun teorema noto che garantisca di trovare una tale E in un tempo polinomiale. Per esserne certi, bisognerebbe conoscere qualcosa in più sulla distribuzione dei primi nell'intervallo:

$[p+1-2{\sqrt {p}}\ ,\ p+1+2{\sqrt {p}}]$,

che sappiamo contenere m per il teorema di Hasse. L'analisi dei tempi di esecuzione dell'algoritmo si basa proprio su congetture (per la verità altamente probabili) su questa distribuzione.

Tempo di esecuzione

L'algoritmo Goldwasser-Kilian termina in un tempo polinomiale con probabilità

$1-O\left(2^{-n{\frac {1}{\log \log n}}}\right)$

Prima Congettura

Sia $\pi (x)$ il numero di primi più piccoli di x

$\exists \ c_{1},c_{2}>0:\ \pi (x+{\sqrt {x}})-\pi (x)\geq {\frac {c_{2}{\sqrt {x}}}{\log ^{c_{1}}x}}$

per x sufficientemente grande.

Dando per dimostrata questa congettura, allora l'algoritmo Goldwasser–Kilian ha un tempo di esecuzione atteso polinomiale per ogni input. Inoltre, se N è di lunghezza k, allora l'algoritmo crea un certificato di dimensione O$(k^{2})$ che può essere verificato in O$(k^{4})$.

La seguente congettura invece dà un limite superiore al tempo di esecuzione totale dell'algoritmo.

Seconda congettura

Supponiamo esistano due costanti positive $c_{1}$ and $c_{2}$ tali che il numeri di primi nell'intervallo

$[x,x+{\sqrt {2x}}]\ ,\ x\geq 2$

sia maggiore di

$c_{1}{\sqrt {x}}(\log x)^{-c_{2}}$

Allora l'algoritmo Goldwasser-Kilian dimostra la primalità di N in un tempo

$O(\log n)^{10+c_{2}}$