傅里叶变换，是如何跨界“秒杀”大数分解难题的？

对于15这个数字，我们用瞪眼法就能知道它的因数。

但如果摆在你面前的，是一个617位的大数呢？

只有乘积，要找出这两个素数，地球上所有计算机加起来，也需要上亿年的穷举。

但 1994 年，一个秀儿提出一个算法。

他极其巧妙地把“大数分解”这个代数问题，转换成了一个看起来八竿子打不着的新问题：寻找周期。再用（量子版）傅立叶变换，把周期测出来。

这就是shor算法。

今天，我们一起来看看，这到底是怎么个事儿～

别害怕，仅需数学基础知识就能看懂喵