Application of Grover's Quantum Search Algorithm to Solve the Transcendental Logarithm Problem
Yi Tang, Shenghui Su · 2014
Transcendental logarithm problem is a new problem which can be used to build signature schemes. Although no polynomial time algorithm or sub-exponential time algorithm has been found to solve this problem, whether it is still an intractable problem with quantum computers is a question. In this paper, we solve the transcendental logarithm problem with improved Grover's quantum search algorithm. In allusion to some characteristics of the transcendental logarithm problem, the average number of the Grover iterations can be reduced to lower the time complexity. The algorithm calls the oracle operator fewer times than before. According to our theoretic analysis and simulation data, cryptosystems based on transcendental logarithm problem can be improved through increasing the length of the key or modifying the original problem by adding suitable parameters to lower the number of solutions.