Ingredients for Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer

What exactly are all of the ingredients or puzzle pieces needed for Shor’s algorithm for factorization of large integers to enable it to supposedly break even the strongest public-key encryption if given a sufficiently powerful quantum computer?

This is essentially the same question as asking what knowledge is needed to comprehend Shor’s algorithm.

An extensive list of questions related to Shor’s algorithm can be found in a preceding paper, Some Preliminary Questions About Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer.

An algorithm is not unlike a cooking recipe, which involves a number of steps as well as a collection of ingredients. And some equipment, and some tools.

This informal paper will not explore all nuances of Shor’s algorithm or even offer a basic description of the full algorithm. Nor will it offer any implementations of the algorithm — actual code, classical or quantum.

Rather, this paper seeks only to compile a list of the ingredients which are needed to comprehend Shor’s algorithm. That won’t constitute a full description of the algorithm, but should be a solid foundation for further elaboration about the algorithm in subsequent papers.

Shor’s algorithm for factorization of large integers, particularly those which are semiprimes, the product of two prime numbers, is a hybrid algorithm, which has a classical part and a quantum part. As such, each part will have its own list of ingredients.

The classical part of Shor’s algorithm is essentially an outer loop which invokes the quantum part. The classical part needs to know what the quantum part accomplishes, but not the details of how it accomplishes that result.

The cooking metaphor of ingredients is not perfect. Some of the ingredients for an algorithm will be data and some of them will be functions or even mathematical concepts. Again, the point is to get at the knowledge which is needed to fully comprehend Shor’s algorithm, how it works, its consequences, its limitations, and its requirements.

The ingredients for the classical part of Shor’s algorithm are:

1. A classical computer. May be very modest in size, capacity, and performance since the heavy lifting is accomplished by the quantum part of the algorithm. In theory, that is. I’m not completely convinced yet.
2. An input number to be factored. Ultimately this must be in binary form, but a variety of input formats could be supported — binary text, decimal text, hex, base64, short lines, white space, commas, PEM, etc. — and converted to binary. This input number is commonly referred to as N.
3. The input number is represented in binary using a number of bits. This count of bits is commonly referred to as n, such that N is an n-bit integer and N is less than 2^n. This number of bits is also referred to as the length of the input. This count could be automatically inferred from the input number or provided as an explicit parameter. Ultimately the length is simply int(log2(N+1)).
4. Number theory.
5. Group theory.
6. Factorization algorithm. Shor’s original algorithm or a derivative algorithm. Focused on semiprimes — input number is presumed to be the product of two prime numbers.
7. Factorization is reduced to an order-finding algorithm. Miller (1976): Riemann’s Hypothesis and Tests for Primality. Why is that the best approach? Great question, which is on my list in that earlier paper — Some Preliminary Questions About Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer.
8. Randomized algorithm. The use of random numbers to achieve a superior result or performance compared to a strictly deterministic algorithm. As Shor writes in his paper, “It is known that using randomization, factorization can be reduced to finding the order of an element [Miller 1976].”
9. A random number generator. Capable of generating integers between 1 and N. The exact range may be more like 3 to N/3, but the precise range is unclear. That’s another open question on my list.
10. The GCD function which calculates the greatest common divisor of two numbers. It must be able to handle integers as large as N.
11. A classical outer loop which iteratively generates random numbers, performs a preliminary checks with GCD to detect trivial cases, invokes the quantum code to calculate the period for the random number, performs post-processing checks on the period and calculates the two prime factors if the post-processing checks succeed.
12. Creation of a quantum program (quantum circuit) for calculating the period for a number, the generated random number, within the range of another number, the input number. The quantum program depends on the input number, N, not as an explicit parameter, but the configuration of the generated quantum logic gates implies both the input number, N, and its count of bits, n. To be clear, the size of the quantum program will depend on the number of bits in the input number.
13. Invocation of the generated quantum program (circuit) for calculating the period of a generated random number relative to the input number. The input number for the quantum program must be prepared to initialize the quantum state of the quantum program and the result must be measured from the final quantum state once the generated quantum program has completed its execution.
14. Perform the invocation of the generated quantum circuit some number of times — the shot count or circuit repetitions — and perform a statistical analysis of the results to determine the most likely result, the expected value. Unclear how many shots will be required — it would depend on the size of the input number to be factored, or what formula to use to calculate the shot count. For more detail on that process, see Shots and Circuit Repetitions: Developing the Expectation Value for Results from a Quantum Computer.
15. Post-processing in classical code to get the actual period of the random number from the intermediate result calculated by the quantum part of the algorithm. See continued fraction expansion.
16. Continued fraction expansion. The quantum part of the algorithm doesn’t calculate the period per se, but produces an intermediate result from which the classical code in the outer loop can then calculate the period from the continued fraction expansion.
17. Recurrence relations. Primarily needed for continued fraction expansion.
18. Convergent of a continued fraction expansion. Needed to calculate the period.
19. Post-processing in classical code in the outer loop using the actual period of the random number to determine if it can produce the factors of the semiprime input number and to actually produce those factors. Requires exponentiation and GCD.
20. Exponentiation. An integer raised to another integer power. The base integer could be as large as N or 2^n minus 1. The exponent is the period divided by two.
21. Prime factor calculation from period. Using exponentiation and GCD.
22. Iterate the outer loop until the period for the generated random number finally results in two prime factors.
23. Is the outer loop guaranteed to eventually stumble on the right random number? In other words, might it have the Turing halting problem? Great question. Also on my list.

Additional ingredients for the classical part, beyond what is officially given in Shor’s algorithm:

1. Detection of even input numbers.
2. Detection of prime power input numbers — N = p^k.
3. Detection of prime numbers. Technically a prime power as well, with a power of 1.
4. Detection of any other pathological input numbers — negative numbers, 0, 1, 2^(n-1).
5. More than two factors. Such as p*q*r.
6. Repetitions or powers of two factors. Including p^k*q, p*q^k, and p^k1*q^k2. For example, 2³*5⁷ is 3 repetitions of the same factor and 7 repetitions of the other factor. Note that 2³ is covered by the case of a prime power.

The ingredients for the quantum part of Shor’s algorithm are:

1. Factorization is reduced to an order-finding algorithm. Miller (1976): Riemann’s Hypothesis and Tests for Primality.
2. Riemann Hypothesis. Miller (1976): Riemann’s Hypothesis and Tests for Primality.
3. Extended Riemann Hypothesis (ERH). Miller (1976): Riemann’s Hypothesis and Tests for Primality.
4. Fermat’s Congruence — Fermat’s Little Theorem. Miller (1976): Riemann’s Hypothesis and Tests for Primality.
5. Test for primality. Miller (1976): Riemann’s Hypothesis and Tests for Primality.
6. Period-finding algorithm. AKA order-finding algorithm or quantum order-finding algorithm (QOFA).
7. Sufficient qubits. To hold both the random number whose period is to be found and intermediate results. This appears to be four times n, the number of bits needed to represent the original input number, plus a few — 4n+3. There are variants and derivatives of Shor’s original algorithm which use n, 2n, 3n, or even 9n qubits (plus a few.) For purposes of this paper, the original algorithm is presumed, so 4n+3 qubits are required. To be clear, the qubits are being used to calculate the period of the random number, not the original input number.
8. Treat qubits as two registers. Each of 2n qubits. Algorithm requires 2^q quantum states in each register where 2^k is greater than or equal to N². N² requires 2n bits. Quantum computers do not have registers per se as in a classical computer, but the algorithm treats qubits as if they were bits in a classical register.
9. Sufficient connectivity to entangle the quantum states of those qubits. I don’t have clarity yet on exactly how much connectivity is required. It may be as simple as two registers, each of 2n qubits, each qubit of each register entangled with the corresponding qubit of the other register, in parallel.
10. Sufficient coherence time to execute a large number of quantum logic gates. As well as preparation and measurement time. How many? Not so clear at this stage, but many thousands, especially for input numbers of a thousand or more bits. Most of these gates will be executing in parallel, so the quantum circuit depth may not really be very high. Again, I don’t have clarity yet. Dozens, maybe?
11. Repetition of execution of the quantum program to assure a statistically accurate result since quantum programs are probabilistic rather than deterministic. How many repetitions? Not so clear at this stage, but a least a few, maybe a dozen or a few dozen, or even a hundred, especially if quantum errors are occurring with too high a frequency.
12. Quantum preparation. Initializing state of qubits including based on the candidate random number.
13. Multiplicative group. Basis for performing modular exponentiation.
14. Modular exponentiation. To calculate the order of the random number, which is the smallest power to which the random number must be raised to get a value of 1 modulo the number being factored. At least that’s the classical calculation, which in the quantum algorithm is calculated using phase estimation.
15. Schönhage-Strassen algorithm for multiplication of large numbers to implement modular exponentiation. Mentioned in Shor’s paper, but it’s not completely clear whether this algorithm is used directly in Shor’s algorithm, or simply mimicked by the quantum-equivalent algorithm.
16. Quantum parallelism to perform modular exponentiation. Use a sequence of Hadamard gates to set a register to a superposition of all possible states of n qubits, then perform modular exponentiation in a second register using the first register (all possible exponent values) for the exponent, calculating all possible modular exponents, in parallel. This is the real bottleneck in the classical implementation.
17. Chinese remainder theorem.
18. Euler’s totient function. Also known as Euler’s phi function.
19. Fourier transform (FT). Use to transform numbers between two domains when calculations will be simplified in another domain. May be continuous or discrete sampling.
20. Fourier series. Basis for Fourier transform.
21. Discrete Fourier transform (DFT). Fourier transform for equally-spaced sample input values, rather than purely continuous input values.
22. The standard fast Fourier transform (FFT) algorithm [Knuth 1981]. Simplified form of DFT for higher performance and less calculation. The quantum Fourier transform (QFT) is derived from it.
23. Approximate Fourier Transform or Approximate Fast Fourier Transform (AFFT). Defined by Coppersmith, alluded to by Shor, but not explicitly incorporated into his algorithm. Supposedly cures potential issue with impossibly small phase factors — division by 2⁴⁰⁹⁶ for 4096-bit keys.
24. Hadamard Transform (HT). A stepping-stone used by Coppersmith to derive an approximate fast Fourier transform (AFFT).
25. Quantum Fourier transform (QFT). Produces the intermediate result which the classical code can then quickly transform into the actual period of the random number.
26. Approximate quantum Fourier transform (approximate Fourier transform or approximate fast Fourier transform — AFFT). Far fewer quantum logic gates than a full quantum Fourier transform, but less precise.
27. Banded quantum Fourier transform. A particular form of approximate quantum Fourier transform proposed to be used with Shor’s algorithm.
28. Reduction of order-finding to phase estimation.
29. Quantum phase estimation.
30. Quantum measurement. This does not directly produce the period of the candidate random number, but produces an intermediate string of bit values from which a classical continued fraction expansion can then produce the period.

These lists of ingredients are not necessarily absolutely comprehensive. They will be enhanced as I delve deeper into the nuances and various alternative descriptions of Shor’s algorithm.

References

See the References section of Some Preliminary Questions About Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer.