Shor算法能够在多项式时间内分解一个大数的质因子,对现行RSA公钥加密体系的安全性提出严峻挑战。很多研究人员提出了Shor算法的改进,其中Zalka的改进使用改造的Schonhage-Strassen算法来降低Shor算法的复杂度,并提出量子电路来计算Schonhage-Strassen算法中用到的快速费马数变换。然而,Zalka提出的电路会产生垃圾位。在量子计算中,没有得到处理的垃圾位会和运算结果纠缠并对其产生影响,最坏情形下会导致运算结果出错。本文提出一个不产生任何垃圾位的量子电路来计算快速费马数变换。对于长度为b的n+1位整数序列,已知最好的电路需要使用17/2 nblog b个Toffoli门来计算该序列的费马数变换,同时会产生3/2b log 6位垃圾位；相比之下,本文提出的电路则需要使用19/2 nb logb个Toffoli门来完成同样的任务,但是不会产生任何垃圾位。这个结果是通过洞察运算结果和垃圾位之间的关系,并审慎地选择垃圾位清除方法而得到的。本文提出的电路为Shor算法的时间复杂度从O(n~3)降低为O(n~2 logn log logn)填补上重要一环。