Paper 2022/921
Low-Delay 4, 5 and 6-Term Karatsuba Formulae in $\mathbb{F}_2[x]$ Using Overlap-free Splitting
Abstract
The overlap-free splitting method, i.e., even-odd splitting and its generalization, can reduce the XOR delay of a Karatsuba multiplier. We use this method to derive Karatsuba formulae with one less XOR delay in each recursive iteration. These formulae need more multiplication operations, and are trade-offs between space and time. We also show that ``finding common subexpressions'' performs better than ``the refined identity'' in 4-term formula: we reduce the number of XOR gates given by Cenk, Hasan and Negre in IEEE T. Computers in 2014.
Note: Add ref. [1], and modify the first sentence as follows: Even-odd splitting of polynomials and its generalization are powerful tools in FFT and Karatsuba algorithms. For example, in 2002, they are used to achieve the optimal cutoff point of Mulders’s short product algorithm under the Karatsuba model [1]; in 2007, they are used to reduce XOR gate delays of VLSI Karatsuba multipliers [2].
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- Karatsuba algorithm polynomial multiplication even-odd splitting overlap-free splitting
- Contact author(s)
- fhn @ tsinghua edu cn
- History
- 2022-07-20: last of 2 revisions
- 2022-07-15: received
- See all versions
- Short URL
- https://ia.cr/2022/921
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/921,
author = {Haining Fan},
title = {Low-Delay 4, 5 and 6-Term Karatsuba Formulae in $\mathbb{F}_2[x]$ Using Overlap-free Splitting},
howpublished = {Cryptology ePrint Archive, Paper 2022/921},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/921}},
url = {https://eprint.iacr.org/2022/921}
}
