Paper 2016/979
The Reason Why Some Divide-and-Conquer Algorithms Cannot Be Efficiently Implemented
Zhengjun Cao and Lihua Liu
Abstract
In the literature there are some divide-and-conquer algorithms, such as Karatsuba's algorithm and Strassen's algorithm, which play a key role in analyzing the performance of some cryptographic protocols and attacks. But we find these algorithms are rarely practically implemented although their theoretical complexities are attractive. In this paper, we point out that the reason of this phenomenon is that decomposing the original problem into subproblems does not take constant time. The type of problem decomposition results in data expand exponentially. In such case the time for organizing data (including assigning address, writing and reading) which is conventionally ignored, accumulates significantly.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Contact author(s)
- caozhj @ shu edu cn
- History
- 2016-10-15: received
- Short URL
- https://ia.cr/2016/979
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2016/979,
author = {Zhengjun Cao and Lihua Liu},
title = {The Reason Why Some Divide-and-Conquer Algorithms Cannot Be Efficiently Implemented},
howpublished = {Cryptology {ePrint} Archive, Paper 2016/979},
year = {2016},
url = {https://eprint.iacr.org/2016/979}
}
