October 28, 2012

Shor's algorithm and Quantum Fourier Transform

This post assumes you have a sound understanding of Quantum Mechanics, more precisely eigenstates,┬ásuperpositions and entanglements Shor’s algorithm allows us to find a factor of any composite number $$N$$ in $$O((log\ N)^2 (\ log^k\ (log\ N)^2))$$ for any random $$k$$, which is important in this scope to understand, as cryptography’s security baseline is founded on the fact that factoring cannot happen in polynomial time - I have talked on this subject in my post Yes Diffie-Hellman is secure, quoting myself ... Read more