A non-redundant and efficient architecture for Karatsuba-Ofman algorithm

Nam Su Chang, Chang Han Kim, Young Ho Park, Jongin Lim

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

10 Citations (Scopus)


The divide-and-conquer method is efficiently used in parallel multiplier over finite field GF(2n). Leone proposed optimal stop condition for iteration of Karatsuba-Ofman algorithm (KOA). Multi-segment Karatsuba method (MSK) is proposed by Ernst et al. In this paper, we propose a Non-Redundant Karatsuba-Ofman algorithm (NRKOA) with removing redundancy operations, and design a parallel hardware architecture based on the proposed algorithm. Comparing with existing related Karatsuba architectures with the same time complexity, the proposed architecture reduces the area complexity. The proposed NRKOA multiplier has more efficient the space complexity than the previous KOA multipliers, where n is a prime. Furthermore, the space complexity of the proposed multiplier is reduced by 43% in the best case.

Original languageEnglish
Title of host publicationInformation Security - 8th International Conference, ISC 2005, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)354029001X, 9783540290018
Publication statusPublished - 2005
Event8th International Conference on Information Security, ISC 2005 - Singapore, Singapore
Duration: 2005 Sept 202005 Sept 23

Publication series

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


Other8th International Conference on Information Security, ISC 2005


  • Hardware Architecture
  • Karatsuba-Ofman Algorithm
  • Non-Redundant Karatsuba-Ofman Algorithm
  • Polynomial Multiplication

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'A non-redundant and efficient architecture for Karatsuba-Ofman algorithm'. Together they form a unique fingerprint.

Cite this