Title of Invention  "A CRYPTOGRAPHIC AND/OR ERROR CORRECTION APPARATUS" 

Abstract  A method of processing binary data representing field elements of an oddcharacteristic finite field GF(pk) is described. The method comprises storing binary data representing at least a portion of a field element of an oddcharacteristic finite field GF(pk) in a register, p being an odd prime number, the field element comprising k coefficients in accordance with a polynomialbasis representation, the binary data comprising plural groups of data bits, wherein each group of data bits represents an associated one of the k coefficients. The method also comprises executing at least one operation on contents of the register such that the plural groups of data bits are processed in parallel. An apparatus comprising a memory and a processing unit coupled to the memory to carry out the method is also described. (FIG1) 
Full Text  EFFICIENT ARITHMETIC IN FINITE FIELDS OF ODD CHARACTERISTIC ON BINARY HARDWARE CROSS REFERENCE TO RELATED APPLICATIONS The present application is related to U.S. Patent Application entitled "Cryptography using finite fields of odd characteristic on binary hardware," Serial No. 10/271,947 (Attorney Docket No. 040001177), and to U.S. Patent Application entitled "Error correction using finite fields of odd characteristic on binary hardware," Serial No. 10/271,945 (Attorney Docket No. 040001178), both filed even date herewith, the disclosures of which are incorporated herein by reference in their entirety. BACKGROUND Field Of The Invention The present invention relates to methods and apparatuses for efficiently carrying out computations hi finite fields of odd prime characteristic on binary hardware. The invention is particularly useful for carrying out such computations in cryptography and in error correction, but is not limited to such uses. Background Information Some Basic Aspects of Finite Fields A finite field (also called a Galois field) is a finite algebraic structure, possessing two Welldefined operations: an "addition" and a "multiplication". A finite field with N Elements exists if and only if N is the power of a prime number, i.e. N=pn for some Prime p=2, 3, 5, ... such as discussed in R. Lidl and H. Niederriter, Introduction to Finite Fields and Their Applications, Cambridge University Press, Cambridge, Revised ed., 1994. This field is unique up to an isomorphism and is normally denoted GF(pn). For a prime p, the ground field GF(p) is simply the integers under addition and multiplication modulo p. In general, if F is a field of q=pl elements (i.e. F=GF(pk)), the extension field of degree / can be defined, denoted as F[t]/(f(t)), where f(t) is a polynomial of degree I, irreducible over F. This extension field may also be referred to as GF(p*). This then gives (the unique) finite field of q' elements. In other words, this is the field of p^p" elements. The number p is called the characteristic of the field. The wellknown fact that the two fields of the same size are isomorphic does not necessarily mean that the mapping between the fields is trivial. However, constructions of such mappings are not necessary for the present invention and, in any event, are within the purview of one of ordinary skill in the art and are discussed in textbooks, such as Introduction to Finite Fields and Their Applications referred to above. There are two predominant ways to represent a finite field. One representation is the normal basis representation well known to those of ordinary skill in the art and such as described in Introduction to Finite Fields and Their Applications referred to above. The main advantage with a normal basis is that it facilitates multiplying elements by themselves, i.e. squaringtype operations. The normal basis representation is not discussed further here. Some computational aspects associated with normal basis representations are discussed in U.S. Patent No. 4,587,627 (Computational method and apparatus for finite field arithmetic), U.S. Patent No. 4,567,600 (Method and apparatus for maintaining the privacy of digital messages conveyed by public transmission), and U.S. Patent No. 5,854,759 (Method and apparatus for efficient finite field basis conversion), the entire contents of each of which are incorporated herein by reference. Another representation is known as the polynomial basis representation. In this representation, field elements of G&($) may be thought of as polynomials of degree at most k1 whose coefficients are field elements of the ground field GF(p), i.e., integers in the set (0, ..., p1). A typical element, y, in the field can therefore be expressed as for some integers by where 0 1. Thus, an element in the field can be written as where each Yi is an element of GF(2fc). Adding field elements a and p in this representation can be done by carrying out the operation Since as , p; are elements of GF(2k), their sum, cq + p; can be computed as the bitwise XOR between the a, and pj. Thus, if k is small enough to fit in a hardware register (typically k(oci, pj) hi these algorithms denotes a procedure carrying out the operation (add, multiply, etc.) on field elements cq and pj in the field GFCp*). First, an addition algorithm, denoted SUM(cc, P), that relates the addition of elements a and P of the extension field GF(pft) to computations to be carried out in the field GFCp*) is given below. i SUM(a,p): for i=0 to /I do 8j=GFjp_k_ADD(ai5 pj) end return where GF__p_k_ADD will be described in detail below. In addition, a multiplication algorithm, denoted PRODUCT(a, P), that relates the multiplication of elements a and P of the extension field GFCp"") to computations to be carried out in the field GFfp1) is now described. Here it is assumed that necessary initializations of DLOG and ANTILOG tables have already been made. Forms of the DLOG and ANTILOG tables will be described below. In addition, exemplary DLOG and ANTILOG tables are given in FIGS. 10A and 11A for a simple illustration for GF(32) to be described later. PRODUCT(cc,p): fori=0to2/2do 5—0 for j=max(0,i/+l) to min(i, M) do 8i=GF_p_k_ADD(Si, GF_p_k_MUL(a,, end end return REDUCER I2*"2 + 8^ t2" + • • • + 8, t + 80 , f(t)) where GF_p_k__MUL and REDUCE(6, f) (the latter computing z(t) mod f(t)) will be described in detail below. It should be noted that the above multiplication algorithm is merely one example of possible multiplication algorithms. For large values of / (e.g., />100), faster performance may be obtained by using Karatsuba's method instead of the simple PRODUCT algorithm above. Karatsuba's method is known to those of ordinary skill in the art and is described, for example, in Seminumerical Algorithms referred to above. Finally, a reduction operation "mod f(t)" necessary for completing the multiplication algorithm, PRODUCT(a, (3), can be done with a wellknown algorithm given below and denoted as REDUCE(8, f> This algorithm can also make use of the present inventive approach for efficient arithmetic hi the field GF^*) to be described. For computational efficiency, f(t) can be chosen to be "sparse", meaning that f(t) has only a few nonzero coefficients (e.g., 3 nonzero coefficients). In this case, f(t) has form f(t)=f, t* + fj tj + f0 for some j between / and 0. It should be noted, however, that it is not necessary hi general for f(t) to have such a sparse. For any value of /, an irreducible polynomial f(t) of degree / can be readily found by methods known to those of ordinary skill hi the art. A general approach for determining an irreducible polynomial f(t) may be found in Sendraanerical Algorithms referred to above, for example. With these comments in mind, the reduction algorithm, denoted REDUCE(8, f), is as follows. REDUCE(5, f) tmpl=GF_p_k_MUL(GF_p_k_INVERSE(fi), f0) tmp2=GF_p_k_MUL(GF_p_k_INVERSE(fz), fy for i=2/2 dovmto 1 do 5w=GF_p_k_SUB(8w, GF_pJc_MUL(tmpl, 8;)) 6i.H=GF_p_k_SUB(Sw+j, GF_p_k_MUL(tmp2, 8,)) end return 8M t'"J + 5wt'2 +  + 8,t + 50. The REDUCE algorithm above is just a normal polynomial division algorithm adapted for the special form of f(t) given above. It should be noted that tmpl and tmp2 can be precomputed because they are fixed once the representation is given, that is, once f(t) is defined. The function GFjp_k_SUB refers to field subtraction hi the field GF(pk), and the function GF_p_k_INVERSE refers to multiplicative inverse computation, both of which are easily implemented given algorithms for GF_p_k_ADD and GF_p_k_MUL and both of which will be described below. An exemplary apparatus 100 for executing the abovenoted algorithms and for implementing other aspects of the invention will now be described with reference to the block diagram of FIG. 1. The apparatus 100 comprises a memory 101 and a processing unit 105 coupled to the memory 101. The apparatus 100 can also comprise an input/output device 103. The processing unit 105 comprises a plurality of registers 107121, which are controlled by logic circuits (not shown) within the processing unit 105. The processing unit 105 can communicate with the input/output device 103 and the memory 101 via electrical connections (e.g., electrical buses) represented by the arrows shown in FIG. 1. It is also possible for the processing unit 105 to communicate with external registers (not shown) located outside the processing unit 105. The processing unit 105 can be, for example, any conventional type of processing unit, such as a Pentiumclass processor or other CPU typically found in personal computers, or it may be a special purpose processor, such as may be found in wireless phones or other handheld devices. It is common for conventional processors used hi personal computers to have eight general purpose registers, such as illustrated by the eight registers 107121 in FIG. 1 (also denoted as registers ah). The registers 107 can be, for example, 8bit registers, 16bit registers, 32bit registers, 64bit registers, etc. Present generation processors for conventional personal computers commonly have 32bit registers. The memory 101 can be, for example, any suitable memory capable of storing computer programs, such as a magnetic disk, a CD ROM, a magnetooptical disk, a flash memory, or other types of memory. In addition to storing computer programs, the memory 101 can also be used to store intermediate or final computational results generated by the processing unit 105 and can also be used to store lookup tables to be utilized during computations. The input/output device 103 can be, for example, any suitable device for passing data to and/or from the processing unit 105, such as a hardwired modem or network interface, a wireless modem, a second memory, an analogtodigital/digitaltoanalog (AD/DA) converter, or other similar types of devices. Separate input and output devices can be utilized in place of a combined input/output device if desired. In addition, the input/output device 103 can be configured to perform guardbit insertion and guardbit removal. Guardbit insertion and guardbit removal are described later in relation to FIGS. 8A and 8B, for example. In one aspect, the memory 101 can store one or more computer programs, and the processing unit 105 can access the memory 101 to execute steps of the computer program(s). These computer programs can include, for example, programs representing the algorithms noted above and programs implementing other aspects of the invention as described below. In addition, although a single processing system 100 having a single processing unit 105 is shown in FIG. 1, it should be understood that the processing system 100 can comprise multiple processing units 105. Moreover, it is possible to embody the present invention using multiple processing systems instead of a single processing system 100. The remainder of the detailed description will focus on describing the inventive approaches for storing binary data representing field elements of GFCp*) in hardware registers and for executing operations on such binary data in a manner to enhance the speed of arithmetic computations involving field elements of GF(pk). In this regard, descriptions of the algorithms GFjp_k_ADD and GFjjJeJMUL, which provide for adding and multiplying field elements of the field GF(pk), will be described. In addition, other apparatuses for implementing the approaches will also be described. According to one aspect of the invention, the apparatus 100 illustrated in FIG. 1 can be used to carry out computations involving field elements of an oddcharacteristic finite field GF(pk) in a manner that enhances computational efficiency compared to conventional approaches for carrying out computations involving field elements of oddcharacteristic finite fields. In particular, the processing unit 105 is configured (e.g., programmed) to store binary data representing at least a portion of a field element of an oddcharacteristic finite field GFCp1*) hi a register, such as register 107 shown in FIG. 1, wherein p is an odd prime number and wherein the field element comprises k coefficients hi accordance with a polynomial basis representation. The processing unit 105 and the register can be viewed as means for storing binary data representing at least a portion of a field element of GF(pk). The binary data comprise plural groups of data bits, wherein each group of data bits represents an associated one of the k coefficients. Thus, binary data representing multiple coefficients of a field element of the oddcharacteristic finite field GF(pk) are packed into a single hardware register according to an aspect of the present invention. In contrast, conventional approaches for carrying out computations involving field elements of oddcharacteristic finite fields merely place binary data representing a single coefficient of an oddcharacteristic finite field into a single hardware register. In addition, the processing unit 105 is also configured to execute at least one operation on the contents of the abovenoted register 107 such that the plural groups of data bits are processed hi parallel. For example, one or more operations can include a shift operation, an addition operation, a binary subtraction operation, a logical AND operation, and a NOT operation (logical negation) to name a few. In this regard, the processing unit 105 can be viewed as means for executing at least one operation on the binary data such that the plural groups of data bits are processed in parallel. Thus, by storing binary data representing multiple coefficients of a field element of GF^ in a single hardware register and by processing the plural groups of data bits in parallel, the speed of computations according to the present invention can be greatly increased compared to conventional methods for computations involving field elements of oddcharacteristic finite fields. For example, if all k coefficients of a field element of GFCp") are represented in a single hardware register, such as register 107 shown in FIG. 1, the speed of processing the binary data representing the field element can be increased by a factor of k for addition and k2 for multiplication over conventional methods. Multiple coefficients of a field element of GF(p*) can be stored in a single hardware register using two exemplary approaches according to the present invention. These approaches are referred to herein as the singleguardbit representation and the multipleguardbit representation, respectively, each of which has different advantages as will be described below. In describing each of these representations, it is assumed that the hardware architecture is capable of performing basic arithmetic and logical operations on wbit words, e.g., the hardware registers can be wbit registers for some w > k(m+ 1) where binary data representing an entire field element is to be stored in a single register. In conventional terms, this means that the hardware architecture can perform arithmetic and logical operations on binary encoded integers in the range (0 .. 2W1). In principle, larger values of w are preferable because more information can thereby be processed per operation. Bit positions are numbered from right to left wherein the least significant bit is indexed by "0", the next bit by "1", the next bit by "2", and so on, up to most significant bit (the word size), which is indexed by "w1". Examples of the singleguardbit representation are shown hi FIGS. 2A and 2B for 32bit hardware registers. FIG. 2A is a schematic illustration of a hardware register 200 with a data storage scheme for storing binary data representing a field element a,{=(a.9£ are stored in bit positions zero and one (from the right). Another group of data bits representing the coefficient a1i, ... , a^, a^ ) of GF(75). In the example of FIG. 2B, five groups of bit positions 211r (unshaded bit positions) are allocated to store binary data representing the field coefficients a4fi, ..., au, cc^. In this example, p=7=2ml. Therefore, m=3, and three bits (not including guard bits) are allocated to store the binary data representing each coefficient ciy. Binary data representing coefficient oc^ are stored in bit positions zero, one and two (from the right). Binary data representing coefficient au i are stored in bit positions four, five and six, and so on. In the example of FIG. 2B for GF(75), the ground field is GF(7), and the following mapping between integer values of each coefficient and corresponding binary data is applicable (the quantities hi parentheses are the binary data): 0~(0, 0, 0); 1~(0, 0, 1); 2~(0, 1, 0); 3(0 ,1, 1); 4'(1, 0, 0); 5~(1, 0, 1); 6~(1, 1, 0); and T(l, 1, 1) where 7 also corresponds to 0 (because 7 mod 7=0). Thus, the present invention provides a dual representation wherein two different numbers in the field GF(p) (7 and 0 in this example, where p=7) represent a same value (zero). In addition, in the example of FIG. 2B, five bit positions 213r are allocated to store guard bits (lightly shaded regions), which are initially assigned binary values of 0. In addition, bit positions three, seven, eight, eleven, etc. are allocated for guard bits. Also, in the Example of FIG. 2B, the twelve most significant bit positions 215 in the register 210 are unused (darkly shaded regions). An example of the multipleguardbit representation is shown in FIG. 2C. FIG. 2C is a schematic illustration of a hardware register 220 with a data storage scheme for storing a field element (^=(0^, ... , aM, a0ii) of GF(38). In the example of FIG. 2C, eight groups of bit positions 221r (unshaded bit positions) are allocated to store binary data representing the field coefficients cc^, ... , ctu, o^, and adjacent groups of bit positions 221r are separate by a group of two guard bit positions 213r (lightly shaded bit positions). In this example, p=3=2ml. Therefore, m=2, and two bits (not including guard bits) are allocated to store the binary data representing each coefficient ctj.j. Binary data representing coefficient a0ii are stored in bit positions zero and one (from the right). Binary data representing coefficient au are stored in bit positions four and five and six, and so on. Eight groups of bit positions 223r are allocated to store two guard bits each (lightly shaded regions), which are initially assigned binary values of 0. In the example of FIG. 2C, bit positions two, three, six, seven, eight, ten, eleven, etc. are allocated for guard bits. There are no unused bit positions in this example. It is typically desirable to store binary data representing an entire field element of GF(p*) in a single hardware register 107. However, in cases where a field element is sufficiently large such that its binary representation exceeds the storage capacity of a single register, it is desirable to store binary data representing at least a portion of the field element in the register 107. The arithmetic and logical operations noted above can be carried out by coordinating the operations in multiple registers that together store binary data representing a single field element of GF(p*). For example, if two registers are used to store binary data representing a single field element of GFOp*), a right shift by m bits over all the binary data can be carried out by coordinating the two registers such that the least significant bit in left hand register is shifted to the mostsignificantbit side of the righthand register. (The terminology "righthand" and "lefthand" are used merely to distinguish the registers in the sense that a leftmostbit position hi a register corresponds to the mo.stsignificantbit position. The terminology is not intended to suggest that one register is necessarily physically positioned to the left of another register). It should be noted, however, that where two registers are used to store binary data representing a field element, if unused bit spaces are present in the mostsignificantbit positions of the righthand register, a rightshift operation must be implemented to skip over the unused bit spaces. According to another exemplary aspect of the present invention, the system 100 illustrated in FIG. 1 can be configured to execute the steps shown hi the flow diagram illustrated hi FIG. 3. FIG. 3 illustrates an approach 300 comprising a plurality of steps that can be executed by the processing unit 105 shown in FIG. 1. As shown at step 301 shown in FIG. 3, the processing unit 105 stores first binary data representing a first field element of GF(pk) in a first register (e.g., register 109), p being an odd prime number, wherein the first binary data comprises k groups of first data bits, and wherein each group of first data bits corresponds to an associated one of the k coefficients of the first field element. Similarly, as shown at step 303, the processing unit 105 stores second binary data representing a second field element of GF^*) in a second register (e.g., register 111), wherein the second binary data comprises k groups of second data bits, and wherein each group of second data bits corresponds to an associated one of the k coefficients of the second field element. Further, as shown at step 305 the processing unit 105 then generates third binary data by executing at least one operation on contents of the first register and contents of the second register such that the k groups of first data bits are processed in parallel and such that the k groups of second data bits are processed in parallel. For example, the operation or operations referred to in step 305 can include an addition operation, a subtraction operation, a shift operation, a logical AND operation, and a NOT operation just to name a few. Combinations of such operations may be carried out, for example, to generate third binary data that represents a third field element equal to the sum of the first and second field elements or a third field element equal to the product of the first and second field elements as will be described in detail below. The k groups of first data bits can be structured in the first register 109 such that at least one first guard bit is positioned adjacent to the most significant bit of each group of first data bits, each group of first data bits being separated from an adjacent group of first data bits by a corresponding at least one first guard bit. The k groups of second data bits can be structured in the second register 111 such that at least one second guard bit is positioned adjacent to the most significant bit of each group of second data bits, each group of second data bits being separated from an adjacent group of second data bits by a corresponding at least one second guard bit. In addition, the third binary data can comprise k groups of third data bits stored and structured in a third register (e.g., register 113)' such that at least one third guard bit is positioned adjacent to the most significant bit of each group of third data bits, each group of third data bits being separated from an adjacent group of third data bits by a corresponding at least one third guard bit. In this regard, the third field element comprises k third coefficients in accordance with the polynomialbasis representation, and each group of third data bits represents an associated one of the k third coefficients. (In the discussion above, "first", "second" and "third" are used as labels.) The processing unit 105 and a first register (e.g., register 109) can be viewed as means for storing first binary data representing a first field element of GF(p*). The processing unit 105 and a second register (e.g., register 111) can be view as means for storing second binary data representing a second field element of GFfc"). The processing unit 105 and a third register (e.g., register 113) can be viewed as means for storing third binary data representing a third field element of GF^*). The processing unit 105 can be viewed as means for executing at least one operation on the first binary data and the second binary data such that the k groups of first data bits are processed in parallel and such that the k groups of second data bits are processed in parallel. At step 307, it is determined whether or not more data should be processed. If more data should be processed, the flow men proceeds back to step 301. If the additional processing involves processing binary data that have already been stored in a manner consistent with steps 301 and/or 303 as a result of another calculation, steps 301 and/or 303 can be skipped as appropriate. If it is determined at step 307 not to process more data, the algorithm ends. Exemplary approaches for executing step 305 shown in FIG. 3 will now be described. Step 305 can be implemented, for example, using an algorithm GFjp_k_ADD or an algorithm GFjp_k_MUL, which will be described below. GFjp_k_ADD and GF_p_k_MUL were referred to above hi the discussion of the algorithms SUM(a, p), PRODUCT(a, p), and REDUCE(5, f). As will be described below, certain aspects of algorithms for both GF_p_k_ADD and GF_p_k_MUL depend upon the functional form of the characteristic value p and upon whether the singleguardbit representation or the multipleguardbit representation is used. In particular, certain aspects of these algorithms depend on whether p is written as p=2ml, p=2m+l or p=2m±dfor some integer m and some small integer d. The integer d is to chosen such that d 1. In general, for p = 2m±d,it is desirable to choose d odd and as close to 1 as possible. Given a value of p, a good (m, d)pair can be found by trying all m = 1, 2, ..., (21og2(p)), and for each such m, selecting d to satisfy p = 2m±d, uitil a small d is found. Addition Using SingleGuardBit Representation, p=2*l A form of GF_p_k_ADD for the singleguardbit representation where p=2ml will now be described, and it will be shown how one full addition of two field elements in GF(p") (i.e., k additions pertaining to the k coefficients of each field element), including the associated modular reduction, can be performed with a small, fixed number of operations (and without modular reductions which require long divisions) on a hardware architecture having at least w=k(m+l) bit word size. For example, for a 32bit architecture, full additions in GF(310) can be performed using only five instructions. In the singleguardbit representation, first binary data representing a first field element ai=(ak.u, ..., aliis a0>i) of OFfe*) is stored in a first single hardware register (e.g., register 107 shown in FIG. 1) by storing binary data representing cc0ji in bit positions 0 through m1, binary data representing au in bit positions m+1 through 2m, etc., such that a group of data bits representing one field coefficient is separated by one bit position from an adjacent group of data bits representing another field coefficient. Second binary data representing a second field element Pj is stored similarly in a second single hardware register (e.g., register 109). Bit positions v(m+l)l where v=l, 2, ..., k are allocated to separate the binary data representing the coefficients ccoi, >) 619 and an output register 621 for holding a result "c". Right shift gates are known to those of ordinary skill in the art, and such gates shift the values therein to the right by a selected number of bits and enter a corresponding number of zeros into the most significant bit positions. The clock/logic unit 605 can also have an output terminal (not shown) for providing a signal to be input to another hardware apparatus to initiate computations in another hardware apparatus when computations in the apparatus 600 are complete. For example, another hardware apparatus can be another apparatus 600 or a multiplier apparatus 1200 such as illustrated hi FIG. 12 to be described later. The operation of the apparatus 600 illustrated in FIG. 6 will now be described. First binary data representing a first field element and second binary data representing a second field element of GF(pk) are input on lines labeled a and b to the first register 601 and the second register 603, respectively. It is assumed that the first and second binary data are already configured with zeros at guardbit positions (e.g., by a processor that is not shown). Binary data representing the quantity m is also provided to the rightshift gate (») 619. Mask register 613 receives a first predetermined binary quantity Ml (a mask quantity) from a processor (not shown), where Ml is a quantity with values as described previously. Alternatively, mask register 613 can also comprise a circuit that generates the quantity Ml upon input, of binary data representing the quantity m. Making such a circuit is within the purview of one of ordinary skill in the art. Computation is initiated by a start signal on the input line labeled s. The first and second binary data, the binary data representing the quantity m, and the start signal can be provided from a processor (not shown) or from another hardware apparatus (not shown), such as a multiplier apparatus as illustrated in FIG. 12 to be described later, via a conventional routing circuit, for example. When the values of the first binary data and second binary data in the registers 601 and 603 are stable, a signal si locks those values into the registers 601 and 603, respectively. The adder 607 then adds the values provided at its two inputs from register 601 and 603. When the output of the adder 607 is stable, the output from adder 607 is locked into register 609 by a signal on the line labeled s2. The tune required for a given value to become stable in a given register can be conventionally determined by one of ordinary skill in the art in view of the circuitry design, and a locking signal (e.g., on line si or line s2) can be timed to occur after this time. At this point, the register 609 holds binary data representing corresponding to the quantity a+b shown hi step 401 of FIG. 4. The binary data hi register 609 are then directed from register 609 to the AND gate 611. The AND gate 611 performs a logical AND between the binary data from register 609 and the mask quantity Ml from mask register 613. The result of this logical AND operation is equivalent to the quantity cl illustrated at step 403 of FIG. 4. The output from the first AND gate 611 is then directed back to the input of the first register 601, and another signal on the line labeled si then locks the corresponding values into the first register 601 at the appropriate time. In this regard, it will be understood that a signal on the line si can be tuned appropriately such that it is unnecessary to provide a multiplexer or switch at the point labeled 623 to route data output from register 609. Of course, the apparatus 609 could be provided with a multiplexer or switch at the point 623 for routing data if desired. While the operations described in the immediately preceding paragraph are being carried out, the following operations are more or less simultaneously carried out. Output from the register 609 is directed to the second AND gate 617, and the first predetermined binary quantity Ml is directed to a logical NOT gate 615. The output from the logical NOT gate 615 is also directed to an input of the second AND gate 617. The data at these the inputs of the second AND gate 617 are then combined via a logical AND operation and are directed to a rightshift gate 619. The rightshift gate 619 executes a rightshift by m bits on the data input from the second AND gate 617 according to the input on the line labeled m. The output of the rightshift gate 619 is then directed to the input of the second register 603. The result of this group of operations, which is input to the second register 603, corresponds to the quantity c2 referred to in step 405 of FIG. 4. When the values of the binary data now stored in the first and second registers 601 and 603 are stable, the signal si locks these values into the first and second registers 601 and 603. At this point, the adder 607 adds the binary data from the first and second registers 601 and 603 and directs the output to output register 609. The binary data now stored in register 609 is then directed to the output register 621, and a signal on line s3 locks the binary data into the register 621 at the appropriate time. This binary data corresponds to third binary data denoted as c at step 407 of FIG. 4. Those of ordinary skill in the art will appreciate that many variations of the apparatus 600 are possible according to the present invention. For example, each internal wbit register 601, 603, 609, 613, and 621 can be replaced with multiple parallel (i.e., coordinated) registers, at least one of which holds binary data representing at least two coefficients of a field element. Further, the first AND gate 611, the adder 607, the second AND gate 617, the NOT gate 615, and the rightshift gate 619 shown in FIG. 6 are accordingly replaced with multiple parallel (i.e., coordinated) copies of each. In the apparatus 600 as described with reference to FIG. 6, first and second binary data are input to first and second registers 601 and 603, respectively, with zeros already configured at appropriate guardbit positions. The first and second binary data may be provided in this configuration by a processor (not shown), for example, that inserts zeros at guardbit positions as appropriate. Thus, the processor (not shown) and the first register 601 can be viewed as means for storing first binary data, and the processor (not shown) and the second register 603 can be viewed as means for storing second binary data. Further, the register 621 and/or the register 609 can be viewed as means for storing third binary data. Moreover, the clock/logic device 605 and any or all of the remaining devices illustrated in FIG. 6 can be viewed as means for executing at least one operation on the first binary data and the second binary data. By utilizing the apparatus 600 along with a processor (not shown), the apparatus 600 has flexibility to be used with field elements for various choices of p and k for the finite field GF(pk), where p is of form p=2ml. In particular, the quantity m is a variable, and the rightshift gate 619 responds accordingly to the input value of m. In addition, the mask register 613 holds an appropriate form of the first predetermined binary quantity Ml that depends upon the quantity m. The quantity Ml is "predetermined" in the sense that once the quantity m is chosen (which determines the quantity p), the form of the quantity Ml directly follows as described above. In another exemplary aspect of the invention, the apparatus 600 can be modified, such as shown by hardware apparatus 700 illustrated in the block diagram of FIG. 7, for a situation hi which a dedicated choice of the finite field GF^*) is made and remains unchanged. That is, the quantities m, p, and k, as well as the choice of whether the representation is a singleguardbit representation or a multipleguardbit representation, are fixed, and the hardware apparatus 700 is dedicated to those choices. In this situation, the hardware apparatus 700 can receive initial binary data representing field elements wherein the initial binary data are not configured with zeros in guardbit positions. Rather, the hardware apparatus 700 itself configures the initial binary data with zeros hi appropriate guardbit positions to generate first and second binary data without the need for a processor to configure the first and second binary data with zeros in guardbit positions. The hardware apparatus 700 illustrated in FIG. 7 will now be described. The hardware apparatus 700 illustrated in the functional block diagram of FIG. 7 shares various common features and operational aspects with the apparatus 600 illustrated hi FIG. 6, and like features are given like reference numerals in FIGS. 6 and 7. Discussion of aspects of the apparatus 700 that are common to the apparatus 600 will not be duplicated here. Rather, aspects in which the apparatus 700 differs from the apparatus 600 will be.discussed. The apparatus 700 possesses several features not found in the apparatus 600. In particular, the apparatus 700 possesses guardbitinsertion circuits 701' and 703' (GB insertion) and a guardbitremoval circuit 709' (GB removal). Exemplary implementations of these circuits will be described in FIGS. 8A and 8B. As shown in FIG. 7, the guardbitinsertion circuits 701' and 703' are functionally arranged at the .input to the hardware apparatus 700, and the guardbitremoval circuit 709' is functionally arranged between the register 709 and the output register 721. The guardbitinsertion circuits 701' and 703' operate to receive initial binary data a' and b' (without guard bits) corresponding to first and second field elements of GF(p") and to insert appropriate guard bits into that data. In other words, the guardbitinsertion circuits 701' and 703' transform the initial binary data a' and b' into first binary data and second binary data having guard bits, in particular, with zeros at guardbit positions. The guardbitremoval circuit 709' has the opposite function  namely, to receive third binary data c representing a computational result and having guard bits and to remove those guard bits, thereby forming final binary data c' representing the computational result, but without guard bits. The apparatus 700 also lacks certain features present in the apparatus 600 because they are not needed hi the apparatus 700. In particular, the apparatus 700 lacks an input line for the quantity m into the rightshift gate 719 and into the mask register 713. Such an input line is not necessary given that m is fixed. Rather, the rightshift gate 719 is initialized once with the value of m to execute the appropriate right shift. Similarly, the mask register 713 is initialized once with the appropriate form of Ml. Conventional electrical connections can be used for carrying out these initializations and are not shown in FIG. 7. The operation of the apparatus 700 illustrated in FIG. 7 is substantially similar to that described for the apparatus 600 illustrated in FIG. 6 except for the operational distinctions noted above. In the apparatus 700 as described above, the first register 701 and the guardbit insertion circuit 701' can be viewed as means for storing first binary data. The second register 703 and the guard bit insertion circuit 703' can be viewed as means for storing second binary data. Further, the register 709 can be viewed as means for storing third binary data. Moreover, the clock/logic device 705 and any or all of the remaining devices illustrated in FIG. 7 can be viewed as means for executing at least one operation on the first binary data and the second binary data. The guardbitinsertion circuits 701' and 703' and the guardbitremoval circuit 709' referred to in FIG. 7 will now be described in greater detail with reference to FIGS. 8A and 8B. The exemplary circuits illustrated in FIGS. 8A and 8B reflect a 32bit register arrangement configured for the field GF(78); however, the concepts reflected in FIGS. 8A and SB are generally applicable to registers of others sizes and to other finite fields GFCp*). FIG. 8A illustrates an exemplary guardbitinsertion circuit 800 that can be used for guardbitinsertion circuits (GB insertion) referred to by reference numerals 701' and 703', respectively, in FIG. 7. As shown in FIG. 8A, the circuit 800 comprises a first register 801 with a plurality of bit positions 803 (e.g., 32 bits). The circuit 800 also comprises a register 805 having plural groups 807 of bit positions intended to store binary data representing field coefficients of a field element of GFCp*) and a plurality of guardbit positions 809 (lightly shaded regions). The circuit 800 also comprises a plurality of electrical connections 811 configured to route data from register 801 to register 805 in a manner that provides a guardbit position 809 adjacent to the most significant bit position of the preceding group of 3bit positions 807. The guardbit positions 809 are electrically grounded to provide zeros for these bit values, but these electrical connections are not shown in the FIG. 8A. Such a circuit can be formed, for example, using conventional lithographic techniques. In this manner, each 3bit group 807 of bit positions in register 805 can store binary data representing a coefficient of a field element of GF(78), and each group 807 of bit positions in register 805 is separated from an adjacent group 807 of bit positions by a single guard bit 809. Accordingly, the guardbitinsertion circuit 800 allows initial binary data representing coefficients of a field element to be transferred in parallel from register 801 to register 805 in a manner that inserts guard bits between groups of data bits representing coefficients of the field element. Similarly, an exemplary guardbitremoval circuit 820 is illustrated in FIG. 8B for a 32bit GF(78) configuration. As illustrated in FIG. 8B the guardbitremoval circuit 820 is the mirror image of the guardbitinsertion circuit 800 shown in FIG. 8A. The guardbitremoval circuit 820 comprises a register 825, a register 821 and a plurality of electrical connections 831. The register 825 comprises plural groups 827 of bit positions and a plurality of guardbit positions 829, each guardbit position being located adjacent to the most significant bit of a given group 827 of bit positions. As illustrated in FIG. SB, the electrical connections 831 are configured such that binary data representing field coefficients of a field element stored in register 825 are transferred to register 821 in a manner that eliminates guard bits between adjacent groups of data bits representing field coefficients. That concludes the discussion of FIGS. 8A and 8B. .Multiplication Using SingleGuardBit Representation According to another aspect of the invention, an exemplary form of GFjp_k_MUL for the singleguardbit representation will now be described for computing the product of two (nonzero) field elements otj and fy in GF^1). The case where one field element is zero is trivial and does not need to be described. This discussion is applicable to p written in the functional forms p=2ml, p=2m+l, p=2md and p=2m+d. As noted previously in the discussion pertaining to Equations 912, a multiplicative group is cyclic, and a field element g, therefore, can be found such that any other nonzero field element can be written as g* for some integer x 1 and d odd), each coefficient of a field element is represented using m+2, m+1 and m+2 bits of binary data (not including guard bits), respectively, instead of m bits as for p=2IDl. Directly addressed DLOG tables for p of forms other than p=2ml, therefore, are correspondingly larger than directly addressed DLOG tables for p of the form p=2™l. An exemplary DLOG table 1000 illustrating concepts described above for the singleguardbit representation is shown in FIG. 10A for the simple case of GF(32) where p=2ml for m=2. The example in FIG. 10A was constructed for GF(32) using the generator g(t)=t and the irreducible polynomial p(t)=t2+t+2. Such a DLOG table can be implemented, for example, using an 8bit, 16bit, 32bit, etc., architecture. As noted previously, choosing an appropriate generator and irreducible polynomial for a given finite field GF(pk) is within the purview of one of ordinary skill in the art. The exemplary DLOG table J.000 illustrated in FIG. 10A comprises memory addresses 1001 corresponding to the field elements a(t) in binary form and stored values 1003 corresponding to the associated integers x in binary form. In addition, the exemplary DLOG table 1000 comprises 2k(m+1)=2*=64 rows (entries) 1005. In the example of FIG. 10A, each memory address comprises a k(m+l)=2(2+l)=6bit string, and the leftmost bit of each memory address 1001 corresponds to the most significant guard bit of a corresponding field element. This most significant guard bit can be eliminated from the memory addresses 1001, if desired, allowing the DLOG table 1000 to be indexed by binary strings k(nHl)l bits in length. The memory addresses 1001 comprise groups of data bits corresponding to coefficients of field elements in the manner previously described. Each memory address 1001 further comprises a plurality of guard bits 1005 The stored values 1003 of the DLOG table 1000 are illustrated as being functionally adjacent to the memory addresses 1001 for purposes of illustration. Each stored value 1003 comprises binary data representing an integer x as defined above. Reference infonnation 1050 is presented in FIG. 10B in a manner that is aligned via rows with the information in the DLOG table 1000 shown in FIG. 10A. The reference information 1050 in FIG. 10B is not part of the DLOG table 1000 and is merely provided for convenience to reflect the association between the binary information shown in the DLOG table 1000 and the field elements a(t) in polynomial form and the actual integer values x. Various blank entries denoted by "" are present in the "x" and "a(t)" columns of both FIG. 10B and FIG. 10A. These blank entries stem from two considerations. First, some blank entries reflect the fact that there is no integer x that satisfies gx=0 for the field element "0" (a(t)=0), as is known to those of ordinary skill in the art. Other blank entries correspond to memory addresses 1001 having a "one" in any corresponding guardbit position. As noted above, these entries are not used in the exemplary DLOG table 1000. hi the abovedescribed directaddressing example, the DLOG table 1000 has reserved memory locations that are not used for lookup operations corresponding to the two types of blank entries described above. The majority of these blank entries are associated with memory addresses having a "one" in any guardbit position. However, compact DLOG tables can be implemented without such blank entries. For example, instead of associating field elements with consecutive memory addresses, binary data representing field elements a(t) with only zeros at guardbit positions can be stored hi a DLOG table. Corresponding values for x=DLOG(a(t)) can also be stored in the DLOG table. The stored a(t) entries and x entries can be associated with each other such that looking up a given a(t) entry returns the corresponding x entry. This approach does not have the simplicity of using consecutive binary data corresponding to a(t) entries as addresses, but it does have the advantage of requiring less memory space. In one aspect of the present invention, a multipleguardbit representation can be used to obtain compact tables without significantly complicating the lookups, as will be described later. In general, such a compact DLOG table can be configured with 2km+l reserved memory locations (e.g., viewed as 2km rows with 2 entries per row), all of which can be used for lookup operations. Alternatively, such a compact DLOG table can be implemented using 2km reserved memory locations if the most significant guard bit is eliminated. In comparison, a directly addressed DLOG table comprises 2k&n+1) reserved memory locations (or 2k(m~HH reserved memory locations if the most significant guard bit is eliminated). Thus, utilizing a compact DLOG table can be useful for computations involving relatively larger field elements (e.g., field elements represented by binary data of greater than 25 bits including guard bits). Exemplary aspects of ANTILOG tables according to the present invention will now be described. ANTILOG tables according to the present invention are similar to DLOG tables described above. In particular, ANTILOG tables also contain binary information representing the quantities x and a(t). However, ANTILOG tables are indexed (addressed) by binary data representing the quantity x=DLOG(a(t)). Thus, for a memory address corresponding to a given value of x, the lookedup quantity is a(t)=ANTILOG(x). Given that ANTILOG tables are indexed by x instead of a(t) (as for DLOG tables), ANTILOG tables are considerably smaller than corresponding DLOG tables. In particular, ANTILOG tables have pkl reserved memory locations regardless of the functional form of p. The fact that there are pkl reserved memory locations instead of pv reserved memory locations stems from the fact that there is no integer x corresponding to the field element a(t)=gx=0. An exemplary ANTILOG table 1100 is shown in FIG. 11A for the simple case of GF(32) for the singleguardbit representation where p=2ml and m=2. The example hi FIG. 11A was constructed for GF(32) using the generator g(t)=t and the irreducible polynomial p(t)=tz+t+2. Such an ANTILOG table can be implemented, for example, using an 8bit, 16bit, 32bit, etc., architecture. The exemplary ANTILOG table 1100 illustrated in FIG. 11A comprises memory addresses 1101 corresponding to integers x in binary form and stored values 1103 corresponding to the associated field elements a(t) in binary form. The memory addresses 1101 of the exemplary ANTILOG table 1100 are illustrated hi FIG. 11A as being functionally adjacent to the stored values 1103 for purposes of illustration. Each stored value 1103 comprises groups of data bits representing coefficients of field elements La the manner previously described. Each stored value 1103 further comprises a plurality of guard bits 1105 whose entries are zeros. In a manner similar to that shown in FIG. 10B, reference information 1150 is presented in FIG. 1 IB in a manner that is aligned via rows with the information in the ANTELOG table 1100 shown in FIG. 11 A. The reference information 1150 in FIG. 11B is not part of the ANTELOG table 1100 and is merely provided for convenience to reflect the association between the binary information shown in the ANTELOG table 1100 and the field elements a(t) in polynomial form and the actual integer values x. As noted above, DLOG tables and ANTELOG tables according to the present invention can be stored using any suitable hardware architecture (e.g., 8bit, 16bit, 32bit, etc.). In addition, as noted above, directly addressed DLOG tables can be implemented with consecutive binary data representing field elements used as memory addresses. Alternatively, compact DLOG tables can be implemented that do not use direct addressing as described above. Such compact DLOG tables use less memory space but do not allow indexing directly by binary data representing field elements, and a more timeconsuming table lookup is needed for compact DLOG tables. However, in the multipleguardbit representation described below, a considerably more compact DLOG table can be provided (approximately a factor 2k smaller) that still allows direct addressing and in which only a very small decrease in efficiency is encountered with regard to table lookups. Memory requirements for directly addressed lookup tables for the singleguardbit representation for p=2ml are as follows. For a directly addressed DLOG table, each row contains the binary form of an integer x of size k*loga(p) « km bits, and (not including the most significant guard bit) the table is indexed by (kl)(m+l)+m=k(m+l)l bit binary strings corresponding to the field elements. .Thus, the size of the DLOG table is roughly km2k(m+1)1 bits. For the ANTELOG table, each entry contains at most a k(m+l)bit string, and there are pkl entries. Thus, the size is k(m+l)( pkl) bits, which is roughly equal to k(m+l)2Ian bits. Accordingly, the DLOG table is roughly a factor 2k' larger than the ANTELOG table. It is possible to reduce table sizes even further (for both the singleguardbit representation and the multipleguardbit representation) at the cost of carrying out a larger number of multiplications. For example, the aforementioned Karatsuba's method for multiplying polynomials of degree k works by replacing a single multiplication of two degreek polynomials with three multiplications, each involving polynomials of degree k/2. Those of ordinary skill in the art will recognize that abovedescribed exemplary multiplication according to the present invention can be similarly modified to use tables of smaller size in conjunction with more table lookups. For instance, if S is a table size for carrying exemplary multiplication according to the present invention as described above, a modification can be made wherein tables of size S1/2 are used in conjunction with three times as many table lookups. Notwithstanding the increased cost in table lookups, this approach can be desirable for memoryconstrained environments. In view of the discussion above with regard to GF_p_k_MUL and the corresponding DLOG and ANTILOG tables, it can be seen that the abovedescribed exemplary approach for carrying out multiplication of field elements of GF(pk) according to the present invention differs significantly from conventional approaches. First, in comparison to approaches for binary finite fields with characteristic p=2, the present approach stores binary data representing field elements differently by utilizing guard bits. Accordingly, the DLOG and ANTILOG tables according to the present invention also possess guard bits, such as illustrated in FIGS. 10A and 11 A, whereas the lookup tables for conventional approaches involving binary finite fields do not possess (or require) guard bits. In addition, in comparison to conventional approaches for multiplication of field elements of an oddcharacteristic finite field, the present method accomplishes the multiplication task with significantly fewer operations. In particular, with regard to the extension field GFCp*) referred to above in the discussion regarding SUM(a, P) and PRODUCT(cc, P), each element of the extension field is represented as a vector (polynomial) of length /, where each component (coefficient) is stored according to the singleguardbit representation. Multiplying two elements in the extension field requires approximately 3/2 operations rather than (flc)2 operations as would be required using conventional approaches. Thus, even for relatively small values of k, a significant increase in computational speed is achieved. In another aspect of the invention relating to multiplications of field elements of an oddcharacteristic finite field, a dedicated hardware apparatus can be provided for carrying out operations of GFj?_k_MUL illustrated in FIG. 9. FIG. 12 is a functional block diagram illustrating such an exemplary hardware apparatus. In particular, the exemplary apparatus 1200 illustrated in FIG. 12 provides another approach for generating third binary data, denoted as c in FIG. 4, that can represent the product of a first field element and a second field element of GFCp11). In FIG. 12, solid lines represent electrical connections for the flow of data, and dotted lines represent electrical connections for the flow of control signals. The apparatus 1200 is described here in the discussion pertaining to the singleguardbit representation, but the apparatus 1200 is equally applicable to a multipleguardbit representation, which is described later. Moreover, the apparatus 1200 is independent of the form of the characteristic value p (i.e., p=2m±l oro=2m±d). The apparatus 1200 comprises a first register 1201 and a second register 1203 for holding first binary data (register contents "a") and second binary data (register contents "b"), respectively. The first binary data and the second binary data represent field elements of the finite field GF(pk). Here, it is assumed that the first and second binary data in the first and second registers 1201 and 1203 are already configured with zeros at appropriate guardbit locations. However, guardbit insertion and removal circuits, such as described with regard to FIGS. 7 and 8 could also be included if desired such that initial binary data without guard bits could be input to the apparatus 1200. The apparatus 1200 also comprises a combinatorial logic and clock device (clock/logic) 1205, a first multiplexer 1207 (MUX1), a DLOG lookup memory 1209, and an ANTILOG lookup memory 1211. The DLOG and ANTCLOG lookup memories can be implemented, for example, using a random access memory (RAM) or a flash memory. The apparatus 1200 also comprises a register 1213 for holding the binary quantity DLOG(a), a register 1215 for holding the binary quantity DLOG(b), an addition gate (+) 1217 (also referred to as an adder), and a register 1219 for holding the integer value pkl in binary form, which can be received, for example, from a processor. Alternatively, a specialized circuit can be provided along with the register 1219 to generate the value pkl upon input of values for p and k. Configuring such a specialized circuit is within the purview of one of ordinary skill in the art. The apparatus 1200 also comprises a modulo arithmetic circuit 1221 (MOD) for computing the remainder of an input quantity divided by pkl, which is supplied by register 1219. The circuit 1221 can be conventional modular arithmetic hardware known to those of ordinary skill in the art and does not need to be described further. The apparatus 1200 further comprises a second multiplexer 1223 (MUX2) and an output register 1225 for holding third binary data "c" resulting from computations within the apparatus. The clock/logic unit 1205 can also have an output terminal (not shown) for providing a signal to be input to another hardware apparatus to initiate computations in another hardware apparatus when computations in the apparatus 1200 are complete. For example, another hardware apparatus can be another apparatus 1200 or an addition apparatus 600 such as illustrated in FIG. 6. The operation of the exemplary apparatus 1200 illustrated in FIG. 12 will now be described. First, the DLOG lookup memory 1209 and the ANTILOG lookup memory 1211 are initialized once with appropriate discrete logarithm and antilogarithm data. This can be accomplished by providing an initial programming signal to the clock/logic unit 1205 via the line labeled s, and by simultaneously supplying discrete logarithm and antilogarithm data to the DLOG lookup memory 1209 and the ANTILOG lookup memory 1211, respectively, via external data buses labeled eDl and eD2. At the same time, address data is supplied to the DLOG memory 1209 and to the ANTILOG memory 1211 by external address buses eAl and eA2, respectively, via MUX1 1207 and MUX2 1223, respectively. As noted above, the lookup memories 1209 and 1211 can be implemented with RAM or flash memory, for example. Alternatively, if the apparatus 1200 is to be dedicated for particular values of p and k, the lookup memories 1209 and 1211 can be implemented using ROM, and precomputations of the discrete logarithm and antilogarithm data can be done once and loaded into the ROM at manufacture. With the lookup memories 1209 and 1211 initialized, first binary data representing a first field element and second binary data representing a second field element can be input on lines labeled a and b to the first register 1201 and the second register 1203, respectively. It is assumed that the first binary data and the second binary data are already configured with zeros at appropriate guardbit positions. Alternatively, guardbit insertion circuits can be utilized to insert appropriate guard bits before loading the first binary data and second binary data into the first and second registers 1201 and 1203, respectively, such as described with regard to FIGS. 7 and 8. Binary data representing the quantity pkl are input on the line labeled "pkl" to the register 1219. The first binary data, the second binary data, the discrete logarithm and antilogarithm data, and the binary data representing the quantities p and k can be provided, for example, from a processor (not shown) or from one or more hardware apparatuses (not shown). For example, an addition apparatus 600 as illustrated in FIGS. 6 or 7 can be used to provide at least some of this data (e.g., first binary data and second binary data) via a conventional routing circuit. Computation is initiated by a start signal on the line labeled s as shown in FIG. 12. The start signal can also be provided from a processor (not shown) or from one or more hardware apparatuses (not shown). When the values of the first binary data and second binary data in the registers 1201 and 1203 are stable, a signal si locks those values into the first and second registers 1201 and 1203, respectively. When values of the binary data representing the quantity pkl in register 1219 are stable, a signal s5 locks those values in register 1219. A signal s2 is then input to MTJX1 1207 which then passes the contents, a, of the first register 1201 to the DLOG memory 1209 to access the DLOG memory 1209. When the output values from the DLOG memory are stable, the output values are locked into register 1213 by a signal s4. Register 1213 now holds the value of DLOG(a). Another signal s2 is then input to MUX2 1223 which then passes the contents, b, of the second register 1203 to the DLOG memory 1209 to access the DLOG memory 1209. When the output values from the DLOG memory are stable, the output values are locked into register 1215 by a signal s3. Register 1213 now holds the value of DLOG(b). The adder 1217 then computes the integer sum of the contents of registers 1213 and 1215 and sends the result to the modulo arithmetic circuit 1221 (MOD) to compute the remainder of the value input thereto when divided by the quantity pkl, which is available from register 1219. The output from MUX2 is then input to the ANTILOG memory 1211 to access the ANTILOG memory 1211. When the output values from the ANTILOG memory 1211 are stable, the output values are locked into register 1225 by a signal s6. Register 1225 now holds the value ANTILOG{(DLOG(a)+DLOG(b)) mod (pkl)} in the singleguardbit representation, which is available for output as register contents, c. If desired, however, a guardbitremoval circuit, such as illustrated in FIGS. 7 and 8, could be placed functionally between the ANTILOG memory 1211 and the register 1225 to remove guard bits from the result of the computations. This completes the description of the exemplary multiplication apparatus 1200 illustrated in FIG. 12. In the apparatus 1200 as described, the first register 1201 and a processor (not shown) can be viewed as means for storing first binary data. Alternatively, the first register 1201 and a guardbit insertion circuit (not shown) can be viewed as means for storing first binary data. The second register 1203 and a processor (not shown) can be viewed as means for storing second binary data. Alternatively, the second register 1203 and a guardbit insertion circuit (not shown) can be viewed as means for storing second binary data. Further, the register 1225 can be viewed as means for storing third binary data. Moreover, the clock/logic device 1205 and any or all of the remaining devices illustrated in FIG. 12 can be viewed as means for executing at least one operation on the first binary data and the second binary data. Addition using MultipleGuardBit Representation, p=2ml Exemplary aspects of the invention pertaining to addition of field elements where p=2ml are now described for the multipleguardbit representation. Here it is assumed that invention is implemented using a hardware architecture operating on at least 2km bit quantities (i.e., registers are at least 2km bits in size). The invention according to the multipleguardbit representation may be implemented, for example, using the system 100 illustrated in FIG. 1, which has already been described. In addition, dedicated hardware apparatuses, such as illustrated in FIGS. 6, 7, 8 and 12 and which have already been described, may also be used to implement the invention according to the multipleguardbit representation. Descriptions of these apparatuses are not reproduced here. However, appropriate modifications to the apparatuses illustrated in FIGS. 6, 7, 8 and 12 for the multipleguardbit representation, where necessary, will be described below. The representation of field elements of GF(pk) in the multipleguardbit representation was described previously in the discussion pertaining to the example of FIG. 2C. As noted in that discussion, elements of a finite field are stored as binary strings, but instead of having only one guardbit position between adjacent groups of data bits representing coefficients of a field element, a plurality of guardbit positions (e.g., m guardbit positions) are provided between adjacent groups of bit positions that are allocated to store binary data representing the field coefficients of a field element. For example, as illustrated in FIG. 2C for GF(38), eight groups of bit positions 221r (unshaded bit positions) are allocated to store binary data representing field coefficients oc7>i, ..., >m) (19) where a and b represent contents of the first and second register, respectively, in which the first and second binary data are stored according to the multipleguardbit representation and where c represents the resulting contents of a third register holding third binary data also stored according to the multipleguardbit representation. The explanation of how the abovenoted operations result in correctly providing third binary data representing a third field element of GF(pk) equal to the sum of the first and second field elements is the same as described above for the single guardbit representation and is not repeated here. As noted above, hardware apparatuses illustrated in FIGS. 6, 7 and 8 can be used to implement the invention according to the multipleguardbit representation. No modifications to the apparatus 600 illustrated in FIG. 6 are necessary hi this regard. It is merely necessary to recognize that the first and second binary data are stored in the first and second registers 601 and 603 according to the multipleguardbit representation and that the first and second predetermined binary quantities Ml and M2 are configured as described above. For the multipleguardbit representation, a modification to the addition apparatus 700 illustrated in FIG. 7 is required in the sense that the guardbitinsertion circuits 701' and 703' and the guardbit removal circuit 709' must be configured to insert multiple guard bits, instead of a single guard bit, between adjacent groups of data bits representing coefficients of a field element. In this regard, the exemplary guard bitinsertion circuit 800 illustrated in FIG. 8A can be configured such that the electrical connections 811 are displaced wherein more than one guardbit position 809 without an electrical connection 811 is inserted between adjacent groups of bit positions 807 in the register 805. Similarly, the exemplary guardbitremoval circuit 820 illustrated in FIG. 8B can be configured such that the electrical connections 831 are displaced to remove more than one guardbit position between adjacent groups of bit positions 807 in the register 825. With such modifications for the multipleguardbit representation, the operation of the apparatus 700 illustrated in FIG. 7 is the same as previously described. Multiplication Using MultipleGuardBit Representation Implementations of exemplary forms of GF_p_k_MUL for the field GF(pk) will now be described for the multipleguardbit representation. This discussion is applicable to p given by the functional forms p=2m±land p=2radd. The only differences that occur for different functional forms of p relate to the number of bits used to store binary data representing a given coefficient of a field element and how many bits are allocated in ANTILOG tables for each coefficient of a field element. These differences will be discussed in greater detail below. The immediate discussion will proceed for the case where p=2ml for which m bits are used to store each coefficient of a field element, but the discussion is applicable to the other functional forms for p noted above. In a first exemplary implementation of GF_p_k_MUL for the multipleguardbit representation, a compression function isused to more efficiently utilize memory space allocated for DLOG and ANTILOG tables. This approach uses directly addressed DLOG and ANTILOG tables in a manner somewhat similar to that described above for the singleguardbit representation, but the forms of the directly addressed DLOG and ANTILOG tables are different. In particular, to save memory space allocated for the DLOG and ANTILOG tables, the DLOG and ANTILOG are configured without guard bits (making them about kmfi1011 bytes in combined size). For a directly addressed DLOG table, where binary data corresponding to field elements are used as memory addresses, eliminating guard bits from the DLOG table means that the total number of consecutive memory addresses are reduced. Thus, the number of reserved memory locations are also reduced. For the ANTILOG table, which is also directly addressed and which uses binary data representing integers x=DLOG(a(t)) as memory addresses, eliminating guard bits reduces the number of bits used to store binary data representing field elements a(t), thereby reducing memory requirements. To utilize such tables, binary data representing field elements of GF(pk) stored in the multiple guard representation are compressed before carrying out a DLOG table lookup. In addition, resulting binary data is then decompressed after carrying out an ANTILOG table look¬up. This is now described in greater detail. Here it is assumed that field elements are stored according to the multipleguardbit representation with m guard bits between adjacent groups of data bits that represent coefficients of a field element. However, the present approach is not limited to m guard bits between adjacent groups of data bits and modifications for multiple guard bits other than m guard bits between adjacent groups of data bits will be apparent from the discussion below. Let t=INT(k/2) where INT(k/2) is the integer value of k/2 rounded down to nearest integer. A compression can be executed on register contents, a, stored in the multipleguardbit representation using a compression function (COMP) given by COMP(a)={(a XOR (a » (2tl)m)) & M3} (20) where M3 is predetermined binary quantity representing the value 2kml so that COMP(a) has km bits. (The XOR can be replaced by a bitwise ORoperation in equation 20 above.) The COMP function moves groups of data bits representing field coefficients (that is, relevant, informationcarry ing data) from bitposition blocks 2jm, ..., (2j +l)ml, where j > t, to the reserved guardbitposition blocks (2(jt)+l)m, ..., (2(jt)+2)ml. This is shown, for example, in FIG. 13 which illustrates the abovenoted mapping of bit positions from a register 1301 to bit positions of a register 1302 where uncompressed data in register 1301 is compressed into register 1302. Dotted oblique lines 1303 illustrate the mapping of bitposition blocks shifted relative to their original positions. Dotted vertical lines 1304 illustrate the mapping of bit position blocks which are not shifted relative to their original positions. As illustrated in FIG. 13 for the case of GF(38) where t=4 and m=2 (because p=2ml), as an example for j=t=4, data in bit positions 16 (i.e., 2jm) and 17 (i.e., (2j + l)ml) are mapped to bit positions 2 (i.e., (2(jt)+l)m) and 3 (i.e., (2(jt)+2)m4). Other data blocks are similarly mapped. Accordingly, no groups of data bits representing coefficients of a field element are lost in the abovenoted operations. The directly addressed DLOG table is configured such that the memory addresses correspond to COMP values of associated field elements for fast lookup. The directly addressed ANTILOG table stores COMP values of binary data representing field elements. Moreover, all entries in the DLOG and ANTILOG tables will contain relevant (i.e., informationcarrying) data. Hence, there is no empty or unused space in the DLOG and ANTILOG tables. A decompression of compressed binary data can be carried out using a decompression function (DECOMP) in an analogous manner. Let M4 be a predetermined binary quantity with ones in bitpositions 2jm, 2jm+l, 2jm+2,..., (2j + l)ml, where j=0., 1, ..., k1, and zeros elsewhere. Then DECOMP(z) = {(z XOR (z « (2tl)m)) & M4) (21) where, again, the XOR can be replaced by a bitwise ORoperation and m)} mod p. (25) Because u 1 will be described below in conjunction with determining suitable representation sets Sp corresponding to allowed values of coefficients of field elements of GF^*). As will be seen, the Sp sets depend on the functional form of p and on m and d, where p=2™±d. In analogy to the above, these sets will be denoted by Sp+ for the case p=2m+l, Sp+d for p=2m+d, and Sp4 for p=2md. As noted above, the coefficients of field elements of GF(p*) themselves are elements of GF(p). It should be noted that as long as a modular reduction of a quantity c subtracts a multiple of p from c, there is mathematically no problem with allowing more general sets Sp if they are closed under addition followed by the modular reduction. Addition and Multiplication in GF(pk) where p= In the following descriptions of GFjp_k_ADD and GF_p_k_MUL for the case where p=2mfl, it is assumed that m £ 2 such that p > 5. This is because the case where p=3 is preferably addressed using the previously described approaches for addition and multiplication where p=2ml (i.e., p=22l). Let the set Sp+ be given by Sp+ = {0, 1, ..., 2p2). (Thus, for p=2m+l the present invention allows the values 0, 1, ..., p2, to have two representations, whereas in the case p=2ml, only the value 0 had more than one representation.) Each coefficient of a field element of GF^11) is then an element of Sp+. Note that 2p2=2m+1, so that m+2 bits (not including guard bits) are used to represent a coefficient of a field element of GF^"), which is one more bit than was needed to represent coefficients in the set Sp" ={0 , ..., p} utilized in the approaches forp=2ml. For the case p=2m+l, binary data representing field elements of GF(pk) can be stored in hardware registers according to either the singleguardbit representation or the muitipleguardbit representation, such as described previously, except that for p=2m+l, m+2 bits (not including guard bits) are allocated for each group of data bits representing a coefficient of a field element. For example, in the singleguardbit representation, first binary data representing a first field element cc; of GFfe*), wherein the first binary data comprises k groups of first data bits, can be stored as follows. Here it is assumed that (m+3)k is at most the hardware word size (i.e., register size). Let cij be a first field element of GF^*) where oci=(ak.1 b ..., o^fi) and where each o^ belongs to the set Sp+. A group of first data bits representing a0>i is stored in a first register in bit positions 0, 1, ,.., m+1. A first guard bit having a value of zero is stored in the first register in bit position m+2 (a guardbit position). Another group of first data bits representing aM is stored hi the first register in bit positions mf 3, ..., 2m+4, and so on. Accordingly, there is one first guard bit in every bit position v(m+3)l where v=l, 2, ...  that is, every successive (m+3)rd bit position. In other words, there is one first guard bit positioned adjacent to the most significant bit of each group of first data bits. Second binary data comprising k groups of second data bits representing a second field element of GF(p^) can similarly be stored in a second register with one second guard bit adjacent to the most significant bit of each group of second data bits. (Here, the use of "first" and "second" merely distinguish between attributes corresponding to the first field, element and the second field element, respectively.) By storing binary data representing first and second field elements of GF(pk) in first and second hardware registers. in this manner, no carry bit will propagate from one group of data bits representing a field coefficient into an adjacent group of data bits representing another field coefficient. The approach for storing binary data representing field elements according to the multipleguardbit representation is completely analogous, the only difference being that more than one guardbit position is provided between adjacent groups of data bits representing field coefficients. An exemplary form of GF_jp_k_ADD where p=2mfl will now be described with reference to the flow diagram of FIG. 14. The operations shown in FIG. 14 can be executed by a system such as system 100 shown in FIG. 1. Further, it is assumed that steps 301 and 303 shown in FIG. 3 have already been executed by the processor 105 such that first binary data representing a first field element of GF(p*) are stored in a first register (e.g., register 107 shown in FIG. 1) and such that second binary data representing a second field element are stored in a second register (e.g., register 109) in a manner such as described directly above. The first and second binary data can be stored according to either the singleguardbit representation or the multipleguardbit representation  the approach is the same in either case. The steps illustrated hi FIG. 14 then represent an exemplary implementation of step 305 shown hi FIG. 3. As indicated at step 1401, the processing unit 105 adds the contents, a, of the first register 107, and the contents, b, of the second register 109 using addition (that is, addition with a carry into the next most significant bit if necessary). The result of the addition can be stored in another register 111 such as illustrated in FIG. 1. As indicated at step 1403, the processing unit 105 then executes a logical AND operation between the quantity (a+b) stored in register 111 and a first predetermined binary quantity Ml stored hi one of the registers (e.g., register 113). The quantity Ml has values of zero at bit positions corresponding to bit positions of first guard bits stored in the first register 107 and has binary values representing the quantity 2ml at bit positions corresponding to bit positions of each group of first data bits stored in the first register. For example, where p5 (i.e., m=2 where p=2m+l), the first predetermined binary quantity Ml comprises successive binary strings (0, 0, 1, 1) separated by bit values of zero (corresponding to guardbit positions), because 2ml=3, which is given by (0, 0, 1, 1) in binary. The above definition for the quantity Ml is applicable to the multipleguardbit representation as well as to the singleguardbit representation for the case where p=2m+l. The result of the operations indicated at step 1403 can be referred to as first intermediate data cl and is stored in one of registers (e.g., register 115). As indicated at step 1405, the processing unit 105 executes a logical AND operation between the quantity (a+b) stored in register 111 and a second predetermined binary quantity M2 where M2 is given by M2=NOT(M1). The NOT operation is bitwise logical negation. The result of this operation is stored in one of registers (e.g., register 117). Also indicated at step 1405, the processing unit 105 then executes a right shift by m bits on the quantity ((a+b)&M2). The result of this operation can be stored in the same register 117 or in a different register. At step 1407, the processing unit 105 subtracts the quantity {((a+b)&M2)> >m} from a third predetermined binary quantity PI. The quantity PI has values of zero at bit positions corresponding to bit positions of the first guard bits stored in the first register and has binary values representing the quantity 2ra+l (=p) at bit positions corresponding to bit positions of each group of first data bits in the first register. For example, where p=5 (i.e., m=2) the third predetermined binary quantity PI comprises successive binary strings (0, 1, 0, 1) separated by bit values of zero (corresponding to guardbit positions), because 2m+l=5 which is given by (0, 1, 0, 1) in binary. The result of the operations indicated at step 1409 can be referred to as second intermediate binary data c2 and is stored in one of the registers (e.g., register 119). At step 1409 the processor executes addition between the first intermediate binary data cl and the second intermediate binary data c2 to generate the third binary data, represented by c, which can be stored in one of the registers (e.g., register 121). According to this approach, the third binary data c represents the sum of the first field element and the second field element. The algorithms according to FIGS. 3 and 14 have been described in terms of a specified sequence of steps to facilitate the description. However, it is not necessary to carry the steps indicated in FIGS. 3 and 14 in the exact order illustrated. Those of ordinary skill in the art will recognize that the order of steps can be varied and that some of the steps can be carried out simultaneously. For example, steps 301 and 303 shown hi FIG. 3 can be carried out simultaneously, and steps 1403 and 1405 shown in FIG. 4 can be carried out simultaneously. Regardless of the sequence in which various operations are executed,' it is merely necessary to determine the quantity c (third binary data) in accordance with the relation where a is first binary data representing the first field element, b is second binary data representing the second field element, + represents addition, and Ml, M2 and PI are as defined above. In this regard, those of ordinary skill in the art will recognize that each group of data bits Cj of the resulting quantity c represents a value that is an element of the set Sp+, and each such Cj is given by Cj=(aj+bj) mod(p) (up to a single multiple of p), where the j subscript for the quantities a and b designate corresponding groups of data bits that represent an associated coefficient of the respective field element. Thus, it is evident that addition of field elements in GFfc*) where p=2TO+l can be carried out using six simple instructions (compared to five simple instructions for p=2ml). Utilizing the second term (Pl{(c '&M2) > >m)}) as an additive quantity in equation 36 is, hi principle, the same as subtracting the quantity ((a+b) div 2*) modulo p, thus making equation 36 consistent with equation 33. However, implementing subtraction of a quantity q as an addition of the quantity pq has advantages. In particular, if subtraction is implemented in a conventional way, i.e. by subtracting ((a+b) div 2m) rather than by adding (Pl{(( a4b)&M2)»m)}), there is a possibility of encountering negative "borrows" even if no additive carries are encountered. In contrast, by utilizing the additive quantity (Pl {((a+b)&M2)> >m)}), such negative borrows can be avoided. To prove that the approach given in equation 36 will produce correct addition results, observe that if a^ and bj e Sp+, then any Cj of the quantity c in equation 36 will satisfy 0 l, as discussed above. An exemplary approach 2100 for implementing GF_p_k_ADD where p/6 WE CLAIM: 1; A cryptographic and/or error correction apparatus carrying out computations involving field elements of an odd characteristic finite field GF(pk), the apparatus comprising: a memory; and a processing unit coupled to the memory, comprising a general purpose wbit ALU and two binary general purpose wbit registers, wherein the processing unit stores binary data representing any two field elements of an oddcharacteristic finite field GF(pk) in a first and a second wbit binary register, p being an odd prime number, the field element comprising k coefficients in accordance with a polynomialbasis representation, the binary data comprising plural groups of data bits, wherein each group of data bits represents an associated one of the k coefficients, the storing being such that at least one guard bit is positioned adjacent to the most significant bit of each group of data bits, each group of data bits being separated from an adjacent group of data bits by a corresponding at least one guard bit, and executing a fixed number of wbit ALU operations on contents of the registers thereby producing the result of a finite field operation. 2. The cryptographic and/or error correction apparatus as claimed in claim 1, wherein the processing unit assigns an initial value of zero to each at least one guard bit. 3. The cryptographic and/or error correction apparatus as claimed in claim 1, wherein multiple guard bits are positioned adjacent to the most significant bit of each group of data bits. 4. The cryptographic and/or error correction apparatus as claimed in claim 1, wherein the finite field operation is a finite field addition. 5. The cryptographic and/or error correction apparatus as claimed in claim 1, wherein the finite field operation is a finite field multiplication. 6. The cryptographic and/or error correction apparatus as claimed in claim 4, wherein p = 2m d, d is an odd integer greater than or equal to 3 and less than 2m1, m is an integer greater than or equal to 3, each group of first data bits and each group of second data bits is m+1 bits in size m > 1, said execution of a fixed number of wbit operations comprises combining the contents of first register, and the contents of the second register, in accordance with equation number 37 such as herein described. 7. The cryptographic and/or error correction apparatus as claimed in claim 4, wherein p=2m+d, d is an odd integer greater than or equal to 3, m is an integer greater than or equal to 3, and less than 2m 1, each group of first data bits and each group of second data bits is m+2 bits in size, and p=2N ±1 for any integer N. said execution of a fixed number of wbit operations comprises combining the contents of first register, and the contents of the second register, in accordance with equation number 40 such as herein described. 8. The cryptographic and/or error correction apparatus as claimed in claim 4, wherein p=2ml, m is an integer greater than or equal to 2, and each group of first data bits and each group of second data bits is m bits in size, said execution of a fixed number of wbit operations comprises combining the contents of first register, and the contents of the second register, in accordance with equation number 13 such as herein described. 9. The cryptographic and/or error correction apparatus as claimed in claim 4, wherein p=2m+l, m is an integer greater than or equal to 2, and each group of first data bits and each group of second data bits is m+2 bits in size, said execution of a fixed number of wbit operations comprises combining the contents of first register, and the contents of the second register, in accordance with equation number 36 such as herein described. 10. The cryptographic and/or error correction apparatus as claimed in claim 5, wherein said execution of a fixed number of wbit operations comprises combining the contents of first register and the contents of the second register in accordance with equation number 18 such as herein described. 11. The cryptographic and/or error correction apparatus as claimed in claim 1, wherein the binary data represents the field element in entirety and wherein said executing at least one operation comprises calculating a quantity given by equation number 32 such as herein described. 

