Efficient Algorithms for gcd and Cubic Residuosity in the Ring of Eisenstein Integers

Ivan B. Damgård
Gudmund Skovbjerg Frandsen

February 2003


We present simple and efficient algorithms for computing gcd and cubic residuosity in the ring of Eisenstein integers, ${\bf Z}[\zeta]$, i.e. the integers extended with $\zeta$, a complex primitive third root of unity. The algorithms are similar and may be seen as generalisations of the binary integer gcd and derived Jacobi symbol algorithms. Our algorithms take time $O(n^2)$ for $n$ bit input. This is an improvement from the known results based on the Euclidian algorithm, and taking time $O(nĚ M(n))$, where $M(n)$ denotes the complexity of multipliplying $n$ bit integers. The new algorithms have applications in practical primality tests and the implementation of cryptographic protocols. The technique underlying our algorithms can be used to obtain equally fast algorithms for gcd and quartic residuosity in the ring of Gaussian integers, ${\bf Z}[i]$

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.