模归约算法表达式自动生成算法设计与实现

杨邓奇，陆正福，左国超

（1.大理学院数学与计算机学院，云南大理 671003；2.云南大学数学系，昆明 650091）

模归约算法表达式自动生成算法设计与实现

杨邓奇1，陆正福2，左国超1

（1.大理学院数学与计算机学院，云南大理 671003；2.云南大学数学系，昆明 650091）

多项式模归约算法是计算机代数中的基本问题之一，在编码算法和密码体制设计中有着广泛应用。基于对模归约数学基础的分析，设计了模归约算法表达式自动生成算法，只要选择实现所需的字宽w和模多项式M（x）的系数，即可自动生成对应的模规约算法表达式，为模规约算法在密码编码学中的应用提供了基础。

模归约算法；计算代数；算法表达式自动生成

代数算法的设计、分析、实现和应用构成了计算代数的主要研究内容，其特征是无误差的符号计算。有限结构上的代数算法是计算代数的基础问题之一〔1-2〕，普遍涉及模归约计算：求一个多项式（大整数、代数结构）关于另一个多项式（整数、代数结构）的余式（余数、商结构）等。在实际应用中，循环码、对称密码算法AES〔3-4〕、椭圆曲线密码体制（ECC）〔5-6〕、无证书密码系统（CL-PKC）〔7〕等在软件实现中经常涉及的则是GF（2m）上的模归约计算，可归为GF（2）上的多项式模归约。从软件实现的角度看，机器指令不直接支持抽象代数运算，但GF（2m）上的计算可通过机器支持的位运算及适当的数据结构和算法来实现。鉴于上述，本文研究了GF（2m）上的模归约运算的计算代数基础，并据此设计了模规约算法表达式自动生成的算法。同时，给出算法实现的关键数据结构，并用C语言实现了模归约算法表达式的自动生成，对GF（2m）上的密码、编码计算具有基础意义。

1 问题的提出与符号约定

模归约算法是指：对于给定的模多项式M（x）和任意的多项式a（x），要求给出算法，求a（x）除以M（x）所得的余式a（x）mod M（x）。

模规约算法是各类密码系统实现的基础，出于效率和安全的考虑，不同的密码系统对实现字宽w和模多项式M（x）有着不同的要求。分析表明，模规约算法表达式随着w和M（x）的变换而呈现不同形式，当重新选择实现字宽w或模多项式M（x）时，需要重新推导模规约算法表达式，这是一项非常繁琐的工作。那么，如果选定了模多项式M（x）和字宽w，是否能够自动生成模规约算法表达式以便直接应用，省去繁琐的重复推导过程？本文通过对模规约算法数学基础的深入分析，探索其一般规律，提出模规约算法表达式自动生成算法，对其用C语言进行实现，给出实验结果。

设r（x）=xdα+xdα-1+…+xd2+xd（1以非零幂次下降序列表示），M（x）=xn+（rx）。给定字宽w，对于任意的多项式其中deg（a（x））表示a（x）的最高幂次。若δ＝deg（a（x））mod w，L=⎿deg（a（x））/w」，则多项式a（x）的分段表示（A［L］，A［L-1］，…，A［j］，…，A［1］，A［0］）称为a（x）的字宽为w的字表示，其中A［j］为xj（wajw+ajw+1x1+…+ajw+w-1xw-1）=xjwt（x）的字表示 ajw+w-1…ajw+1ajw，t（x）＝ajw+ajw+1x1+…+ajw+w-1xw-1；若δ≠0，则A［L］的高w-δ位置0。

为了研究算法设计中的一般规律，先给出一个M（x）＝x163+x7+x6+x3+1，w=8时的算法作为研究样例。

上述算法可参见ECC的各类实现文献。不难看出，困难的是迭代计算式的一般形成规律。在模归约研究中，给定模多项式，希望研究A［j］对于A［i］（i

前期针对情形②和③提出了字归约算子、半字归约算子〔9〕。

2 字归约算子

本节假定jw≥n。A［j］关于模多项式M（x）=xn+r（x）的按字归约表达为一个算子，我们将其称为字归约算子，记为R（1，A［j］，M（x），w），定义如下：

其中的计算量涉及2次移位，2次位异或。

3）在di-δ＞w时，用N+⎿（di-δ）/w」替代N，用（di-δ）mod w替代di-δ，可以得到类似2）的结论。

4）在-（w-1）＜di-δ＜0时，表示A［j］先右移N个字，再右移个位，因此该项影响A［j-N］和A［j-N-1］，并且有迭代公式：

其中的计算量涉及2次移位，2次位异或。

5）在di-δ＜-w时，用替代N，用替代di-δ，可以得到类似4）的结论。

3 半字归约算子

本节假定：jw＜n，jw+w-1≥n。由于n=Nw+δ，0＜δ≤w-1，所以j=N，A［N］的0，1，…，δ-1位不在归约范围内，因此应该取为被归约项，

