基于右移k-ary消减的递归最大公因子算法

• 作者: 曾光 王广赛 韩文报
• 来源期刊: 信息工程大学学报
• 学科: 工学
• 关键词: 最大公因子算法 欧几里得算法 二进制GCD算法 右移k-ary消减 整数最大公因子算法
• 年，卷（期）: 2016,（2）
• 所属期刊栏目: 数学与信息安全
• 页码范围: 190-193
• 页数: 4页
• 分类号: TP301
• 字数: 3987字
• 语种: 中文
• DOI: 10.3969/j.issn.1671-0673.2016.02.012

摘要

对于输入B和C,利用Sorenson的右移k-ary消减(right-shift k-ary reduction)思想提出一种算法用于寻找整数x和y,使得x和y满足Bx-Cy在二进制表示下低比特位部分为0,利用该算法能够大规模降低循环次数,再结合模算法,提出递归最大公因子算法.递归最大公因子算法复杂度虽然对Knuth-Sch(o)nhage算法的复杂度上没有提高,仍然是O(nlog2 nloglogn),但是该算法相比于Knuth-Sch(o)nhage算法实现简单,正确性分析和复杂度分析都比较容易.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	韩文报		19	90	4.0	9.0
2	曾光		14	21	3.0	3.0
3	王广赛		3	6	1.0	2.0