Research on Quantum Annealing Integer Factorization Based on Different Columns

Abstract

Read online

The majority of scholars believe that Shor’s algorithm is a unique and powerful quantum algorithm for RSA cryptanalysis, so current postquantum cryptography research has largely considered only the potential threats of Shor’s algorithm. This paper verifies the feasibility of deciphering RSA public key cryptography based on D-Wave, which is the second most effective RSA attack method after Shor’s algorithm. This paper proposes the influence of different column methods on the final integer factorization, puts forward a new dimension reduction formula, simplifies the integer factorization model based on quantum annealing, simulates it with the qbsolv quantum computing software environment provided by D-Wave, and factors the integer 1630729 (an 11-bit prime factor multiplied by an 11-bit prime factor). The research results show that choosing an appropriate number of columns and column width in the binary integer factorization multiplication table is very important for studying the optimization ability of the quantum annealing algorithm. In fact, Science, Nature, IEEE Spectrum, and the National Academies of Sciences (NAS) are consistent in asserting that the practical application of general-purpose quantum computers is far in the future. Therefore, although D-Wave computers were initially mainly purchased by Lockheed Martin, Google, etc., for purposes such as image processing, machine learning, combinatorial optimization, and software verification, post quantum cryptography research should further consider the potential of the D-Wave quantum computer in deciphering RSA cryptosystems in the future, and a discussion of this potential is one of the contributions of this paper.

Keywords

• integer factorization
• quantum annealing
• QUBO
• multiplication table
• RSA public key cryptography