二元域快速通用模约减方法

摘要

本发明公开了一种二元域快速通用模约减方法，提取二元域下不可约多项式中所有非零项的次数；预计算约减位置参数q_i和移位参数r_i，满足(m-d_i)＝w×q_i+r_i，其中，w＞0，为每次循环中约减的数据块的位数；根据m、被约减数据的位数和被约减数据块的位数计算约减循环次数，从最高数据块到最低数据块逐块进行约减，其中最低数据块中的部分位进行约减；对被约减数据块进行约减，采用多次数据块的加法来完成数据块的约减，根据预计算的约减位置参数q_i和移位参数r_i计算被约减数据块多次加法的位置。本发明适用于所有的二元域上的不可约多项式的模约减运算，大幅提高二元域上的椭圆曲线以及双线性对的运算效率。

主权项

1.一种二元域快速通用模约减方法，其特征在于：步骤1，提取二元域下不可约多项式中所有非零项的次数，即为m，d_i，其中，f(x)为m次不可约多项式，m为二元域的扩张次数，d_i是不可约多项式中除了最高位之外任一非零项的次数；步骤2，预计算约减位置参数q_i和移位参数r_i，满足(m-d_i)＝w×q_i+r_i，其中，w＞0，为每次循环中约减的数据块的位数；步骤3，根据m、被约减数据的位数L比特和被约减数据块的位数w比特，计算约减循环次数，从最高数据块即第个数据块到最低数据块即第个数据块，逐块进行约减，其中最低数据块中的部分位即进行约减；步骤4，对被约减数据块进行约减，采用多次数据块的加法来完成数据块的约减，根据预计算的约减位置参数q_i和移位参数r_i计算被约减数据块多次加法的位置；上述步骤中，i≥0，当i＝0时，d₀＝0。