Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Science

Factoring Numbers with Waves

Muhammad Suhail Zubairy

Published Apr 26, 2007• 5 citations
Publisher

Abstract

Finding prime factors of a number by means of wave interference may have applications in quantum computing and security systems.
DOI
10.1126/science.1140915

Related papers

HUBO and QUBO models for prime factorization

Kyungtaek Jun, Hyunju Lee

The security of the RSA cryptosystem is based on the difficulty of factoring a large number N into prime numbers [Formula: see text] and [Formula: see text] satisfying [Formula: see text]. This paper presents a prime factorization method using a D-Wave quantum computer that could threaten the RSA cryptosystem in the future. The starting point for this method is very simple, representing two prime numbers as qubits. Then, we set the difference between the product of the two prime numbers expressed in qubits and N as a cost function, and we find the solution when the cost function is minimized. D-Wave's quantum annealer can find the minimum value of any quadratic problem. However, the cost function must be a higher-order unconstrained optimization (HUBO) model because it contains second- or higher-order terms. We used a hybrid solver accessible via Leap, D-Wave's real-time quantum cloud service, and the dimod package provided by the D-Wave Ocean software development kit (SDK) to solve the HUBO problem. We also successfully factorized 102,454,763 with 26 logical qubits. In addition, we factorized 1,000,070,001,221 using the range-dependent Hamiltonian algorithm.

arXiv:2301.06738•Scientific Reports•Jun 21, 2023•21 citations

A New Simple and Efficient Quantum Algorithm for Factoring Composite Integers

Dhananjay P. Mehendale

Quantum Physics Letters•Aug 1, 2018•1 citation

Quantum Procedures for Factorizing Large Numbers

Schuurman, Lynn K.N.

•Jun 1, 2025•0 citations

What has quantum mechanics to do with factoring? April 2007

N. David Mermin

A quantum computer is a digital computer capable of exploiting quantum coherence among the physical two-state systems that store the binary arithmetic information. To factor an integer is to find its (unique) expression as a product of prime numbers. The most impressive, most important, and best-known thing a quantum computer can do is to factor with spectacular efficiency the product of two enormous prime numbers. But what on earth can quantum mechanics have to do with factoring? This question bothered me for four years, from the time I heard about the discovery that a quantum computer was spectacularly good at factoring until I finally took the trouble to find out how it was done. The answer, you will be relieved—but, if you're like me, also a little disappointed—to learn, is that quantum mechanics has nothing at all directly to do with factoring. But it does have a lot to do with waves. Many important waves are periodic, so it is not very surprising that quantum mechanics might be useful in efficiently revealing features associated with periodicity. Quantum mechanics is connected to factoring through periodicity. It turns out, for purely arithmetic reasons having nothing to do with quantum mechanics, that if we have an efficient way to find the period of a periodic function, then, as we shall see below, we can easily factor the product of two enormous prime numbers. And a quantum computer provides an extremely efficient way to find periods. All of the above is of considerable practical importance, because the great difficulty in factoring such a product—where the two enormous prime numbers are typically each several hundred digits long—is the basis for the security of the most widely used encryption scheme (called RSA [1] encryption) for protecting private information sent over the internet. In 1994 Peter Shor discovered [2] that a quantum computer would be super-efficient at period finding and thereby pose a potential threat to innumerable secrets. Whence the explosion of interest in developing quantum computation. The threat is only potential because no quantum computer capable of anything like serious period finding currently exists. I suspect the emphasis has been put on factoring rather than period finding because factoring is more famously associated with RSA code breaking, although, as it happens, period finding can be used directly to crack the RSA code, without any need for a detour into factoring.

Cambridge University Press eBooks•Jan 5, 2016•0 citations

Computing prime factors with a Josephson phase qubit quantum processor

Erik A. Lucero, R. Barends, Yulin Chen +11 more

arXiv:1202.5707•Nature Physics•Aug 19, 2012•307 citations

Modeling One-way and Two-way quantum key distribution protocols

Ahmed Mahmoud Sofy, Mohamed Ahmed Shalaby, Hisham Dahshan +1 more

