对Schoof算法加速方法的研究

介绍两种计算椭圆曲线离散对数的求解算法——袋鼠算法和BSGS算法,并比较了它们各自的特点。将它们应用于对Schoof算法的加速过程中,提出了加速后的算法。实验结果说明加速后可以获得很大的速度的提升。

SEA算法的有效实现

选取安全椭圆曲线的核心步骤是对椭圆曲线阶的计算.SEA(Schoof Elkies Atkin)算法是计算椭圆曲线阶的有效算法,同种圈(isogeny cycles)方法是Morain对SEA算法改善的一种重要局部优化技术.在实现了Fp上SEA算法的前提下,对同种圈方法作了进一步改进,就SEA算法中各方法的综合运用提出一种方案,并且对用SEA算法选取素数阶和拟素数阶椭圆曲线速度上的优化作了一些讨论,所获得的一些速度指标和国际公开资料上的指标有可比性.

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

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

利用超奇异椭圆曲线进行素性检验(英文)

根据超奇异椭圆曲线有理点个数与素数的关系,提出一个具有多项式时间复杂度的素性检验的概率型算法.对于给定的整数N,如果N≡3(mod4)或者N≡1(mod3),该算法具有多项式时间O(log8N).在广义黎曼假设成立的情况下,对于所有整数都具有这一时间复杂度.

Schoof算法及其在椭圆曲线密码体制中的应用

Schoof算法是一种确定性算法,用于计算有限域Fq上椭圆曲线上的点的个数#GFq。详细介绍了Schoof算法,并应用它构造了一种方法随机生成安全的椭圆曲线,在此椭圆曲线上实现的加密系统可以抵抗Pohlig-Hellman攻击。