How Shor's Algorithm Factors 314191

Опубликовано 22 мая 2019, 15:13

Go to dashlane.com/minutephysics to download Dashlane for free, and use offer code minutephysics for 10% off Dashlane Premium!
Watch the main video: youtube.com/watch?v=lvTqbM5Dq4...

Support MinutePhysics on Patreon! patreon.com/minutephysics

This video explains how Shor’s Algorithm factors the pseudoprime number 314191 into its prime factors using a quantum computer. The quantum computation relies on the number-theoretic analysis of the factoring problem via modular arithmetic mod N (where N is the number to be factored), and finding the order or period of a random coprime number mod N. The exponential speedup comes in part from the use of the quantum fast fourier transform which achieves interference among frequencies that are not related to the period (period-finding is the goal of the QFT FFT).

REFERENCES

RSA Numbers (sample large numbers to try factoring)
en.wikipedia.org/wiki/RSA_numb...

IBM on RSA ibm.com/support/knowledgecente...

Modulo Multiplication Group Tables mathworld.wolfram.com/ModuloMu...

Difference of squares factorization en.wikipedia.org/wiki/Differen...

Euclid’s Algorithm en.wikipedia.org/wiki/Euclidea...

Rational sieve for factoring en.wikipedia.org/wiki/Rational...

General Number field Sieve en.wikipedia.org/wiki/Generaln...

Scott Aaronson blog post about Shor’s Algorithm scottaaronson.com/blog/?p=208

Experimental implementation of Shor’s Algorithm (factoring 15, 21, and 35) arxiv.org/pdf/1903.00768.pdf

Adiabatic Quantum Computation factoring the number 291311 arxiv.org/pdf/1706.08061.pdf

Scott Aaronson course notes scottaaronson.com/qclec scottaaronson.com/qclec/combin...

Shor’s Algorithm on Quantiki quantiki.org/wiki/shors-factor...

TLS And SSL use RSA encryption en.wikipedia.org/wiki/Transpor...

Dashlane security whitepaper dashlane.com/download/Dashlane...

Link to Patreon Supporters: minutephysics.com/supporters
MinutePhysics is on twitter - @minutephysics
And facebook - facebook.com/minutephysics

Minute Physics provides an energetic and entertaining view of old and new problems in physics -- all in a minute! Created by Henry Reich