The present cryptography systems security depends on the hardness of factorizing an integer number with a large number of digits to its prime integer factors. In 1994, Peter Shor proposed a quantum procedure (Shor's algorithm) that easily factorizes large integer numbers to its prime factors compared with other algorithms. Consequently, present cryptography systems became endangered and once quantum computers exist, conventional cryptography systems could breakdown. On the other hand, quantum cryptography security is based on the well-known quantum mechanics uncertainty principle, and so the quantum cryptography enhances the cryptography field with a mechanism for eavesdropper detecting. Here, a hardware implementation was proposed for two types of key distribution protocols based on quantum computing, the one-way quantum key distribution protocol (BB84 protocol), and the two-way quantum key distribution protocol.

International Conference on Intelligent Computing and Information Systems (ICICIS)•Dec 1, 2019•3 citations
The security of the RSA cryptosystem is based on the difficulty of factoring a large number N into prime numbers [Formula: see text] and [Formula: see text] satisfying [Formula: see text]. This paper presents a prime factorization method using a D-Wave quantum computer that could threaten the RSA cryptosystem in the future. The starting point for this method is very simple, representing two prime numbers as qubits. Then, we set the difference between the product of the two prime numbers expressed in qubits and N as a cost function, and we find the solution when the cost function is minimized. D-Wave's quantum annealer can find the minimum value of any quadratic problem. However, the cost function must be a higher-order unconstrained optimization (HUBO) model because it contains second- or higher-order terms. We used a hybrid solver accessible via Leap, D-Wave's real-time quantum cloud service, and the dimod package provided by the D-Wave Ocean software development kit (SDK) to solve the HUBO problem. We also successfully factorized 102,454,763 with 26 logical qubits. In addition, we factorized 1,000,070,001,221 using the range-dependent Hamiltonian algorithm.
A quantum computer is a digital computer capable of exploiting quantum coherence among the physical two-state systems that store the binary arithmetic information. To factor an integer is to find its (unique) expression as a product of prime numbers. The most impressive, most important, and best-known thing a quantum computer can do is to factor with spectacular efficiency the product of two enormous prime numbers. But what on earth can quantum mechanics have to do with factoring? This question bothered me for four years, from the time I heard about the discovery that a quantum computer was spectacularly good at factoring until I finally took the trouble to find out how it was done. The answer, you will be relieved—but, if you're like me, also a little disappointed—to learn, is that quantum mechanics has nothing at all directly to do with factoring. But it does have a lot to do with waves. Many important waves are periodic, so it is not very surprising that quantum mechanics might be useful in efficiently revealing features associated with periodicity. Quantum mechanics is connected to factoring through periodicity. It turns out, for purely arithmetic reasons having nothing to do with quantum mechanics, that if we have an efficient way to find the period of a periodic function, then, as we shall see below, we can easily factor the product of two enormous prime numbers. And a quantum computer provides an extremely efficient way to find periods. All of the above is of considerable practical importance, because the great difficulty in factoring such a product—where the two enormous prime numbers are typically each several hundred digits long—is the basis for the security of the most widely used encryption scheme (called RSA [1] encryption) for protecting private information sent over the internet. In 1994 Peter Shor discovered [2] that a quantum computer would be super-efficient at period finding and thereby pose a potential threat to innumerable secrets. Whence the explosion of interest in developing quantum computation. The threat is only potential because no quantum computer capable of anything like serious period finding currently exists. I suspect the emphasis has been put on factoring rather than period finding because factoring is more famously associated with RSA code breaking, although, as it happens, period finding can be used directly to crack the RSA code, without any need for a detour into factoring.
The present cryptography systems security depends on the hardness of factorizing an integer number with a large number of digits to its prime integer factors. In 1994, Peter Shor proposed a quantum procedure (Shor's algorithm) that easily factorizes large integer numbers to its prime factors compared with other algorithms. Consequently, present cryptography systems became endangered and once quantum computers exist, conventional cryptography systems could breakdown. On the other hand, quantum cryptography security is based on the well-known quantum mechanics uncertainty principle, and so the quantum cryptography enhances the cryptography field with a mechanism for eavesdropper detecting. Here, a hardware implementation was proposed for two types of key distribution protocols based on quantum computing, the one-way quantum key distribution protocol (BB84 protocol), and the two-way quantum key distribution protocol.