Fattorizzazione e Test di Primalità con Curve Ellittiche

Le questioni della primalità e della fattorizzazione non sono poi così indipendenti ma, anzi, intervengono l’una nell’altra. Abbiamo già detto che l’applicazione di un algoritmo di fattorizzazione su un intero n avviene dopo aver stabilito tramite un test di primalità se questo è primo o composto.
Tuttavia, durante lo svolgimento di un test di primalità su n potrebbe essere necessario fattorizzare, anche solo parzialmente, un certo numero richiesto dal test che si sta effettuando.

Il Test di Goldwasser-Kilian e quello di Pocklington-Lehmer, che si può considerare il suo analogo moltiplicativo, sono algoritmi in grado di produrre un certificato di primalità succinto, ovvero una serie di dati che consentono di provare in tempo polinomiale la primalità del numero in esame. Tali dati permettono a chiunque di verificare indipendentemente la primalità di un certo intero basandosi esclusivamente su di essi, evitando perciò di ripetere completamente il test. Nel 1975 V.R. Pratt dimostrò che un tale certificato esiste sempre (e quindi che il problema della primalità appartiene alla classe NP), anche se esso potrebbe non essere prodotto in tempo polinomiale, in quanto si basa sulla fattorizzazione di interi grandi.

Euristicamente, l’ECPP è un test a complessità polinomiale O(log¹¹ n). Nel 2002 M. Agrawal, N. Kayal e N. Saxena hanno definitivamente dimostrato che il problema della primalità appartiene alla classe P, esibendo un test di primalità (test AKS) a complessità polinomiale di O(log^21/2 n) operazioni.
Assumendo vere alcune congetture della teoria analitica dei numeri, la stima della sua complessità potrebbe essere migliorata a O(log⁶ n) operazioni. Un algoritmo interessante dovuto a Qi Cheng combina cicli di ECPP e cicli di AKS.