G - Physics – 06 – F
Patent
G - Physics
06
F
G06F 7/44 (2006.01) G06F 7/72 (2006.01)
Patent
CA 2225899
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 F2" 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 i th 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 i th basis element of the ONB representation of element C, arranged in polynomial order, initializing a register A, selecting a digit ci of the vector C, computing a partial product vector A of the i th 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 n th 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.
L'invention est une méthode de calcul du produit D de deux éléments B et C d'un corps fini modulo un polynôme irréductible f1(x), ces éléments B et C étant représentés en fonction d'une base normale optimale du type 1 sur un corps F2'' et le polynôme irréductible f1(x) étant de degré n. La méthode de l'invention comprend les opérations suivantes : représentation de l'élément B sous la forme d'un vecteur de chiffres binaires bi, où bi est le coefficient du i-ème élément de base de la représentation de l'élément B dans la base normale optimale en ordre polynomial; représentation de l'élément C sous la forme d'un vecteur de chiffres binaires ci, où ci est le coefficient du i-ème élément de base de représentation de l'élément C dans la base normale optimale, en ordre polynomial; initialisation d'un registre A; sélection d'un chiffre ci du vecteur C; calcul du vecteur de produit partiel A du i-ème chiffre ci de l'élément C du vecteur B; introduction du produit partiel dans le registre A; décalage du contenu du registre A; réduction du produit partiel A par un multiple f2(x) du polynôme irréductible f1(x) si les bits aux positions supérieures à n sont des 1; stockage du produit partiel réduit dans le registre A; répétition des opérations pour chaque bit successif du vecteur C, le registre A contenant le vecteur de produit final quand ces répétitions sont terminées; et réduction du vecteur du produit final A par le polynôme irréductible f1(x) si le n-ème bit du registre est 1. La réduction par un multiple du polynôme irréductible se fait simplement par un décalage des produits partiels.
Lambert Robert J.
Vadekar Ashok
Blake Cassels & Graydon Llp
Certicom Corp.
LandOfFree
A method and apparatus for finite field multiplication does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with A method and apparatus for finite field multiplication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A method and apparatus for finite field multiplication will most certainly appreciate the feedback.
Profile ID: LFCA-PAI-O-1821534