761DELNP2005Abstract(05092008).pdf
761DELNP2005Abstract(09032009).pdf
761DELNP2005Abstract(09092008).pdf
761DELNP2005Claims(05092008).pdf
761DELNP2005Claims(09032009).pdf
761DELNP2005Claims(09092008).pdf
761delnp2005complete specification (granted).pdf
761DELNP2005CorrespondenceOthers(05092008).pdf
761delnp2005correspondenceothers.pdf
761delnp2005description (complete)05092008.pdf
761delnp2005description (complete).pdf
761DELNP2005Drawings(05092008).pdf
761DELNP2005Form1(05092008).pdf
761DELNP2005Form1(09092008).pdf
761DELNP2005Form2(05092008).pdf
761DELNP2005Form2(09092008).pdf
761DELNP2005Form26(05092008).pdf
761DELNP2005Form3(05092008).pdf
761DELNP2005Form5(05092008).pdf
761delnp2005pctsearch report.pdf
761DELNP2005Petition137(05092008).pdf
Patent Number  233901  

Indian Patent Application Number  761/DELNP/2005  
PG Journal Number  20/2009  
Publication Date  15May2009  
Grant Date  17Apr2009  
Date of Filing  25Feb2005  
Name of Patentee  TELEFONAKTIEBOLAGET LM ERICSSON (PUBL.)  
Applicant Address  S126 25 STOCKHOLM, SWEDEN.  
Inventors:


PCT International Classification Number  G06F 7/00  
PCT International Application Number  PCT/SE2003/001560  
PCT International Filing date  20031007  
PCT Conventions:
