Application of Shor’s Algorithm to Generate Prime Numbers
Yash Raj Kohli Vaibhav Sharma Srishti Yadav
yash.kohli.ug21@nsut.ac.in vaibhav sharma.ug21@nsut.ac.in srishti.yadav.ug21@nsut.ac.in
Mathematics and Computing (CSE), Netaji Subhas University of Technology, Dwarka, Delhi, 110078, India
Abstract
Within recent times, the field of Quantum Computing has slowly grown and it’s expected to re-
place classical computers in the future. We tend to implement the Shor's algorithm to generate
prime numbers which can be used in Hashing technique. The hash functions utilise a prime
number to generate indices to store information for faster access. Classical computers and algo-
rithms utilise exponential time to generate these numbers. This paper aims to utilise the Shor’s
algorithm and harness the speed of quantum computation to generate these prime numberes that
work in polynomial time and thus utilise it in Hashing technique.
Keywords: Shor's Algorithm, Prime Factorization, Quantum Computers, Hashing, Number
Theory, Quantum Fourier Transforms
1. Introduction
The realm of quantum computing (QC) has captured significant attention in recent years
due to its potential to revolutionize problem-solving across various fields. By leveraging
quantum-mechanical phenomena like superposition and entanglement, quantum computers
offer exponential speedups, particularly in tackling combinatorial problems. The applications of
quantum computing are diverse, ranging from machine learning and security to drug discovery.
However, the practical realization of quantum computing faces formidable challenges, including
qubit decoherence, measurement inaccuracies, and gate errors.
Quantum error correction (QEC) codes hold promise for ensuring reliable quantum oper-
ations, yet their resource demands currently hinder widespread adoption. The emergence of
Noisy Intermediate-Scale Quantum (NISQ) computers, operating amidst noise with a limited
qubit count, along with hybrid algorithms, presents a potential solution for discrete optimization,
quantum chemical simulations, and drug discovery.
In parallel with these advancements, interest in quantum encryption and quantum key
distribution has surged. These developments open avenues for utilizing quantum algorithms to
develop robust cryptographic primitives, critical for secure data communication and storage.
It has been known since before Euclid that every integer n is uniquely decomposable into
a product of primes. Mathematicians have been interested in the question of how to factor a
number into this product of primes for nearly as long. It was only in the 1970’s, however, that
researchers applied the paradigms of theoretical computer science to number theory, and looked
Preprint submitted to Knowledge-Based Systems May 1, 2024
at the asymptotic running times of factoring algorithms.[1]
Motivated by these developments, our research investigates the intersection of quantum
computing and data security. We acknowledge the dual role of quantum computing, posing both
a threat and an opportunity for innovation in cryptographic codes and data security.
The threat lies in the computational power of quantum computing, which could render classical
cryptographic codes obsolete. For instance, Shor’s algorithm has the potential to efficiently
factor large numbers, compromising widely-used encryption schemes like RSA. Consequently,
there is an urgent need for quantum-resistant cryptographic solutions to safeguard sensitive
information.
However, amid this challenge lies an opportunity for innovation. Quantum circuits and
algorithms, leveraging properties such as superposition and entanglement, offer the potential to
design cryptographic solutions that are not only more secure against quantum attacks but also
more efficient in performance.
Our work focuses on exploring the potential of quantum computation to generate large
prime numbers which can be further used in Hashing and Hash-Table data structure. As hashing
primarily requires a large prime number to create a hash table. The Shor’s algorithm also
challenges the AES-128 encryption algorithm but that depends on the computational power
of the state of the art quantum computers. Here, our research proposes a novel quantum-based
implementation to use the prime factors generated by the Shor’s Algorithm to create Hash
functions which may be used to counter the demand for better data structures as the data grows
daily.
2. Theory
2.1. Classical Algorithms Explanation
The distinction between computable and non-computable functions, as explored in founda-
tional papers by Church [1936], Turing [1936], and Post [1936], marked a seminal moment
in the mathematics of computation, laying the groundwork for much of theoretical computer
science [2]. Central to this distinction is Church’s thesis, which posits that all computing
devices can be simulated by a Turing machine, thereby simplifying the study of computation by
narrowing the scope to Turing machines.
Classical factorization algorithms have played a pivotal role in shaping our understanding of
computational complexity. These algorithms represent fundamental approaches to decomposing
composite numbers into their prime factors, a problem of central importance in number theory
and cryptography.[3]
1. Trial Division Algorithm: The trial division algorithm, dating back to ancient times, repre-
sents the simplest approach to factorization. It involves systematically dividing the target integer
by each potential factor up to its square root. While intuitive, its exponential time complexity
renders it impractical for large numbers.
2. Pollard’s Rho Algorithm: Pollard’s rho algorithm is a probabilistic method for integer fac-
torization. It relies on Floyd’s cycle-finding algorithm to identify non-trivial factors by detecting
2
cycles in a sequence of values generated through modular arithmetic. Although its worst-case
time complexity is exponential, it often performs well in practice for moderately sized integers.
3. Elliptic Curve Factorization Method: The elliptic curve factorization method leverages
the algebraic structure of elliptic curves to factorize integers. By exploiting the group law on
elliptic curves defined over finite fields, this method achieves sub-exponential time complexity,
making it suitable for certain classes of integers.
4. Continued Fraction Factorization Method: The continued fraction factorization method,
pioneered by Brillhart, Lehmer, and Selfridge, utilizes the periodicity of continued fractions to
efficiently factorize integers. This method exploits the properties of quadratic irrationals and
convergents of continued fractions to identify prime factors, offering a viable alternative to other
classical algorithms.
2.2. Shor’s Algorithm Explanation
The significance of Shor’s algorithm[4] lies in its direct assault on the bedrock of modern
cryptography—the challenge of factoring large numbers. Traditional encryption systems heavily
rely on the presumed computational infeasibility of factoring large numbers efficiently. Shor’s
algorithm, by demonstrating the feasibility of this task on a quantum platform, cast a looming
shadow over existing cryptographic protocols. While classical computing methods for factoring
large numbers operate at exponential time complexity, Shor’s algorithm, powered by quantum
parallelism, slashes this complexity to polynomial time on a quantum computer, albeit with some
post-processing steps on a classical computer.
Central to Shor’s algorithm is a profound insight from number theory: the periodic nature
of certain mathematical functions, particularly when applied to coprime integers. Leveraging
this insight, Shor devised a method to efficiently find the period of such functions, crucially
applicable to factoring large numbers. The algorithm exploits quantum parallelism to explore a
vast number of potential periods simultaneously, a feat unattainable by classical computers.
Shor’s algorithm ingeniously employs a quantum memory register to handle superpositions of
states representing candidate integers for the function evaluation. Through quantum operations
and measurements, the algorithm extracts the period information from the quantum register, lay-
ing the groundwork for subsequent classical analysis to deduce the factors of the target number.
2.3. Comparison
The cornerstone of secure communication has long been traditional cryptographic protocols
based on mathematical algorithms that incorporate large prime numbers. These methodologies
take advantage of the presumed computational complexity associated with tasks such as the
calculation of large numbers, which, in theory, makes them impervious to attacks from modern
classical computer architectures.
The susceptibility of classical cryptography[5] to potential breaches caused by quantum
computing advances, epitomized by Shor’s algorithm’s polynomialtime factorization capability,
reveals a fundamental vulnerability. When confronted by adversaries with quantum compu-
tational capacity, the advent of quantum computing poses a serious challenge to established
reliability of classical encryption mechanisms due to its expected speed and ability for quantum
superposition.
The inherent uncertainty principle is used in quantum communications protocols to ensure that
any attempt to intercept transmitted information is inevitably perturbing the quantum state,
3
thereby betraying the presence of an intruder. This intrinsic security feature, irreplicable within
classical transmission mediums, forms the cornerstone of quantum cryptographic methodologies.
In addition, quantum cryptography[5] presents a complex interplay of benefits and chal-
lenges in the assessment of technology, economic or application aspects. Although quantum
communications systems are capable of covering a limited distance, usually around 50 km, they
provide unprecedented security guarantees.
However, widespread adoption is hindered by prohibitively high implementation costs
and current constraints on the deployment of cryptographic points to quantum connections. On
the other hand, in communication distance and application scenarios, classical cryptographic
paradigms, which are easy to implement via software at nominal costs, are flexible, albeit at the
risk of susceptibility to attacks on the basis of computational power.
Fundamentally, the dichotomy between traditional and quantum cryptographic methodolo-
gies resides in the underpinning security paradigm: traditional cryptography rests upon
mathematical complexity assumptions, vulnerable to obsolescence in the face of quantum
algorithmic breakthroughs, while quantum cryptography capitalizes on the intrinsic properties
of quantum mechanics to furnish verifiable security, even when confronted with quantum
adversaries. The need for an adaptive security architecture, capable of surviving the rigors of
quantum computing, is underlined by a comparative analysis which shows that traditional and
quantum cryptographic methods are constantly evolving.
3. Methodology
Implementing Shor’s algorithm on a quantum computer involves several key steps. Here’s a
more detailed breakdown of those steps:
1. Preprocessing: - Choose the integer N to be factored. It must be composite, odd, and not
a power of a prime. - Choose a random integer a such that gcd(a, N) = 1. This ensures that a is
not a multiple of N.
2. Quantum Circuit Initialization: - Initialize the quantum register to a superposition state
using Hadamard gates to prepare all possible values of the input register. - Initialize an auxiliary
register to hold intermediate values.
3. Quantum Modular Exponentiation: - Implement modular exponentiation f (x) = a x
mod N as a quantum circuit. This involves repeated modular multiplication of the input register
with the base a and reducing modulo N. - This step is crucial for finding the period of f (x),
which is the key to factoring N.
4. Quantum Fourier Transform (QFT): - Apply the Quantum Fourier Transform to the
auxiliary register. The QFT amplifies the periodic components of the state. - This step extracts
the period of the modular exponentiation function from the quantum state.
5. Period Measurement: - Measure the auxiliary register to collapse the quantum state and
obtain a classical outcome representing the period of the modular exponentiation function. - Use
quantum parallelism and interference effects to efficiently find the period with high probability.
6. Classical Post-processing: - Use the measured period to compute potential factors of N
using classical algorithms, such as continued fraction expansion or Euclid’s algorithm. - Check
if the factors obtained are non-trivial and if they indeed factorize N.
4
Figure 1: Shor’s quantum factoring algorithm flowchart
[6]
5
Figure 2: Quantum circuit for phase estimation
7. Repeat or Terminate: - If the factors obtained are trivial, meaning they don’t yield non-
trivial factors of N, repeat the algorithm with a different randomly chosen a. - Continue until
non-trivial factors of N are obtained or until a predetermined number of iterations is reached.
8. Error Correction and Optimization: - Implement error correction techniques to mitigate
errors introduced during quantum computation. - Optimize the quantum circuit to reduce the
number of qubits, gates, and overall computational complexity.
9. Experimental Implementation: - Implement the quantum circuit on a physical quantum
computer or a quantum simulator. - Experimentally verify the algorithm’s performance and
scalability.
10. Analysis and Interpretation: - Analyze the results obtained from the experimental im-
plementation. - Compare the performance of the quantum algorithm with classical factoring
algorithms for various input sizes of N. - Interpret the implications of the results for cryptogra-
phy and number theory.
Implementing Shor’s algorithm on a quantum computer is a complex task that requires exper-
tise in quantum algorithms, quantum circuit design, error correction, and experimental quantum
physics. Each step involves careful design, optimization, and validation to ensure the correctness
and efficiency of the algorithm.
4. Implementation
4.1. Quantum Circuit Initialization and Modular Exponentiation
The quantum circuit for the phase estimation process can be seen in Figure 1. The circuit takes
m qubits and the quantum state |Ψ⟩ and passes the m qubits each through a Hadamard gate to
create a superposition and each of these qubits now act as a controlling qubit for the iterating
unitary function U f by which we determine the eigenvalue and then pass the m qubits through
the QFT tranformation gate and then measure.
The state immediately prior to the quantum Fourier transform looks like this:
6
2m −1 2m −1
1 X x 1 X 2πixθ
√ (U |ψ⟩) |x⟩ = |ψ⟩ ⊗ √ e |x⟩ (1)
2m x=0 2m x=0
This circuit helps in iterating the unitary gate U f multiple times to determine the eigenvalue
of the form 2πiθ in which we only need to find θ which is found by the phase kickback property
of the unitary gate.
4.2. Quantum Fourier Transform
The Quantum Fourier Transform (QFT) plays a crucial role in phase estimation algorithms in
quantum computing. Phase estimation is a quantum algorithm used to estimate the eigenvalues of
unitary operators, which is a fundamental problem in quantum computing and has applications in
various quantum algorithms, including quantum simulation and factoring large numbers (Shor’s
algorithm).
The Quantum Fourier Transform for N-dimensions with the standard basis states (0, 1, ..., N −
1) can be defined as:
N−1 N−1
1 X X xy
QFTN = √ ωN |x⟩⟨y| (2)
N x=0 y=0
This whole function is represented by the quantum gate QFT in the quantum circuit diagram.
Further, the QFT can be used to extract periodic features of wave functions or to switch from
“position” to “momentum” representations and is defined as follows:
1 X ′
x = 0q−1 e2πixx /q x′
′
QFTq|x⟩ = √ (3)
q
[7]
4.3. Shor’s Algorithm
Shor’s algorithm is a quantum algorithm for integer factorization, which efficiently finds the
prime factors of a given composite number. The algorithm consists of the following main steps:
1. Choose a random integer a < N.
2. Compute the greatest common divisor (GCD) of a and N. If the GCD is greater than 1, then
we have found a non-trivial factor of N, and the algorithm terminates.
3. Use quantum algorithms to find the period r of the function f (x) = a x mod N.
4. If r is odd or ar/2 ≡ −1 mod N, then go back to step 1 and choose a different a. Otherwise,
use classical algorithms to compute the factors of N.
4.4. Pseudocode
ShorAlgorithm(N):
repeat:
a := random integer such that 1 < a < N
if GCD(a, N) 1:
return non-trivial factor
until false
7
r := PeriodFinding(a, N)
if r is odd or a^(r/2) -1 (mod N):
repeat:
a := random integer such that 1 < a < N
if GCD(a, N) 1:
return non-trivial factor
until false
p := GCD(a^(r/2) - 1, N)
q := GCD(a^(r/2) + 1, N)
return p, q
5. Results
5.1. Sample output for N = 15
The program is tried on number N = 15 and the first guess a is taken as 8 and the program
proceeds with 3 attempts and then finds the non-trivial factor which is 3.
The program can be further modified to process for large numbers which requires editing the
initial conditions of the exponential modulo function, so that it works for that particularly large
number.
As of now, with the state-of-the-art quantum computers the biggest number to be factorized
is RSA-250. Now, as the quantum computation power grows overtime, it is expected to factor
larger numbers.
We ought to use those large numbers factored even till RSA-250, in the hashing process.
5.2. Runtime analysis
The time complexity of the Shor’s algorithm is found to be O((logN)3loglogNlogloglogN)
which is affected by the primary feature of quantum computers to act on qubits rather than clas-
sical bits.
5.3. Comparison
The most efficient algorithm for factorization in classical computing is the Number Field Sieve
which has never been analysed rigorously but the closest algorithm
√ √
to have a defined runtime
is the Dixon’s algorithm which has the time complexity eO(2 2 log n log log n) . Although, Dixon’s
algorithm is randomised.
Now, it’s clear that the classical algorithms are exponential whereas the quantum algorithm is
polynomial with logarithmic factors or non-exponential.
This helps in generating prime numbers very fast and thus we don’t have to wait for years to
compute them.
8
Figure 3: Program flow of phase estimation function
9
Figure 4: Program flow of Shor’s Algorithm (basic)
10
Figure 5: Program output for N = 15
6. Linking prime numbers to Hashing
6.1. A brief history of hashing
The term “hash” is originated from the physical world, where the standard meaning of “hash”
is “chop and mix,” which intuitively means that the hashing function “chops and mixes” infor-
mation and derives hash results. The importance of hashing techniques has been well recognized
since the very early stage of computing systems. Soon after the invention of the first true elec-
tronic computer in 1950, the concept of hashing was first mentioned in 1953 [8], where a defined
general hash function using random keys could achieve the equivalent of the mathematical con-
cept of uniformly distributed random variables. In computer science, it is almost impossible to
get a completely even distribution. Creating even distributions can only be achieved by consider-
ing the structure of the keys. For any arbitrary set of keys, it is also impossible to create a general
hash function that works better because the keys could not be obtained in advance. In this case,
a random uniform hash is the best. In 1957, motivated by the needs of using a random-access
system with very large capacity for business applications, Peterson [9] provided an estimation of
the amount of search required for the exact location of a record in several types of storage sys-
tems, including the index-table method and the sorted-file method. In 1968, the word “hashing”
was first used. [10] [11]
6.2. Introduction
Hash functions play a crucial role in computer science, cryptography and as a data structure
as well. These functions map data of arbitrary size to fixed-size values, typically used for data
indexing, storage, and retrieval. Traditional hash functions often rely on large prime numbers
due to their unique properties, such as distribution uniformity and collision resistance. In this
section, we explore the potential of utilizing prime numbers generated from Shor’s algorithm as
a means for hashing.
The hash function family is described as:
n o
H p = ha,b
p (x) = ((ax + b) mod p) mod m (4)
Here, for all a, b : 1 < a < p − 1, 0 < b < p − 1 is a universal family for the set of integers
between 0 and p − 1, for any prime p.
11
Now, p is the target variable that we want to mine from the Shor’s algorithm. Classicaly,
large prime numbers would take exponential time to generate from classical algorithms. Shor’s
algorithm comes in handy to solve the same problem in much less time (in polynomial time
complexity).
The general procedure to generate prime numbers by iterating from small numbers moving up
to large numbers would take a lot of time. We only need a large prime number, this can be done by
prime factorization of even more larger numbers. Shor’s algorithm does this in polynomial time.
This fact can be used and applied to generate hash functions which can sustain exponentially
huge data.
6.3. Prime Numbers from Shor’s Algorithm
Shor’s algorithm efficiently factors composite numbers, producing their prime factors. These
prime factors are often large and possess desirable properties for cryptographic applications. By
leveraging Shor’s algorithm, we can obtain large prime numbers that are suitable for crypto-
graphic hash functions.
6.4. Properties of Prime Numbers
Prime numbers generated from Shor’s algorithm exhibit several properties desirable for cryp-
tographic hash functions:
• Large Size: Prime numbers generated by Shor’s algorithm are typically large, enhancing
the security of cryptographic operations.
• Unpredictability: Shor’s algorithm selects random integers for factorization, resulting in
prime numbers with unpredictable values, essential for cryptographic security.
• Irregular Distribution: Prime numbers obtained from Shor’s algorithm exhibit an irregular
distribution, reducing the likelihood of hash collisions.
• Computational Complexity: Shor’s algorithm is computationally intensive, making it dif-
ficult for adversaries to derive prime factors efficiently.
6.5. Hashing with Prime Numbers from Shor’s Algorithm
To utilize prime numbers from Shor’s algorithm for hashing, we can incorporate them into
cryptographic hash functions. These functions can take advantage of the properties of prime
numbers to ensure data integrity, authenticity, and resistance against attacks.
6.6. Remarks
Shor’s algorithm provides a powerful means of generating large prime numbers, which are cru-
cial for cryptographic hash functions. By leveraging prime numbers from Shor’s algorithm, we
can enhance the security and efficiency of hashing operations in various applications, including
data storage, digital signatures, and blockchain technology.
12
7. Conclusion and Future Scope
The conclusion of the research turns out to harness the powers of quantum computation and
utilise them partly to classical computation, particularly targeting the areas where we would
require a prime number.
Prime numbers are tough to deal mathematically and there is no general formula for calculating
a prime number. A lot of conjectures on prime numbers are proposed overtime but they are still
conjectures and thus it makes prime numbers tough to deal with.
Calculating prime numbers is long and tedious on pen and paper and so one might prefer to
use computers to do so. But classical computers also take a lot of time as the input size grows and
for the particular problem of prime number generation it takes exponential time. Here, comes
the usage of quantum computation and it’s found to work in polynomial time complexity.
7.1. Future Scope
This research can be helpful in the future to utilise prime numbers in various other applications
that utilise them. There are numerous areas where hashing plays a key role such as blockchain
technology, image processing, data compression, various cryptography techniques, classical in-
dexing (helpful in data structures like dictionaries and maps).
The motive of this research thus can be used in these areas and as quantum computing im-
proves overtime, such aspects of classical computing can be replaced with quantum computing.
References
[1] L. Adleman, Algorithmic number theory-the complexity contribution, in: Proceedings 35th Annual Symposium on
Foundations of Computer Science, 1994, pp. 88–113. doi:10.1109/SFCS.1994.365702.
[2] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,
SIAM Journal on Computing 26 (5) (1997) 1484–1509.
[3] J. Wagstaff, Samuel S., History of integer factorization, Journal of Algorithms 4 (3) (1983) 66–75.
[4] M. Hayward, Quantum computing and shor’s algorithm, Journal Name (2005) 13–15.
[5] C. H. Ugwuishiwu, U. E. Orji, C. I. Ugwu, C. N. Asogwa, An overview of quantum cryptography and shor’s
algorithm, Department of Computer Science, University of Nigeria, Nsukka, Enugu StatePage 6.
[6] A. Wicaksana, A. Anthony, A. Wicaksono, Web-app realization of shor’s quantum factoring algorithm and grover’s
quantum search algorithm, TELKOMNIKA (Telecommunication Computing Electronics and Control) 18 (2020)
1319. doi:10.12928/telkomnika.v18i3.14755.
[7] Y. S. Weinstein, M. A. Pravia, E. M. Fortunato, S. Lloyd, D. G. Cory, Implementation of the quantum fourier
transform, Phys. Rev. Lett. 86 (2001) 1889–1891. doi:10.1103/PhysRevLett.86.1889.
URL https://link.aps.org/doi/10.1103/PhysRevLett.86.1889
[8] H. P. Luhn, A new method of recording and searching information, American Documenta-
tion 4 (1) (1953) 14–16. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/asi.5090040104,
doi:https://doi.org/10.1002/asi.5090040104.
URL https://onlinelibrary.wiley.com/doi/abs/10.1002/asi.5090040104
[9] W. W. Peterson, Addressing for random-access storage, IBM Journal of Research and Development 1 (2) (1957)
130–146. doi:10.1147/rd.12.0130.
[10] R. Morris, Scatter storage techniques, Commun. ACM 11 (1) (1968) 38–44. doi:10.1145/362851.362882.
URL https://doi.org/10.1145/362851.362882
[11] L. Chi, X. Zhu, Hashing techniques: A survey and taxonomy, ACM Comput. Surv. 50 (1). doi:10.1145/3047307.
URL https://doi.org/10.1145/3047307
13
