ショアのアルゴリズムは、1994年にピーター・ショアによって開発され、量子コンピュータを用いて整数Nを多項式時間O((log N)³)で因数分解できます。既知の最良の古典アルゴリズム（一般数体ふるい法）は準指数時間で動作します。RSA暗号は大きな数の因数分解の困難さに依存しているため、これは重要です。ショアのアルゴリズムは、剰余べき関数の周期を求めるために量子フーリエ変換を用います。このアルゴリズムは理論的には強力ですが、RSA-2048を破るために実ハードウェアで実行するには数百万個の誤り訂正された量子ビットが必要となり、現在のNISQの能力（最大でも約1000個のノイズのある量子ビット）をはるかに超えています。ショアのアルゴリズムは、ポスト量子暗号の研究やNISTのポスト量子暗号標準化の取り組みの主要な動機となっています。