Quantum Algorithm for Attacking RSA Based on Fourier Transform and Fixed-Point

摘要

Shor in 1994 proposed a quantum polynomial-time algorithm for finding the order r of an element a in the multiplicative group Z_(n)^(*),which can be used to factor the integer n by computing gcd(a^(r/2)±1,n),and hence break the famous RSA cryptosystem.However,the order r must be even.This restriction can be removed.So in this paper,we propose a quantum polynomial-time fixed-point attack for directly recovering the RSA plaintext M from the ciphertext C,without explicitly factoring the modulus n.Compared to Shor’s algorithm,the order r of the fixed-point C for RSA(e,n)satisfying C^(er)≡C(mod n)does not need to be even.Moreover,the success probability of the new algorithm is at least 4φ(r)/π^(2)r and higher than that of Shor’s algorithm,though the time complexity for both algorithms is about the same.