Shor's Factoring Algorithm and Modular Exponentiation Operators Article Swipe

MAKE IMPACT

Robert L. Singleton · YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2306.09122

These are pedagogical notes on Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time. In contrast, all known classical algorithms for the factoring problem take an exponential time to factor large numbers. In these notes, we assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing. The literature is thick with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation. We develop the theory of modular exponentiation (ME) operators in some detail, one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. We also discuss the post-quantum processing and the method of continued fractions, which is used to extract the exact period of the modular exponential function from the approximately measured phase angles of the ME operator. The manuscript then moves on to a series of examples. We first verify the formalism by factoring N=15, the smallest number accessible to Shor's algorithm. We then proceed to factor larger numbers, developing a systematic procedure that will find the ME operators for any semi-prime $N = p \times q$ (where $q$ and~$p$ are prime). Finally, we factor the numbers N=21, 33, 35, 143, 247 using the Qiskit simulator. It is observed that the ME operators are somewhat forgiving, and truncated approximate forms are able to extract factors just as well as the exact operators. This is because the method of continued fractions only requires an approximate phase value for its input, which suggests that implementing Shor's algorithm might not be as difficult as first suspected.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2306.09122

PDF

https://arxiv.org/pdf/2306.09122

OA Status

green

Cited By

1

Related Works

10

OpenAlex ID

https://openalex.org/W4380994385

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4380994385

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2306.09122

Digital Object Identifier

Title

Shor's Factoring Algorithm and Modular Exponentiation Operators

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2023

Year of publication

Publication date

2023-06-15

Full publication date if available

Authors

Robert L. Singleton

List of authors in order

Landing page

https://arxiv.org/abs/2306.09122

Publisher landing page

PDF URL

https://arxiv.org/pdf/2306.09122

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2306.09122

Direct OA link when available

Concepts

Factoring, Modular exponentiation, Exponentiation, Quantum computer, Algorithm, Modular arithmetic, Quantum algorithm, Quantum phase estimation algorithm, Operator (biology), Mathematics, Computer science, Exponential function, Prime factor, Arithmetic, Quantum, Discrete mathematics, Algebra over a field, Prime (order theory), Cryptography, Pure mathematics, Combinatorics, Public-key cryptography, Quantum error correction, Quantum mechanics, Encryption, Physics, Biochemistry, Repressor, Transcription factor, Finance, Operating system, Mathematical analysis, Chemistry, Economics, Gene

Top concepts (fields/topics) attached by OpenAlex

Cited by

1

Total citation count in OpenAlex

Citations by year (recent)

2025: 1

Per-year citation counts (last 5 years)

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload