基于GCD算法的GF(2m)上高速带模除法

2008 年 10 月Journal on CommunicationsOctober 2008 第 29 卷第 10 期通 信 学 报Vol 29 No 10 基于 GCD 算法的 GF 2m 上高速带模除法 丁勇 1 2 桂丰1 1 桂林电子科技大学 数学与计算科学学院 广西 桂林 541004 2 西安电子科技大学 计算机网络与信息安全教育部重点实验室 陕西 西安 710071 摘 要 对常规 GCD 算法进行了深入分析 改进了算法的判断标准和体系结构 使得每轮迭代中的比较次数由 4 次降低为 3 次 与此同时 迭代次数不再固定为 2m 改变成上限为分母的长度与 m 之和 从根本上加快了 GCD 算法的效率 在此基础上 根据 A Zadeh 的思想 将新算法分别扩展到基 4 基 8 比较次数分别降低为 50 和 34 从而大大缩短了计算时间 通过 MATLAB 实验验证了算法改进取得了很好的效果 关键词 GCD 算法 有限域 基数 8 中图分类号 TP309 文献标识码 A 文章编号 1000 436X 2008 10 0199 06 High speed modular divider based on GCD algorithm over GF 2m DING Yong1 2 GUI Feng1 1 School of Mathematics and Computational Science Guilin University of Electronic Technology Guilin 541004 China 2 Key Lab of Computer Networks and Information Security of Ministry of Education Xidian University Xi an 710071 China Abstract With an in depth analysis improvement was done on the architecture and the determinant standard of the traditional GCD algorithm to build a novel algorithm It reduces the comparisons from 4 to 3 in each iteration Moreover it s iteration number is no longer fixed 2m but the upper bound of the sum of the length of the denominator and m Hence the efficiency is fundamentally increased Furthermore based on A Zadeh s ideology the new algorithm was extended to radix 4 and 8 respectively such that the number decreased 50 and 34 comparing with the original one thereby greatly reducing the computing time Experiments with MATLAB proved the efficiency of our new algorithms Key words GCD algorithm finite field radix eight 1 引言 在数据通信系统中 尤其是编码和密码学中 广泛使用着有限域的算术运算 特别是随着椭圆 曲线密码体制 ECC 的发展 需要大量地使用 有限域上除法 恰恰除法又是最耗费时间的运算 为此人们已经做出了很多尝试以提高除法的运算效 率 1 15 这些各式各样的方法主要可分为以下 3 类 基于费尔马定理的除法 基于最大公约数 GCD 算法的除法 通过求解线性方程组 或者 通过求逆 本文属于第二类算法 相同的条件下 GCD 算法在各类算法中能最有效地计算带模除法 12 200 通 信 学 报第 29 卷 GCD 算法主要经历了下列几个阶段 古典 的 GCD 算法是基于计算逆元 其 1 mod BxP x 中是域上的不可约多项式 因此要计算 P x 只需要再额外计算一次带模 mod A xB xP x 乘法即可 基于古典 GCD 算法 在文献 14 中 N Takagi 提出了 while 循环 但是该算法不能确定 具体的迭代次数 以至于计算时间是不定的 随着扩展的欧几里德算法的出现 GCD 算法进入 了一个崭新的时代 Hoon Kim 在文献 2 3 中提出 了新的算法 for 循环取代了 while 循环 从而能 够确定具体的迭代次数 A Zadeh 在文献 1 中提 出将 GCD 算法的从基数 2 扩展到 4 本文针对常规算法的执行效率 改进了算法 的判断标准和体系结构 使得每轮迭代中的比较 次数由 4 次降低为 3 次 从根本上加快了 GCD 算 法的效率 并且迭代次数不再固定为 2m 而是上 限为分母的长度与 m 之和 同时 运用文献 1 的 思想将改进后的 GCD 算法分别扩展到基 4 基 8 使得比较次数分别降低为 50 和 34 最后通 过用 matlab 编程实现各个算法 比较它们的计算 时间 结果表明改进算法效率提高了 17 而扩 展基数后效率更是提高了 38 和 43 2 常规 GCD 算法 令是有限域上的元素 A xB x GF 2 m 为不可约多项式 P x 1 12 1210 mm mm A xaxaxa xa 2 12 1210 mm mm B xbxbxb xb 3 1 110 mm m P xxpxp xp 具有以下性质 GCD A B 1 A 和 B 都是偶数 那么 2GCD A B 2 2 GCD AB 2 A 是偶数 B 是奇数 那么 GCD A B 2 GCD AB 3 A 和 B 都是奇数 那么 GCD A B 2 GCDABB 这些性质是 GCD 算法的基础 如表 1 所示 反复运用这些性质成功解决 了 mod A xB xP x 表 1GCD 算法性质 a0b0 GCD A B 002 2 2 GCD AB 01 2 GCD AB 11 2 GCDABB 算法 1 基数 2 GCD 算法 若分母最后 一比特 LSB 是 1 则通过带模加法将分母的 LSB 化为 0 分子分母同时除以 x GCD 算法的中心思想是 通过恒等变换 降 低分母次数 直到分母变为 1 即 不断地降次 使得分母为零次 具体算法如下 0 0 mod 0 12 0 1 1 1 1 1 input A x B x P x output A xB xP x RB x SP x UA x V for itom if statethen cntcnt if rthen R SSR RU VVU U state else cntcnt if rthen R SSR SU VVU 0 0 mod U if cntthen state RR x UU xP x end loop return V 变量 state 和 cnt 的初始值由 A x和共同 B x 决定 cnt 表示 A 与 B 的次数差 state 记录 A B 哪个有更高的次数 由于算法的中心思想就是分 母的降次 总体要求降低分母次数 因此算法都 围绕分母来展开 由此 当分母的 LSB 为 0 时 分子 分母同 时除以 x 就能保证分母降低次数 当分母的 LSB 为 1 时 此时若直接除以 x 不但不能降低 分母的次数 反而会增加 因此在这里 利用最 大公约数的性质 2 GCD A BGCDABB 收稿日期 2008 06 21 修回日期 2008 09 28 基金项目 西安电子科技大学网络与信息安全教育部重点实验室开放基金 资助项目 2008CNIS 03 广西教育厅基金资助项 目 ZT5800 Foundation Items Open Grant of Key Lab of Computer Networks and Information Security of Ministry of Education Xidian University 2008CNIS 03 The Department of Education of Guangxi Provincial Grant ZT5800 第 10 期丁勇等 基于 GCD 算法的 GF 2m 上高速带模除法 201 先给分母加上一个 LSB 同样为 1 的多项式 S x 相加以后 LSB 就变为 0 了 再除以 x 就能降低 分母的次数 当然不能随便选取 它要满足 S x 等值变换的条件 通常情况下域上的不可约多项式的 LSB 都等 于 1 只有例外 大家都知道 P xx 则 mod A xA xP xP x 0 mod mod mod U xV xU x P xP x R xS xR xP x U x P x R x 因此赋初值 这样一来 0S xP xV x 分母的 LSB 变为 0 了 但是此时分母的次数变为 也就是 m 次 同时做变换 1P x 于是就有 这SRVU modmod UV PP RS 样就为下一轮迭代做好准备 modmod UUV PP RRS 如此经过 2m 轮的迭代 分母的次数就能降为 0 次 最终 V 的值就是所求的结果 3 改进的 GCD 算法 在常规算法中 总体的结果是使分母的次数 降低 但是在某些条件下 分母的次数会增加 所以长度不大于 m bit 的分母需要进行 2m 轮的迭 代才能使得次数降成 0 事实上 由于找不到更合适的初值 赋初值 分母的次数变为 m 次 这 0S xP xV x 是不可避免的 但是从这之后 由于和 S x 有了恰当的值 我们完全有能力使得分母的 V x 次数不断降低 因此迭代的次数应该改变 值时的次数再加上 m S xV x 算法 2 改进的 GCD 算法 在常规算法的 基础上 删除了变量 state 和 cnt 改变变量 R 和 S U 和 V 的替换标准 当 S 的长度大于 R 的长度 则进行替换 增加跳出循环的判断 当 R 的长度为 1 时 跳出循环 具体算VU 法如下 0 mod 0 1 1 1 R input A x B x P x output A xB xP x RB x SP x UA x V for itolength Bm if length R VU break if r if lengthlength S R SRS RU VUV U else RRSUUV RR x UU x end loop return V 常规算法是以变量 state 和 cnt 作为依据进行 判断的 但是这并不能保证分母次数的依次降低 究其根源是因为不能正确地抓住 R 和 S U 和 V 的替换时机 在不恰当的时候对它们进行替换 有很大可能性会使得迭代后分母的次数不降反增 当 R 的 LSB 为 1 并且 S 的长度大于 R 的长度时 就需要对 S 进行替换 否则 分母是不可能降低 次数的 增设跳出循环的判断可以在某些特殊条件下 更快地得到结果 比如 当 应该做的 k B xx 只是进行 k 次分子分母同时除以 x 分母次数已经 降为 0 此时的分子 U 就是要的结果 那么根据常规 GCD 算法是怎么做的呢 首先 是做完 k 次除法 在这之后 V 的值确实是从 0 更 换为 U 然而循环并没有结束 迭代还将继续下 去 因此增设一个判断条件在某些情况下可以提 高计算效率 4 GCD 算法的扩展 4 1 A Zadeh 的扩展 A Zadeh 提出了将算法基数由 2 扩展到 4 的思 想 使得原来需要进行 16 次比较的迭代合并成仅 需要比较 12 次的迭代 提高了计算效率 算法 3 基数 4 的 GCD 算法 在基数 2 的常 规 GCD 算法的基础上 分析一次迭代后的结果 据此来进行下一步迭代 在此基础上 A Zadeh 对判断条件进行了进一 202 通 信 学 报第 29 卷 步的分析整合 将原本需要 12 次的比较划为 10 次的比较 具体算法如下 input A xB xP x modoutput A xB xP x 0 RB xSP x UA x V 1for ito m 1 0 00R UR Uwhenrr 1 01 0 00elseRS UVwhenrrs s 1 011 01 01elseRS UV S VS V 1 0 100whenstateor rr else 2 RU x 1 01 10elseR U 1if statethen 1 cntcnt 0 0cntcnt end if 0if cntthen 0 state 01state end if 22 mod mod UU xP xRR xP x end loop return V 然而由于扩展的基础是常规 GCD 算法 由于 该算法的判断依据不够完善 导致扩展的时候继 承了前者的不足 4 2 新算法的扩展 从 A Zadeh 的思想得知 扩展能很大程度地 提高计算效率 因此对新算法做出了相应的扩展 基数由 2 扩展到 4 和 8 4 2 1 扩展到基数 4 算法 4 基数 4 的高速 GCD 算法 以改进的 GCD 算法为基础 对其一次迭代结果进行分析 判断 做出二次迭代得出结果 并对满足整合条 件的情况进行了合并 最终得到不同条件的8 个类别 对一次迭代结果进行分析 首先要分析一 次迭代后 R 值的变化 得到正确的 LBS 要充 分考虑到 S 和 R V 和 U 替换的因素 这是区别 于常规算法的关键 具体算法如下 input A xB xP x modoutput A xB xP x 第 10 期丁勇等 基于 GCD 算法的 GF 2m 上高速带模除法 203 1 0 22 1 0 0 11 0 12 1 22 00 10 1 1 0 B R R RS RS RB xSP x UA x V for itolm if lVU break elseif ldo radixGCD algorithm elseif rr RR xUU x elseif rr if ll R SR xSx R xU V U xVx U x else RR xSx UU xVx elseif r if rs if ll R S 2 2 22 11 1 RS RS RSxRU V UVxU else RRSxUUVx elsers if ll R SRSxRx RU V UVxUx U elseif ll R SRSxSxRSx U VUVxVx UVx else RRSxSx UUVxVx end loop return V 4 2 2 扩展到基数 8 算法 5 基数 8 的高速 GCD 算法 以基 4 的 高速 GCD 算法为基础 对其一次迭代结果进行分 析判断 使用基 2 的 GCD 算法进行二次迭代得出 结果 并对满足整合条件的情况进行了合并 最 终得到不同条件的 22 个类别 类似于从基数 2 扩展到 4 同样的方法 将基 数从 4 扩展到 8 只不过是复杂度增加了 具体算 法如下 由于算法太长 只列举 R 和 S 的变化 U 和 V 的变化与之相对应 3 2 1 0 2 1 0 2 mod 0 13 1 22 34 000 100 2 B R R R RS input A xB xP x output A xB xP x RB xSP x UA x V for itolm if lVU break elseif ldo radixGCD algorithm elseif ldo radixGCD algorithm elseif r rrRR x elseif r rr if llR SR xSx R 2 2 1 0 21 2 2 01122 3 10 0 1 1 1 1 RS RS RS RS x elseRR xSx elseif rr if rs if ll R SR xSxR x elseRR xSx elseif ll R SR xSxR xx R x elseif llRR xSxSx elseR S R xSxSxR xSx elseif rrsrs if llR SRSxR else 3 01122 1 1 RS RS if ll R SRSxRxRSx elseif ll R SRSxRx R 2 22 1 RS RS elseif llRRSxSx elseR SRSxSxRSx elseif ll 221 2 221 0 1 0 RS if rsr R SRSxRxR elseif ll R SRSxRxRx R else R SRSxRxRx RSxRx elseif rss 2 2 1 RS RS RS if llR SRSxSxS elseR SRSxSxRSx elseif ll R SRSxSxRSxxRSx elseif llRRSxSxSx elseR SRSxSxSxRSxRx end loop return V 本文总共介绍了 5 个算法 如表 2 所示 表 2 中 1 表示常规 GCD 算法 2 表示改进 GCD 算法 3 表示 A Zadeh 基 4 算法 4 表示基 4 改进 GCD 算法 5 表示基 8 改进 GCD 算法 使用 MATLAB 做实验 在中测试 每 12 GF 2 mod A xB xP x 千次平均运行时间的结果分别为 常规GCD 算法 为 2 424 3s 改进 GCD 算法为 2 004 4s A Zadeh 基 4 算法为 1 904 0s 基 4 改进 GCD 算法为 1 495 6s 基 8 改进 GCD 算法为 1 381 7s 其中 P x 111111111111 通过测试结果 各个算法的执行效率比较结 果如表 3 所示 表 3算法提高速度百分比 改进算法比较基础前者与后者的比较 改进 GCD 算法常规 GCD 算法提高了 17 3 的速 度 A Zadeh 基 4 算法常规 GCD 算法提高了 21 5 的速 度 改进基 4 算法常规 GCD 算法提高了 38 3 的速 度 改进基 4 算法改进 GCD 算法提高了 25 4 的速 度 改进基 8 算法常规 GCD 算法提高了 43 0 的速 度 改进基 8 算法改进 GCD 算法提高了 31 1 的速 度 5 结束语 本文针对常规 GCD 算法的运算效率 改进了 其判断标准和算法结构 减少了比较次数 从根 表 2算法运行时间的比较 A x B x mod A xB xP x 12345 1 0 1 1 0 11 0 0 0 1 0 12 562 01 797 01 906 01 266 01 219 0 1 1 1 0 0 11 0 0 1 0 0 0 12 719 02 344 02 156 01 797 01 594 0 1 0 0 0 1 11 0 1 1 0 0 1 12 438 02 078 02 172 01 516 01 453 0 1 0 1 0 0 1 11 1 0 1 1 1 12 469 02 359 01 891 01 828 01 687 0 1 0 1 11 0 0 0 0 0 11 547 01 656 01 141 01 218 01 110 0 1 1 0 1 1 10 1 1 0 0 1 1 12 672 01 953 02 109 01 485 01 359 0 1 1 0 0 10 0 0 1 0 1 0 12 563 01 844 01 953 01 359 01 250 0 注 若 则表示为 38 1A xxxx 110100001A x 第 10 期丁勇等 基于 GCD 算法的 GF 2m 上高速带模除法 205 本上提高了算法的效率 使得运算效率提高了 17 3 在此基础之上 进一步将新算法分别扩展 到基数 4 基数 8 又使得运行效率再次提高了 25 4 和 31 1 随着椭圆和超曲线密码体制的不 断发展 带模除法的使用量将进一步攀升 新算 法具有一定的应用价值 参考文献 1 ABDULAH A Z High speed modular divider based on GCD algorithm A ICICS 07 C Zhengzhou China 2008 189 200 2 KIM H C PYO H C High speed division architecture for GF 2m J Electronics Letters 2002 38 15 835 836 3 HOON K C KWON S PYO H C Efficient bit serial systolic array for division over GF 2 sup m elliptic curve cryptosystem applications A Proceedings of the 2003 International Symposium on Circuits and Systems IEEE Los Alamitos C 2003 252 255 4 DALY A MARNANE W KERINSY T Fast modular division for application in ECC on reconfigurable logic A FPL 2003 C Springer Heidellberg 2003 5 GUAJARDO J PAAR C Itoh tsuji inversion in standard basis and its application in cryptography and codes J Design Codes and Cryptography 2002 25 2 207 216 6 RODRIGUEZ HENRIQUEZ F MORALES LUNA et al Parallel Itoh Tsujii multiplicative inversion algorithm for a special class of trinomials J Designs Codes and Cryptology 2007 45 1 19 37 7 MCIVOR C MCLOON E MCCANNY J V Improved Montgomery modular inverse algorithm J IEEE Electronics Letters 2004 40 18 1110 1112 8 SAVAS E A carry free architecture for montgomery inversion J IEEE Transactions on Computers 2005 54 12 1508 1519 9 KAIHARA M E TAKAG I A VLSI algorithm for modular multiplication division A Proceedings of the 16th IEEE Symposium on Computer Arithmetic C 2003 220 227 10 WEI S W VLSI architectures for computing exponent