Digit set efficienti per la moltiplicazione scalare su curve ellittiche

In this thesis we describe a method to perform scalar multiplication on two classes of ordinary elliptic curves, namely $E: y^2 = x^3 + Ax$ in prime characteristic $p\equiv 1$ mod 4, and $E: y^2 = x^3 + B$ in prime characteristic $p\equiv 1$ mod 3, whose endomorphism rings are isomorphic to the ring of Gaussian integers $Z[i]$, and the ring of Eisenstein integers $Z[(-1+\sqrt{-3})/2]$ respectively. In order to optimise scalar multiplication, we consider a $w$-NAF (non-adjacent form) digit expansion of positive integers to the complex base of $\tau$, where $\tau$ is a zero of the characteristic polynomial $x^2 - tx + p$ of the Frobenius endomorphism associated to the curve. We provide a precomputationless algorithm by means of a convenient factorisation of the unit group of residue classes modulo $\tau$ in the endomorphism ring. We create a digit set that consists of powers of subgroup generators, which are chosen as efficient endomorphisms of the curve.

In questa tesi descriveremo un metodo per eseguire la moltiplicazione scalare su due classi di curve ellittiche ordinarie, ovvero $E: y^2 = x^3 + Ax$ in caratteristica prima $p\equiv 1$ mod 4 ed $E: y^2 = x^3 + B$ in caratteristica prima $p\equiv 1$ mod 3, i cui anelli degli endomorfismi sono isomorfi rispettivamente all'anello degli interi di Gauss $Z[i]$ e all'anello degli interi di Eisenstein $Z[(-1+\sqrt{-3})/2]$. Al fine di ottimizzare la moltiplicazione scalare considereremo un'espansione $w$-NAF (non-adjacent form) di interi positivi nella base complessa $\tau$, dove $\tau$ è uno zero del polinomio caratteristico $x^2 - tx + p$ dell'endomorfismo di Frobenius associato alla curva. Definiremo un algoritmo senza precomputazione grazie ad un'opportuna fattorizzazione del gruppo delle unità delle classi di resto modulo $\tau$ nell'anello degli endomorfismi. Costruiremo un digit set che consisterà di potenze dei generatori dei sottogruppi, i quali saranno scelti come endomorfismi efficienti della curva.