傅里叶变换对称性在整数因式分解中求阶的应用

摘要

大整数因式分解,一直以来都是公钥密码分析的一个研究热点问题之一.对大整数因式分解问题可以归约到基于傅里叶变换求阶问题.经典计算机上求解大整数的因子都是一个NP难题.直到shor算法的出现,大整数分解的难解问题理论上可以在PPT(probabilistic polynomialtime,中文称之为概率多项式时间,是密码协议的一种概率算法,类似于掷硬币)内求解,这种理论上的求解主要是在量子计算机上执行量子傅里叶变换,以求解交换子群的阶为目的.本文把傅里变换的对称性,应用于量子算法大整数因式分解求阶之中,使得其时间与存储空间减半.