How Shor's Algorithm Factors 314191

How Shor’s Algorithm Factors 314191

Source: How Shor’s Algorithm Factors 314191, minutephysics, 5:52, uploaded 2019-05-22, playlist index 334.

MinutePhysics follows up its explanation of quantum computers and encryption with a small, complete factoring example. The story is a bank vault full of pies whose access code uses the composite number $N = 314191$ . The number is small enough for the video to name the intermediate quantum states, although the method is meant to explain why factoring large RSA numbers could threaten public-key encryption. The description calls 314191 a pseudoprime and links the example to the number-theoretic form of Shor’s algorithm.

From factoring to order-finding

Shor’s algorithm does not search through possible factors one by one. It starts with a random number $a$ and checks whether $a$ already shares a factor with $N$ . If it does, the classical calculation is finished. If it does not, the useful question becomes the smallest positive power $p$ for which

a^p \equiv 1 \pmod N.

This $p$ is the period, or order, of $a$ modulo $N$ . When the period is even, the expression $a^{p/2}$ gives a route to two factors through the greatest common divisors of $N$ with $a^{p/2} - 1$ and $a^{p/2} + 1$ . The video calls $a^{p/2} \pm 1$ a much better guess because each value can share a non-trivial factor with $N$ .

The classical part is easy to state. Finding $p$ for a large $N$ is the hard part, and that is where the quantum computation enters.

The first period: 101

The video chooses $a = 101$ . Euclid’s algorithm shows that 101 shares no factor with 314191, so the example proceeds to order-finding.

The imagined quantum computer raises 101 to many powers at once and records the remainders modulo 314191. A superposition of possible exponents becomes a superposition of values such as $101$ , $101^2$ , $101^3$ , and their remainders. Measuring the remainder might return 74126. The remaining state then contains the exponents that produced that remainder.

For this small example, the video can calculate those exponents explicitly. They include 20, 4367, and 8714. Their spacing is 4347, so the hidden period is $p = 4347$ . In a real factoring problem, the computer would leave the exponents in a periodic state without handing us a neat list of them. The periodic spacing is the information that matters.

The next step makes that spacing visible as a frequency. A quantum Fourier transform turns a state with period $p$ into a superposition of multiples of $1/p$ . The video first gives the simplified picture of $1/p$ , then adds the qualification it skipped in the earlier explanation: technical details make the transform produce $1/p$ , $2/p$ , $3/p$ , and so on. For the example, those frequencies are multiples of $1/4347$ .

Measurement returns one value at random. One run might give $5/4347$ , another $6/4347$ , and another $2/4347$ . Repeating the computation lets the common denominator emerge, which reveals $p$ . The source keeps the classical reconstruction brief because the small example lets it name the answer directly.

The result checks out: $101^{4347}$ is one more than a multiple of 314191. The multiple is enormous, even though the number being factored is small enough for the animation to keep visible.

An odd period forces a restart

The first run reaches a genuine failure. The period 4347 is odd, so $p/2$ is not a whole number. The factoring step cannot use $101^{4347/2}$ , and the video drops the calculation with an audible “oh, crap” before starting again with $a = 127$ .

The second run repeats the same order-finding process. This time it finds

p = 17388,

so $p/2 = 8694$ . The two Euclidean-algorithm calculations are now useful:

\gcd(314191, 127^{8694} + 1) = 829

and

\gcd(314191, 127^{8694} - 1) = 379.

The factors multiply back to the original number:

829 \times 379 = 314191.

The bank-vault code is open and the pies are available. The demonstration earns its conclusion through the failed first choice as much as through the successful second one. The quantum part finds a period, while the final factor extraction remains a familiar Euclidean calculation.

What the small example leaves out

The video calls its first account a rough overview and uses the second video to fill in one detail about the Fourier transform. Its numbers are deliberately small, which lets the creator show the remainders, exponent gaps, frequency samples, and final greatest common divisors. A cryptographic instance would hide those values inside a far larger state. The note therefore records the source’s teaching example rather than treating it as a demonstration of a practical quantum machine breaking a current RSA key.

The captions and description do not explain the circuit that performs modular exponentiation, the number of qubits, error correction, success probabilities, or the classical method that reconstructs a period from measured Fourier samples. They also attach the encryption claim to the motivating context rather than proving a security result. The durable part of the example is the division of labour: quantum interference exposes the period in modular arithmetic, and ordinary number theory turns that period into factors.