有限域上椭圆曲线 Jacobian 群求阶算法综述与比较

摘要：

关于椭圆曲线密码体制（ECC）的研究，如今无论是 ECC 理论还是 ECC 的标准化、产业化都趋于成熟。在 ECC 的设计中，安全椭圆曲线的选取是 ECC 实现的基石，也是其安全性的重要保证。目前，随机选取法是最好的安全椭圆曲线选取方法，其核心思想是对随机生成的椭圆曲线计算其 Jacobian 群的阶。文章主要介绍了几类经典的计算椭圆曲线 Jacobian群阶的算法：Schoof 算法、SEA 算法、Satoh 算法、AGM 算法。在详细介绍 Schoof 算法的基础上，提出了其基于离散对数问题的改进算法：袋鼠算法和大步小步（BSGS）算法的改进方法，并用实验结果说明加速后的算法得到了提升。针对 SEA 算法，文章也提出了其 BSGS 改进算法并通过实例分析比较了原 SEA 算法与 BSGS 改进算法的实现效率。针对 Satoh 算法、AGM算法，文章介绍了算法的理论依据和具体实现，并通过实例分析比较了其优劣性和适用情况。

关键词：椭圆曲线、Schoof 算法、Satoh 算法、AGM 算法

分类号：TP309(计算技术、计算机技术)

资助基金：国家自然科学基金面上项目KYZ083712053

在线出版日期：2014-08-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：41-47