Paper 2009/636
Obtaining More Karatsuba-Like Formulae over The Binary Field
Haining Fan, Ming Gu, 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.
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]
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. unpublished
- Keywords
- number theoryKaratsuba algorithmpolynomial multiplicationChinese remainder theoremMontgomery algorithm
- Contact author(s)
- fhn @ tsinghua edu cn
- History
- 2010-06-28: revised
- 2010-01-01: received
- See all versions
- Short URL
- https://ia.cr/2009/636
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2009/636,
author = {Haining Fan and Ming Gu and Jiaguang Sun and Kwok-Yan Lam},
title = {Obtaining More Karatsuba-Like Formulae over The Binary Field},
howpublished = {Cryptology {ePrint} Archive, Paper 2009/636},
year = {2009},
url = {https://eprint.iacr.org/2009/636}
}
