A String Reconstruction Algorithm and Its Application to Exponentiation Problems
Jeong Seop Sim, Mun‐Kyu Lee, Dong-Kyue Kim · Jeongbo gwahaghoe nonmunji. si'seu'tem mich i'lon · 2008
Most string problems and their solutions are relevant to diverse applications such as pattern matching, data compression, recently bioinformatics, and so on. However, there have been few works on the relations between string problems and cryptographic problems. In this paper, we consider the following string reconstruction problems and show how these problems can be applied to cryptography. Given a string x of length n over a constant-sized alphabet and a set W of strings of lengths at most an integer , the first problem is to find the sequence of strings in W that reconstruct x by the minimum number of concatenations. We propose an O(kn+L)-time algorithm for this problem, where L is the sum of all lengths of strings in a given set, using suffix trees and a shortest path algorithm for directed acyclic graphs. The other is a dynamic version of the first problem and we propose an -time algorithm. Finally, we show that exponentiation problems that arise in cryptography can be successfully reduced to these problems and propose a new solution for exponentiation.