Patent ID: 6052704
Filing Date: 2000-04-18
Classification: G06F

Abstract:
An exponentiation circuit for performing b.sup.N (power N of b) computations in a finite field GF(2.sup.m), where b is an arbitrary element of GF(2.sup.m), m is the field size of said finite field GF(2.sup.m), and N is an integer (0.ltoreq.N.ltoreq.2.sup.m-1 -1) expressed as N=N.sub.0 +N.sub.1 2+N.sub.2 2.sup.2 + . . . +N.sub.i 2.sup.i + . . . +N.sub.m-1 2.sup.m-1 where N.sub.i is selected from among the elements 0 and 1 of said finite field for i ranging from 0 to m-1 (i=0, 1, 2, . . . , m-1), said exponentiation circuit comprising:a group of m multiplex circuits Ui respectively inputting both N.sub.i and b where integer i ranges from 0 to m-1 (i=0, 1, 2, . . . , m-1), and respectively providing output signals Ou.sub.i where Ou.sub.i =b if said N.sub.i =1 and Ou.sub.i =1 if said N.sub.i =0 for i ranging from 0 to m-1; anda group of m-1 power-sum circuits PK i where i ranges from 0 to m-2 (i=0, 1, 2, . . . , m-2), each having a first input pin, a second input pin, and an output pin for providing an output signal Sp=E*F.sup.2 in response to a signal E applied to said first input input pin and a signal F applied to said second input pin, where E and F being arbitrary elements in said finite field, and * being a multiplication operation over said finite field, said Ou.sub.m-1 being applied to said second input pin of said PK.sub.m-2, and said Oui being applied to said first input pin of said PK i for i ranging from 0 to m-2 (i=0, 1, 2, . . . , m-2), said output signal Sp provided by said output pin of said PK i being applied to said second input pin of said PK i-1 for i ranging from 1 to m-2 (i=1, 2, . . . , m-2) said output signal Sp provided by said output pin of said PK.sub.0 is said b.sup.N.