量智信息中心_量科网

求解椭圆曲线离散对数问题（ECDLP）对于评估广泛部署的椭圆曲线密码系统的量子安全性至关重要。因此，最小化执行此算法所需的逻辑量子比特数量成为一个关键目标。在肖尔算法的实现中，空间复杂度主要由点加法过程中的模逆运算决定。从扩展欧几里得算法（EEA）出发，该团队改进了Proos和Zalka的寄存器共享方法，并提出一种空间高效的可逆模逆算法。该研究使用长度寄存器结合位置控制算术，以紧凑形式在整个计算过程中存储中间变量。随后优化了逐步更新规则，并给出所得受控算术组件的具体电路构造。由此得到的模逆电路使用 \(3n + 4\lfloor \log_2 n \rfloor + O(1)\) 个逻辑量子比特和 \(204n^2\log_2 n + O(n^2)\) 个托弗利门。通过将该模逆组件插入受控仿射点加法电路，该工作获得了一个空间高效的ECDLP算法，仅需 \(5n + 4\lfloor \log_2 n \rfloor + O(1)\) 个量子比特和 \(O(n^3)\) 个托弗利门。特别地，对于256位素域曲线，该团队的估计将逻辑量子比特数减少至1333个，而此前Häner等人的低宽度实现则需要2124个。