引用本文:蔡兆政, 瞿云云, 包小敏.两种求二次剩余平方根算法的比较[J].西南大学学报(自然科学版),2019,41(1):60~64
【打印本页】   【HTML】   【下载PDF全文】   查看/发表评论  【EndNote】   【RefMan】   【BibTex】
←前一篇|后一篇→ 过刊浏览    高级检索
本文已被:浏览 257次   下载 183 本文二维码信息
码上扫一扫!
分享到: 微信 更多
两种求二次剩余平方根算法的比较
蔡兆政, 瞿云云, 包小敏1,2
1. 西南大学 数学与统计学院, 重庆 400715;2. 贵州师范大学 数学与计算机科学学院, 贵阳 550001
摘要:
在模是大合数的情况下,求二次剩余平方根是一个困难问题.目前已知的求二次剩余平方根的算法有两种,本文对Cocks和曹珍富的算法进行分析比较,结果表明由Cocks提出的算法效率更高,这对今后求二次剩余平方根时进行算法选择提供了帮助.
关键词:    二次剩余  平方根  中国剩余定理
DOI:10.13718/j.cnki.xdzk.2019.01.009
分类号:O211.4
基金项目:国家自然科学基金项目(61462016);贵州省科学技术基金项目(黔科合J字[2014]2125号);贵州省教育厅青年科技人才成长项目(黔教合KY字[2016]130.
Comparison of Two Algorithms for Finding the Quadratic Residue Square Root
CAI Zhao-zheng, QU Yun-yun, BAO Xiao-min1,2
1. School of Mathematics and Statistics, Southwest University, Chongqing 400715, China;2. School of Mathematical Science, Guizhou Normal University, Guiyang, Guizhou 550001, China
Abstract:
In the case of a large composite number of modules, to find the quadratic residue root is a difficult problem. There are two kinds of algorithms that are known for finding the square root of quadratic residuals. In this paper, the two known algorithms are analyzed and compared, and the results show that the algorithm 1 proposed by Cocks is more efficient than the algorithm 2 proposed by Cao Zhenfu, et al.
Key words:  module  quadratic residue  square root  Chinese remainder theorem
手机扫一扫看