Quantum Annealing Advances Integer Factorisation and RSA Cryptosystem Security.

Researchers demonstrate integer factorisation using quantum annealing, achieving accurate results for semiprimes up to 60 bits, including N = 1152921423002469787. High order unconstrained binary optimisation models factor smaller numbers but lack scalability, while constrained quadratic models offer improved performance and consistency.

The security of much modern digital communication relies upon the computational difficulty of factoring large numbers into their prime constituents, a principle underpinning the widely used RSA encryption algorithm. Recent advances in quantum computation present a potential challenge to this established cryptographic standard, prompting investigation into novel quantum approaches to integer factorisation. Researchers at Chungbuk National University and QTomo now detail a quantum annealing based method for prime factorisation, utilising both high order unconstrained binary optimisation (HUBO) and constrained quadratic model (CQM) formulations to represent the mathematical problem in a form suitable for quantum solvers. Arim Ryou, Kiwoong Kim, and Kyungtaek Jun, alongside colleagues at the Chungbuk Quantum Research Center, present their findings in the article, “Quantum prime factorization algorithms using binary carry propagation”, demonstrating successful factorisation of semiprimes up to 60 bits utilising a CQM approach with constraint relaxation and global product consistency, and outlining the scalability limitations of the HUBO model.

The security underpinning the widely used RSA cryptosystem relies on the computational difficulty of prime factorisation, the process of breaking down a composite number into its prime number constituents. Researchers continually investigate alternative computational methods to address potential vulnerabilities within this system, and a recent study explores the application of quantum annealing, a metaheuristic for finding the global minimum of a given objective function, to the problem of integer factorisation. The research utilises D-Wave systems, a type of quantum computer designed specifically for implementing quantum annealing. Solutions are formulated using both higher-order unconstrained binary optimisation (HUBO) and quadratic unconstrained binary optimisation (QUBO).

HUBO, a mathematical optimisation technique involving binary variables and higher-order polynomial terms, suffers from exponential memory growth, severely limiting its scalability for larger factorisation problems. QUBO, conversely, employs only quadratic terms, offering improved scalability and enabling the accurate factorisation of semiprimes – composite numbers derived from the product of two prime numbers – up to 60 bits. The study successfully factors the example semiprime N = 1152921423002469787 using this approach. A key innovation within the research lies in the implementation of global product constraints, which enforce the requirement that the factors found multiply to equal the original number being factorised. This demonstrably improves both the accuracy and consistency of the factorisation process, reducing the incidence of incorrect results.

This research demonstrates a quantum annealing approach to prime factorisation, offering valuable insights into the capabilities of this technology for tackling computationally challenging problems. The successful factorisation of 60-bit semiprimes, while not immediately threatening to current RSA key sizes which typically range from 2048 to 4096 bits, demonstrates the potential of quantum annealing to address increasingly complex computational challenges as the technology matures. Further development could potentially impact cryptographic security in the future.

The computational difficulty of prime factorisation remains a cornerstone of modern cryptography, and this study contributes to the ongoing effort to assess the security of widely used encryption algorithms. Researchers are actively exploring various quantum and classical approaches to factorisation, seeking to identify potential vulnerabilities and develop more robust cryptographic systems to safeguard digital communications and data.