SIDH中3^(e_(3))-挠基的快速生成

Fast Generation of 3^(e_(3))-torsion Basis in SIDH

SIDH协议作为抗量子计算的同源密钥交换协议,具有高安全性和公钥长度较小的优点,但同时也有相对较长的计算时间,如何提升SIDH实现效率还是待解决的问题。本文在近些年形成的挠基生成技术基础上对3^(e_(3))-挠基生成提出改进算法,使得生成挠基时在随机点的阶为2^(r)的情况下,减少e_(2)-r次点2倍计算,尽可能地降低使用余因子乘法的频率,更快地避免不符合条件的随机点,同时也就更快地找到正确阶数的点,从而提高整体生成基的效率。

As a homogenous key exchange protocol of the anti-quantum computation,SIDH protocol has advantages of high security and relatively short public key length.However,for the problem of long calculation time,improving the efficiency of implementing the SIDH is still an unsolved issue.Based on the research achievements in technologies of generating torsion basis in recent years,an modified algorithm of generating 3^(e_(3))-torsion basis is proposed in this paper.With the algorithm,when the order of random points is 2^(r),the number of double point calculation will decrease by e_(2)-r.In the algorithm,utilization frequency of the cofactor multiplication is reduced to the greatest extent and incompetent random points are avoided more quickly,to find the points with correct order more rapidly and to improve the efficiency of generating the basis.