Paper 2009/636 Original: eprint.iacr.org/2009/636 ↗
Obtaining More Karatsuba-Like Formulae over The Binary Field
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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2010-06-28: last updated
- 2010-01-01: published
- Short URL
- https://ia.cr/2009/636
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}