检索结果-内蒙古大学图书馆

primality proving via one round in ECPP and one iteration in AKS

JOURNAL OF CRYPTOLOGY 2007年第3期20卷 375-387页

作者： Cheng, Qi Univ Oklahoma Sch Comp Sci Norman OK 73019 USA

In August 2002, agrawal, kayal and saxena announced the first deterministic and polynomial-time primality-testing algorithm. For an input n, the Agarwal-kayal-saxena (AKS) algorithm runs in time Omicron (log(7.5) n) (heuristic time Omicron (log(6) n)). Verification takes roughly the same amount of time. On the other hand, the Elliptic Curve primality Proving algorithm (ECPP) runs in random heuristic time 6 (log6 n) (some variant has heuristic time complexity Omicron(log(4) n)) and generates certificates which can be easily verified. However, it is hard to analyze the provable time complexity of ECPP even for a small portion of primes. More recently, Berrizbeitia gave a variant of the AKS algorithm, in which some primes (of density Omicron(1/log(2) n)) cost much less time to prove than a general prime does. Building on these celebrated results, this paper explores the possibility of designing a randomized primality-proving algorithm based on the AKS algorithm. We first generalize Berrizbeitia's algorithm to one which has higher density (Omega (1/log log n)) of primes whose primality can be proved in time complexity 6(log4 n). For a general prime, one round of ECPP is deployed to reduce its primality proof to the proof of a random easily

关键词： computational number theory primality testing elliptic curve primality proving agrawal-kayal-saxena primality-testing algorithm algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：