Cryptology ePrint Archive: Report 2009/636

Obtaining More Karatsuba-Like Formulae over The Binary Field

Haining Fan and Ming Gu and Jiaguang Sun and Kwok-Yan Lam

Abstract: The aim of this paper is to find more Karatsuba-like formulae for a fixed set of moduli polynomials in GF(2)[x]. To this end, a theoretical framework is established. We first generalize the division algorithm, and then present a generalized definition of the remainder of integer division. Finally, a previously generalized Chinese remainder theorem is used to achieve our initial goal. As a by-product of the generalized remainder of integer division, we rediscover Montgomery’s N-residue and present a systematic interpretation of definitions of Montgomery’s multiplication and addition operations.

Category / Keywords: foundations / number theory, Karatsuba algorithm, polynomial multiplication, Chinese remainder theorem, Montgomery algorithm,

Publication Info: unpublished

Date: received 29 Dec 2009, last revised 27 Jun 2010

Contact author: fhn at tsinghua edu cn

Available formats: PDF | BibTeX Citation

Note: I received an email from Dr. Ekatherina Karatsuba, A. Karatsuba' daughter, and she told me that the Karatsuba algorithm was found by her father himself. So I added the following information on the 1st page:

which was invented by Karatsuba in 1960 [1]

Version: 20100628:013129 (All versions of this report)

Discussion forum: Show discussion | Start new discussion