公开(公告)号：US20010054053A1

公开(公告)日：2001-12-20

申请号：US09477678

申请日：2000-01-05

Applicant: Certicom Corp.

Inventor： ROBERT J LAMBERT ,  ASHOK VADEKAR

IPC: G06F007/00

CPC classification number: F01N13/14 ,  F01N3/28 ,  F01N3/2803 ,  F01N2240/20 ,  F01N2330/14 ,  F01N2330/22 ,  Y02A50/2322

Abstract: A method of computing the product D of two finite field elements B and C modulo an irreducible polynomial f1(x), wherein the finite field elements B and C are represented in terms of an optimal normal basis (ONB) of Type 1 over a field F2n and the irreducible polynomial f1(x) being of degree n, which comprises the steps of representing the element B as a vector of binary digits bi, where bi is a co-efficient of an ith basis element of the ONB representation of element B, in polynomial order, representing the element C as a vector of binary digits ci, where ci is a co-efficient of an ith basis element of the ONB representation of element C, arranged in polynomial order, initializing a register A, selecting a digit ci of vector C, computing a partial product vector A of the ith digit ci of the element C and the vector B, adding the partial product to the register A, shifting the register A, reducing the partial product A by a multiple f2(x) of the irreducible polynomial f1(x) if bits in a position above n are set, storing the reduced partial product in the register A, repeating for each successive bit of the vector C and upon completion the register A containing a final product vector; and reducing the final product vector A by the irreducible polynomial f1(x) if an nth bit of the register is set. The reduction step by the multiple of the irreducible polynomial simply involves a shift operation performed on the partial products.

Abstract translation: 计算两个有限域元素B和C的不可约多项式f 1（x）的乘积D的方法，其中有限域元素B和C以字段1的最佳正态基（ONB）表示 F2n和不可约多项式f1（x）为度数n，其包括将元素B表示为二进制数字bi的向量的步骤，其中bi是元素B的ONB表示的第i个基元的有效性 以多项式顺序，将元素C表示为二进制数字ci的向量，其中ci是以多项式顺序排列的元素C的ONB表示的第i个基元的有效值，初始化寄存器A，选择数字 ci，计算元素C的第i位ci和向量B的部分乘积向量A，将部分积加到寄存器A，移位寄存器A，将部分乘积A减少多个f2（x ）的不可约多项式f1（x） 设置n以上的位置，将减少的部分乘积存储在寄存器A中，对向量C的每个连续位重复，并且在完成包含最终乘积向量的寄存器A时; 并且如果设置了寄存器的第n位，则通过不可约多项式f1（x）来减少最终乘积向量A. 通过不可约多项式的倍数的减少步骤仅仅涉及对部分乘积执行的移位操作。