At2-optimal galois field multiplier for VLSI

Martin Fürer, Kurt Mehlhorn

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

For every prime p, there are AT2-optimal VLSI multipliers for Galois fields GF(pn) in standard notation. In fact, the lower bound AT2 = Ω(n2) is matched for every computation time T in the range [Ω(log n), 0(√n)]. Similar results hold for variable primes p too. The designs are based on the DFT on a structure similar to Fermat rings. For p=2 the DFT uses 3-th instead of 2-th rotts of unity.

Original languageEnglish (US)
Title of host publicationVLSl Algorithms and Architectures - Aegean Workshop on Computing, Proceedings
EditorsKurt Mehlhorn, Fillia Makedon, T. Papatheodorou, P. Spirakis
PublisherSpringer Verlag
Pages217-225
Number of pages9
ISBN (Print)9783540167662
DOIs
StatePublished - 1986
EventAegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC 1986 - Loutrak, Greece
Duration: Jul 8 1986Jul 11 1986

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume227 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherAegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC 1986
Country/TerritoryGreece
CityLoutrak
Period7/8/867/11/86

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'At2-optimal galois field multiplier for VLSI'. Together they form a unique fingerprint.

Cite this