Cryptology ePrint Archive: Report 2016/979

The Reason Why Some Divide-and-Conquer Algorithms Cannot Be Efficiently Implemented

Zhengjun Cao, 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.

Category / Keywords: foundations /

Date: received 10 Oct 2016

Contact author: caozhj at shu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20161015:190328 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]