Karatsuba-like formulae and their associated techniques


CENK M.

JOURNAL OF CRYPTOGRAPHIC ENGINEERING, vol.8, no.3, pp.259-269, 2018 (Journal Indexed in ESCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 8 Issue: 3
  • Publication Date: 2018
  • Doi Number: 10.1007/s13389-017-0155-8
  • Title of Journal : JOURNAL OF CRYPTOGRAPHIC ENGINEERING
  • Page Numbers: pp.259-269
  • Keywords: Polynomial multiplication, Karatsuba algorithm, Cryptographic computation, Chinese remainder theorem, EFFICIENT MULTIPLICATION, 5-TERM, 6-TERM

Abstract

Efficient polynomial multiplication formulae are required for cryptographic computation. From elliptic curve cryptography to homomorphic encryption, many cryptographic systems need efficient multiplication formulae. The most widely used multiplication formulae for cryptographic systems are the Karatsuba-like polynomial multiplication formulae. In this paper, these formulae and Montgomery's work yielding more efficient such formulae are introduced. Moreover, recent efforts to improve these results are discussed by presenting associated techniques. The state of art for this area is also discussed.