大整数分解问题是指将一个大合数分解为素数因子的计算难题，在经典计算下没有多项式时间算法，目前最快的数域筛法（NFS）也仅能达到亚指数复杂度；该问题是RSA等公钥密码学的安全基石，但Shor算法表明量子计算机可在多项式时间内解决它，从而对现有密码体系构成根本性威胁。