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

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
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 withzeta, 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 Euclidean algorithm, and taking time O(nsdot M(n)), where M(n) denotes the complexity of multiplying n bit integers. The new algorithms have applications in practical primality tests and the implementation of cryptographic protocols.
Original languageEnglish
Title of host publicationFundamentals of Computation Theory
EditorsAndrzej Lingas, Bengt J. Nilsson
Number of pages8
PublisherSpringer
Publication year2003
Pages109-117
ISBN (print)978-3-540-40543-6
DOIs
Publication statusPublished - 2003
EventInternational Symposium on Fundamentals of Computation Theory - Malmö, Sweden
Duration: 12 Aug 200315 Aug 2003
Conference number: 14

Conference

ConferenceInternational Symposium on Fundamentals of Computation Theory
Nummer14
LandSweden
ByMalmö
Periode12/08/200315/08/2003
SeriesLecture Notes in Computer Science
Volume2751
ISSN0302-9743

See relations at Aarhus University Citationformats

ID: 281359