| 一个快速的二进制多重精度gcd算法 |
| |
| 引用本文： | 罗永龙,黄刘生,周智. 一个快速的二进制多重精度gcd算法[J]. 中国科学技术大学学报, 2002, 32(5): 542-545 |
| |
| 作者姓名： | 罗永龙 黄刘生 周智 |
| |
| 作者单位： | 1. 中国科技大学计算机系,安徽合肥,230027;安徽师范大学计算机系,安徽芜湖,241000
2. 中国科技大学计算机系,安徽合肥,230027 |
| |
| 基金项目： | 国家自然科学基金 (10 0 710 0 1)，国家 973项目 (G19980 30 4 0 3)，中科院支持高水平大学项目 (KY2 70 6 )资助 |
| |
| 摘 要： | 求两个整数的最大公因子（gcd)的经典的Euclid算法时间复杂度为O（ln^3n)，不适宜于多重精度运算。论文证明了gcd的相关性质，提出了一个基于二进制的、适用于多重精度运算的改进算法，其时间复杂度为O（ln^2n)。
|
| 关 键 词： | 二进制 多重精度gcd算法 Euclid算法 最大公因子 时间复杂度 公钥密码体制 |
| 文章编号： | 0253-2778(2002)05-0542-04 |
A Fast Algorithm for Computing gcd Based on Binary Multi-Precision |
| |
| LUO Yong long ,,HUANG Liu sheng ,Zhou Zhi. A Fast Algorithm for Computing gcd Based on Binary Multi-Precision[J]. Journal of University of Science and Technology of China, 2002, 32(5): 542-545 |
| |
| Authors: | LUO Yong long HUANG Liu sheng Zhou Zhi |
| |
| Affiliation: | LUO Yong long 1,2,HUANG Liu sheng 1,Zhou Zhi 1 |
| |
| Abstract: | |
| |
| Keywords: | gcd Euclid algorithm multi precision binary |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