并且称S关于模多项式M（x）=xn+r（x）的归约为半字归约，相应的算子称为半字归约算子（注：此处的“半”并不意味着δ一定是w/2，故笔者将其英文译为semi-，表达不完全之意），记为R（δ，S，M（x），w），定义如下：

（1）式与（2）式可以合并成一个右移δ位的操作。

4 模规约算法表达式自动生成算法设计

对于上述的描述，设计模规约算法表达式自动生成算法如下。

4.1数据结构描述算法采用的数据结构描述如下。

图1给出算法1的数据结构存储示例，将其输出即可得到对应的模规约算法表达式。

图1 模规约算法表达式存储结构图

4.2 算法描述算法的输入为所选择的字宽w和数组d，其中d［0］=α，d［1］=deg（M（x）），r（x）的指数从d［2］开始存储。算法的输出返回链表数组的首地址。算法中insert（node1变量名）表示在p2-＞next中插入node1类型的结点，insert（node2变量名）表示在p2-＞prior中插入node2类型的结点，结点中字符串的赋值本算法中不再具体给出。

算法的思想是：先从首地址开始查找，若找不到对应的结点，则申请结点并插入到链表中（若找到相应的node2），然后查找node1应插入的位置并插入相应的node1。

4.3 算法实现流程图根据上述算法，得到其对应的流程。见图2。

图2 模规约算法表达式自动生成算法流程图

5 实验结果

采用C语言对算法进行实现，程序运行结果如图3。其中字宽w=32，模多项式M（x）=x163+x7+x6+x3+1。改变字宽w或模多项式M（x），可以得到对应的算法表达式。

图3 程序执行结果实例

6 结束语

模规约运算是代数算法中有限结构上计算代数的基础问题之一，在实际的编码密码应用中经常涉及到的是GF（2m）上的模归约计算，且可归为GF（2）上的多项式模归约。本文运用数学方法得到了模规约算法的自动生成算法，并选择了链表数据结构对其进行了程序实现，为模规约算法在编码密码学方面的应用提供基础。

〔1〕Joachim Von Zur Gathen，Jürgen Gerhard.Modern Computer Algebra〔M〕.London：Cambridge University Press，1999：1-40.

〔2〕Mishra B.Algorithmic Algebra〔M〕.Berlin：Springer-Verlag，2001：66-78.

〔3〕程桂花，罗永龙，齐学梅，等.AES算法中基于流水线的可逆S盒设计与实现〔J〕.小型微型计算机系统，2012，33（3）：577-581.

〔4〕王韬，赵新杰.针对AES的Cache计时模板攻击研究〔J〕.计算机学报，2012，35（2）：235-341.

〔5〕任瑞芳，汪学明.基于ECC的广义门限签密方案设计〔J〕.计算机工程与设计，2011，32（1）：17-20.

〔6〕杨邓奇，杨健，杜英国，等.ECC点乘运算在网络并行实现中的装箱问题〔J〕.大理学院学报，2009，8（4）：19-21.

〔7〕Al-Riyami S S，Paterson K G.Certificateless Public Key Cryptography〔M〕.Berlin：Springer-Verlag，2003：452-473.

〔8〕Darrel Hankerson，Julio López Hernandez，Alfred Menezes. Software Implementation of Elliptic Curve Cryptography over Binary Field〔M〕.K.Ko and C.aar（Eds.）：ChES，2000：1-24.

〔9〕陆正福，何英，杨邓奇，等.模归约算法的数学基础研究〔J〕.云南大学学报：自然科学版，2005，27（4）：305-309.

The Design and Implement of Algorithm Expression Auto-generation for Modulo Reduction Operation

YANG Dengqi1，LU Zhengfu2,ZUO Guochao1
（1.College of Mathematics and Computer,Dali University,Dali,Yunnan 671003,China；2.Department of Mathematics,Yunnan University,Kunming 650091,China）

Polynomial modulo reduction operation is one of the fundamental issues of computer algebra,and widely used in coding algorithms and cryptographic system design.Based on the analysis on the mathematic foundation of modulo reduction operation,this paper designs the expression auto-generation algorithm of modulo reduction operation.This algorithm can auto-generate the algorithm expression of modulo reduction operation according to the selected word-width and modulo polynomial.This provides a foundation for the application of modulo reduction algorithm in the areas of cryptography and encode,such as ECC,AES and CL-PKC.

modulo reduction algorithms；computer algebra；algorithm expression auto-generation

O157；TP301.6

A

1672-2345（2013）04-0012-05

云南省自然科学基金资助项目（2010ZC142）

2012-09-07

杨邓奇，讲师，博士，主要从事网络安全、密码学和网络体系结构研究.

（责任编辑 袁 霞）

10.3969/j.issn.1672-2345.2013.04.005