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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2016/979}},
      url = {https://eprint.iacr.org/2016/979}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.