Weil对和Tate对在群结构查找新方法上的实施

摘要

针对Tate对的计算效率优于Weil对问题仍然存疑，有待进一步验证，以及Miller提出的二元群结构参数选择算法属于概率型算法，算法效率不高的问题，建立了Tate对和Weil对执行效率的分析模型，提出一种利用椭圆曲线的阶是扭曲值的平方关系查找扭曲值参数的新方法。研究表明，在扭曲值较小时，Tate对的计算效率优于Weil对，与已有研究结果一致，但当扭曲值很大时，Weil对的计算效率优于Tate对，同时扭曲值参数查找新方法的时间复杂度小于Miller方法的时间复杂度O(M),相对Miller的概率方法，新方法为确定型方法。分析和实例验证了分析模型的正确性，而且新方法极大地提高了参数选择的效率和准确性。

关键词

Weil对 / Tate对 / Miller算法 / 素数有限域 / 离散对数