Finite field multiplication

Background of the Invention

The present invention relates to a method and apparatus for multiplying two elements in the finite field GF(2^m). .

As explained fully in European application 0080528 from which the following discussion is taken, the finite field GF(2^m) is a number system containing 2^m elements. Its attractiveness in practical applications results from the ability to represent each element by a vector of m binary digits. The practical application of error-correcting codes makes considerable use of computation in GF(2^m). Both the encoding and decoding devices for the important Reed-Solomon codes must perform computations in GF(2^m). The decoding device for the binary Bose-Chaudhuf i-Hocquenghem codes also must perform computation in GF(2^m). The reader is referred to Error-Correcting Codes by W.W. Peterson and E.J. Weldon, Jr., 2nd Ed., the M.I.T. Press, 19 72, for details of these and other applications of GF(2^mj computation for error-correction.

There exist cryptographic systems with encryption and decryption algorithms that require exponentiation operations on large numbers. Several public-key cryptosystems have been proposed that require or may be adapted to use the exponentiation of elements in GF.(2^m) . Since the process of exponentiation consists of squaring and multiplication operations, it is essential that these operations be performed

W.

WO 88/04805 PCT/US86/0>751 ''

- 2 as quickly and efficiently as possible. The reader is referred to Cryptography and Data Security by D. E. Denning, _t

Addison-Wes.ley, 1983, for desriptions of Gt'(2^m) arithmetic and ' exponentiation algorithms, and for examples of public-key cryptosystems utilizing these algorithms.

Recent advances in the art of secrecy coding also require the use of computation in GF(2^m). The reader is referred to the letter Implementing Public Key Scheme, by S. Berkovits, J.

Kowalchuk and B. Schanning, IEEE Communications Magazine, Vol.

17, pp. 2-3, May 1979.

The finite field GF(2) is the number system in which the only elements are the binary numbers 0 and 1 and in which the rules of addition and multiplication are the following:

+ 0 = 1 + 1 = 0 + 1 = 1 + 0 = 1 4

0x0 = lx0 = 0x1 = 0 (1)

1x1 = 1

These rules are commonly called modulo-two arithmetic. Hence all additions specified in logic expressions or by adders in this application are performed modulo two. In addition, multiplication is implemented with logical AND gates to correspond with the rule set out at (1) above. The finite field

GF(2^m), where m is an integer greater than 1, is the number | system in which there are 2^m elements and in which the rules ’ ' . . :. . ^: γ, of addition and multiplication correspond to arithmetic modulo ' i ’i

- T ii ϊ

V.

^! WO 88/04805

PCT/US86/02751

<img file="AU625552B2_D0001.tif" />

<img file="AU625552B2_D0002.tif" />

- 3 an irreducible polynomial of degree m with coefficients in GF(2) . Although in an abstract sense there is foe each m only one field GF(2^m), the complexity of the logic circuitry required to perform operations in GF(2^m) depends strongly on the particular way in which the field elements are represented.

The conventional approach to the design of logic circuitry to perform operations in GF(2^m) is described in such papers as T. Bartee and D. Schneider, Computation with Finite

Fields, Information and Control, Vol. 6, pp. 79-98, 1963. In this conventional approach, one first chooses a polynomial Ρ (X) of degree m which is irreducible over GF(2), that is P(X) has binary coefficients but cannot be factored into a product of polynomials with binary coefficients each of whose degree is less than m. An element A in GF(2^m) is then defined to be a root of Ρ (X) , that is, to satisfy P(A) = 0. The fact that P(X)

2 is irreducible guarantees that the m elements A = 1, A, A ,

..., A^{m 1} of GF(2^m) are linearly independent over GF(2) ,

Ό ml that is, that b_n + b A + b A + ... + b .A 0 12 m-1 vanishes only when the binary digits b_,b,,b„ ..., b , • 0 12 m-1 are all zeroes. The conventional approach is then to assign the unit vectors of length m with binary components to the elements, , ' x 2 »m-l

X t A / A _r . . . _t A «

As a specific example of the conventional approach, consider the finite field GF(2^) with the choice

P(X)=X³+X+1 (2) for the irreducible polynomial of degree 3. The next step is to define A as an element of GF(2³) such that

A³ τ A + 1 = 0

A' (3)

WO 88/04805 ₄ . J , PCT/US86/02751 .1

- 4 The following assignment of unit vectors is then made:

A° = 1 = [0, 0, 1]

A = [0, 1, 0]

A² = [1, 0, 0] (4)

An arbitrary element B of GF(2³) is now represented by the binary vector [b₂&gt; b]_, bg] with the meaning'.that

B .= [b₂,b}_,b.g] = b₂A² + b]_A + bg \ (5)

Let C = [c₂,C]_,cg] be a second element of GF(2³) · ft follows from equations (4) and (5) that \

B + C = (b₂ + c₂,bj_ + cj_,bg + eg]. . (6)

Thus, in the conventional approach, addition in GF(2^m) is easily performed by logic circuitry that merely forms the modulo-two sum of the two vectors representing the elements to be summed component-by-component. Multiplication is, however, considerably more complex to implement. Continuing the example, one sees from equation (3) that

A³ = A + 1 A⁴ = A² + A (7) where use has been made of che fact that -1 = +1 in GF (2).

From the equations (4), (5) and (7) it follows that

B x C - [d₂, dp dg] (8) where ^d0 ^{= b}0^c0 ^{+ b}l^c2 ^{+ b}2^cl ^dl ^=b0^cl ^{+ b}l^c0 ^{+ b}l^c2 ^{+ b}2^cl ^{+ b}2^c2 ⁽⁹⁾ d₂ = ^b0^c2 ^{+ b}2^c0 ^{+ b}l^c] ^{+ b}2^c2

WO 88/04805

PCT/US86/02751

<img file="AU625552B2_D0003.tif" />

- 5 Complex logic circuitry is required to implement equations (9). Upon taking C = B equation (8), it follows from equation (9) that = [&amp;2' ^el' ^e0) (¹°) where ^e0 = t&gt;₀ e i ⁼ b2 (11) ^e2 = t&gt;l + b₂ and where use has been made of the facts that b = b and b + b = 0 in GF (2) . Whereas the squaring rule of equations (11) is considerably simpler to implement than the multiplication rule of equations (9) , it. still has the disadvantage that some additions (in the example, only one ) must be performed and that the form of the squaring rule varies among the components of the square.

By way of summary, one can say that the conventional approach to the design of logic circuitry to perform operations in GF(2^m) leads to simple circuitry for addition, somewhat more complex circuitry for squaring, and very complex circuitry for multiplication.

In the European application 0080528 noted above advantage was taken of the following special features of the finite field GF(2^m) . There always exists a so-called normal, basis for this finite field, that is, one can always find a

<img file="AU625552B2_D0004.tif" />

J ί

WO 88/04805

PCT/US86/02751

-61-.

I . 2 4 2 field element A such that A, A , A , ..., A are a basis for GF(2^m in the sense that every field element B can be uniquely written as

<img file="AU625552B2_D0005.tif" />

ϊ':

,m-l m-Γ b₂A b^A b₀A (12)

<img file="AU625552B2_D0006.tif" />

I ^[bm-l.....' ^b2' ^bl' ^b0^ where bg, b^, b2, ..., ^are binary digits.

Moreover, squaring in GF(2^m is a linear operation in the sense that for every pair of elements B and C in GF(2^m) (B + C)² = B² + C² (13)

Further, it is the case for every element

B of GF(2^m) that ~m

B^z = B (14)

The inventors in the above application sought to simplify the multiplication procedure by initially choosing a polynomial P(X) of degree m which is irreducible over GF (2) and which has linearly independent roots. This latter condition on P(X) insures that upon defining A as an e. lenient of GF(2^m) such that z. 4 2^m_1

P(A) = 0 then A, A , A , ... A form a normal basis for GF(2^m).

For a discussion of normal bases in finite fields, the reader is referred to Finite Fields by Lidl and Neidereiter.

<img file="AU625552B2_D0007.tif" />

'ΤΙΤΙ1ΤΪ·

<img file="AU625552B2_D0008.tif" />

V ^f WO 88/04805

PCT/US86/02751

- 7 Then if B = (b ., ..., b,,, b. , b ,] and m-1 2 1 d

C = (c ..·, , c , Cq] are any two elements of

GF(2^m) in said normal basis representation, then the product

D = Β X C = (d . ·.., d_, d. , d_] (15) m-1, 2 1 0 has the property that the same logic circuitry which when applied to the components or binary digits of the vectors representing B and C produces d_[n_^ will sequentially produce the remaining components d^' ···, d^, d^, άθ of the ·».

product when applied to the components of the successive rotations of the vectors representing B and C.

This may be appreciated by considering the binary digits d^r d^, d^ of e.g. equation (9) above where ^d2 “ ^bl^cl ^{+ b}0^cl ^{+ b}l^c0 ^{+ b}0^c2 ^{+ b}2^c0 ^dl ^{= b}0^c0 ^{+ b}2^c0 ^{+ b}0^c2 ^{+ b}2^cl ^bl^c2 d₀ - b₂c₂ + b]_c₂ + ό₂θ! + bj-CQ + όθοχ

<td> Like</td><td> ones of one</td><td> of</td><td> the binary digits bj_ or</td><td> Cj_ are grouped</td>

<td colspan="2"> to obtain grouped</td><td colspan="2"> terms so that these may be</td><td> : rewritten in the</td>

<td> form</td><td> d₂ = Dq</td><td> (c_x</td><td> + c₂) + cq (b+ b₂) +</td><td>^bl^cl</td>

<td></td><td> di = b₂</td><td> (c₀</td><td> + Cj_) + c₂ Φβ + bj_) +</td><td>^bo^co</td>

<td></td><td> do = b_x</td><td> (c₂</td><td> + eg) + c_x (b₂ + brt) +</td><td>^b2^c2</td>

Where an expression such as bgtcj. + c₂) is subsequently referred to as a grouped term. Thus the logic equation for dj_ could be derived from that for d₂ by reducing the suffix of

<img file="AU625552B2_D0009.tif" />

WO 88/04805

PCT/US86/01751

- 8 all binary digits b^, c^, by 1 (Modulo-3). A practical implementation was achieved by entering the vectors in respective shift registers, establishing connections and implementing digital logic circuitry to generate all terms of the component d₂ simultaneously. Then the shift register contents are rotated one bit position to obtain d^, and, similarly d_Q. Thus, by rotating the vectors B and C in the two shift registers., the binary digits of the product vector D could be generated by the one logic circuit.

However, whilst the above proposal is more efficient than the conventional approach, it suffers the disadvantage that all grouped terms constituting one binary digit of the vector must be added simultaneously at one location. This makes the implementation of the logic complicated, and for large values of m, (e.g. greater than 250), impractical. The above European application also proposes the simultaneous or parallel generation of all m binary digits of the product vector by m identical multiplier logic circuits. However, this simply compounds the difficulty of logic implementation because of the increase in external shift register connections and the large amount of circuitry required.

The applicants have recognised that multiplication may be implemented by storing bit vectors B and C in respective shift registers and establishing connections to respective accumulating cells such that a grouped term of each of the expressions d₄ is generated in respective ones of m

<img file="AU625552B2_D0010.tif" />

Λ ' ‘ WO 88/04805

PCT/US86/02751 accumulating cells. By rotating the bit vectors B and C in the shift registers and by rotating the contents of the accumulating cells each grouped term of a respective binary digit is accumulated in successive cells. Thus all of the binary digits of the product vector are generated simultaneously in the accumulating cells after one complete rotation of the bit vectors B and C.

Embodiments of the invention will now be described by way of example only with reference to the accompanying drawings in which ‘ί ·

<img file="AU625552B2_D0011.tif" />

Figure 1 is a block diagram of a multiplier to implement multiplication of two elements in the field GF(2^).

Figure 2 is a block logic diagram of a component used in the multiplier of Figure 1.

Figure 3 is a block diagram of an alternative form of multiplier to implement multiplication of two elements in the field GF(2⁵) .

Figure 4 is a block diagram of a further embodiment of a multiplier to implement multiplication in the field GF(2^).

Figure 5 is a block diagram of the multiplier of Figure 4 with the connections modified for an optimal implementation of a GF(2^) multiplier.

The principle of operation may best be understood by reference to Figures 1 and 2 that represents the logic implementation for multiplying two elements in the finite field GF(2⁵) . Before referring to the figures in detail, it will be useful to consider the form of the product D of two element's B and C

<img file="AU625552B2_D0012.tif" />

<img file="AU625552B2_D0013.tif" />

-1026

PCT/US 86/02751

Rac'd PGi-RTO 04 JMl

Ξ will be of th·· form B = (b_Q, b^, b₂, b₃, in normal basis representation and C will be of the form C c₄) in

Ό' 1' 2' 3 ' normal bas^s representation.

The product D will be of the form d ₃, a,) in normal basis represenEach of the bit vectors d^ will consist of tat ion .

grouped terms of the binary digits representing B and C and for the case where m - 5 d.· = b , Ac :

^{+ C}i + 3 ^{+ c}i₊l^{+ c}i^}^{+ b}i + 3

<td>^(ci.4^{+ c}i+2^{+ c}itl ^{+ c}i&gt;</td><td>^{+ b}i+2⁽Si+3^{+ c}i</td>

<td>^{+ b}i +1 ^cit4 + ^ci+3)</td><td> 1¹</td>

<td> + 4&lt;4 + 4 ^{+ c}i+3 ^cit2^}</td><td></td>

<td> In general, all subscripts a</td><td> re added using</td>

<td colspan="2"> module 5 arithmetic. Thus the binary digits have</td>

<td> f o rm :</td><td></td>

<td>^d0 ^{= b}4^(c4^C3^+Cl^+C0^{) + b}3^(c4</td><td> +C₂tC₁+C_q)t</td>

<td> b^IC^tCg) t bj- ( C^ + C^ y</td><td> t b_Q(C₄+C₃TC₂)</td>

<td>^dl ^{= b}0^(c0 ^{+ c}4 ^{+ c}2 ^{+ c}l&gt; ⁺</td><td>^b4^(c0 ^{+ c}3 ⁺</td>

<td> c₂ + C_L) + b₃(C₄ + 4)</td><td> + b₂(c_Q + c₄) +</td>

<td>^bl ( ^c0 ^C4 ^C3</td><td></td>

<td>^d2 ~ ^bl^(cl ^{+ C}0 ^{+ C}3 ^{+ c}2^ ⁺</td><td>^b0^^cl ^{+ c}4 ⁺</td>

<td>^c3 ^{+ c}2 ^{+ b}4^^c0 ^{+ c}2^</td><td> + ^b3(^Cl + Cg) +</td>

^b2^{( C}1 ^C0 + ^c4^} d, =

<img file="AU625552B2_D0014.tif" />

b₂(c₂ + ^ci + ^c4 + c₃) + b₁(c₂ + c_c^b3 ^(c 2 ^b3 ( ^c3 ^C0 +

<td>^c3^{} + + C}1</td><td>^b0^(cl + Cg)</td><td> + c₃)</td><td> + bje</td>

<td> + c₂ '</td><td> + Cg +</td><td>^c4 ) ⁺</td><td>^b2^(c3</td>

<td> c₄) +</td><td> 4((=2</td><td>^{+ c}4&gt;</td><td> + bg(C</td>

<td> + c₂</td><td> + 4)</td><td></td><td></td>

+ Cj + 4 + 3 ^{+ c}2⁾

SUBSTITUTE SHEET IPEA/US

J ' ' ‘ WO 88/04805

PCT/US86/02751

<img file="AU625552B2_D0015.tif" />

- il It will be appreciated from the above that by establishing logic connections to generate the first grouped term b,(c. + c.+ c. + c_n) of d_n , the first grouped 4 4 3-1 0 0 term of the binary digits d , d^ , d^, and d^ will also ^: t be generated by these same connections if the bit vectors of B and C are successively rotated one place to the right. The applicants have recognised that if connections are also established to generate the second grouped term of d_Q after the generation of the first grouped term and the bit vectors have been rotated, the connections will in fact generate the second grouped term of d^ prior to rotation of the bit vectors

B and C. Thus by establishing connections to generate successive group terms of the binary digits όθ in successive ?

clock cycles, it is possible to accumulate in parallel each of , the binary digits of the product vector. This simplifies ^: implementation of the logic.

Referring therefore to Figure 1, a multiplier 10 includes a pair of shift registers 12, 14 each having m cells 16. Shift registers 12 and 14 are loaded with bit vectors B and C respectively so that each cell 16 contains one of the binary digits b. or c..

The shift registers 12, 14 are connected, in a manner to be described below, to the respective ones of accumulating cells 18 of a term accumulating register 20. The register 20 will have m cells 18 each of which is configured as shown in jj

Figure 2. Referring to Figure 2, each ceii 18 receives a pair ‘ · V * of inputs 22, 24 that originate from the shift registers 12, 14 V

«

.....

WO 88/04805

PCT/US86/02751 ¹ '^(S

<img file="AU625552B2_D0016.tif" />

-12respectively and an input 26 from the adjacent cell 18 of the register 20. The inputs 22, 24 are connected to inputs of an AND gate 28. The output of gate 28 is added to the input 26 at MOD 2 ADDER 30 whose output is connected to a latch 32. The output of latch 32 forms the input 26 of the next cell 18 and receives a clock signal 34 to store the output of ADDER 30.

The nature of inputs 22, 24 is determined by the connections implemented between the cells 16 of shift registers 12, 14 and the cell 18. The connections are arranged such that one grouped term of the binary digits d^ is generated at the output of AND gate 28. Thus for the binary digits d_Q to d₄ shown above, the binary digits bg to b₄ and c_q to c^ are stored in shift registers 12, 14 respectively as indicated in Figure 1. A first grouped term of dg is to be accumulated in cell 18 indicated as dg in Figure 1, i.e. the output of AND gate 42 will represent the grouped term bg(c₄^{+ c}3 ^{+ c}2)’ ^To i^mPl^ement this, a connection is established from the cell 16 of shift register 12 containing the binary digit bg to form input 22. Connections from cells 16 of shift register 14 containing binary digits c₄ , c₃ and c₂ are made to ADDER 36 whose output, representing c₄ + + c₂ , forms the input 24 to AND gate 28. The output of AND gate 28 will thus be bg(c₄ + + C2).

Connections are made between the shift register 12, 14 and the cell 18 indicated as d^ to generate the penultimate grouped term of d·^, i.e. the term b₂(cg + c₄). Thus f;

τ &lt;**1 iTr .

ΐ'ί

<img file="AU625552B2_D0017.tif" />

PCT/US86/02751

WO 88/04805 . - 13 cells 16 of shift register 14 containing the binary digits οθ and c^ are connected to adder 38 whose output forms input 24 of the cell 18 designated d^ and cell 16 of shift register 12 containing binary digit b₂ is connected as the input 22 of cell 18 designated so that the output of AND gate 28 is ^2 (^c0 ^{+ c}4 ) '

Similarly the shift registers 12, 14 are connected to the cell 18 indicated d₂ to generate the third term of binary digit d₂, i.e. b^ (οθ + c^) to the cell 18 indicated όθ to provide the second term of binary digit d^, i.e.

b.(c_ + c_n + c. + c-,) ; and to the cell 18 indicated to produce the first term of binary digit d^, i.e.

^b3^(c3 ^{+ C}2 ^{+ C}0 ^{+ C}4^} *

In general, therefore, the jth cell 18 of accumulating register 20 is connected to the shift registers 12, 14 to produce the jth grouped term of a binary digit d_i with the subscripts of binary digits b^ and c increased by j-1 using modulo m arithmetic. This adjustment of the subscripts of the grouped term is called offsetting¹' and ensures that each of the m accumulating cells generates one grouped term of each of the binary digits d^ during each of m successive clock cycles.

With the connections established the binary digits άθ to dj. can be generated as follows.

First, the binary digits b_Q to b₅ are loaded into shift register 12 and the binary digits c_Q to c₅ are loaded into shift register 14. These may be loaded in parallel or in

<img file="AU625552B2_D0018.tif" />

<img file="AU625552B2_D0019.tif" />

secies as is most appropriate for the particular shift register utilised. The contents of the latches 32 of the cells 18 of accumulating register 20 are cleared by loading zeroes into each. Upon initation of the multiplication, the grouped terms corresponding to the connections noted above will be generated at the output of each AND gate 28. Because each of the inputs 26 is zero the outputs of the MOD 2 ADDER 30 in each case will correspond to the output of the AND gate 28.

On the first rising edge of the clock signal, the output, of each ADDER 30 is entered into the corresponding latch 32 to appear as the input of the adjacent cell 18. Thus, latch 32 of cell 18 designated dg will contain the term bg (c^ + ^c3 ^{+ c}2^ ’ }-^at-^ch of cell 18 designated d^ will contain the term t&gt;2 (^cq ^{+ etc}· The first rising edge of the clock signal causes the simultaneous rotation one position to the right of the contents of registers 12, 14 respectively so that the binary digits b^ and c are transferred to an adjacent cell. Thus, the inputs to cell 18 designated d_Q will now be b₄ from shift.register 12 and (c^ + c₂ + c^) from the adder 36. The output of AND gate 28 of cell 18 designated d_Q will thus be b₄ (ο_χ + c₂ + cp . The input 26 of cell 18 (dg) will be the contents of latch 32 of cell 18 (d₄) , i.e. (c₃ + c₂ + ο_β + c₄) and thus the output of the MOD 2 ADDER 30 of cell 18 (d_Q) will be b₄(c_{L +} c_{2 +} c₃) ₊ b₃(c₃ + c_{2 +} c₀ + c₄).

It will be seen that this corresponds to two grouped terms of

I

1' ’{ i

ί . WO 88/04805 ' PCT/US86/02751

- 15 the binary digit d^ set out above. A careful consideration of the output of each ADDER 30 will show that the sum of two grouped terms of each binary digit d^ will appear as the input of respective latches 32.

On the next rising edge of the clock signal, the outputs of each ADDER 30 will be entered into respective latches 32 and the binary digits b^ and c^ rotated in the shift registers 12, 14 respectively. Thus, the contents of the latch of cell 18 (d_Q) , namely b₄(c^ + c₂ + c₃) + b₃ (c₃ + ^c2 ^{+ c}0 ^{+ c}4^ ^wx^l be present as input 26 of cell 18 (d^) and the output of AND gate 28 of cell 18 (d^) will be bg (^c2 ⁺ £3), i.e. a third grouped term of the binary digit d₄. It will be appreciated that after five clock cycles, the sum of all grouped terms of the binary digit d^ will be stored in the latch of cell 18 designated d₃ and similarly the sum of all the grouped terms of binary digits d₃ to d^ will be stored in respective ones of cells 18. Thus, the bit vector constituting the normal basis representation of product D is available by reading the ;ontents of the accumulating register 20.

It will also be noted the connections from the cells 16 of shift registers 12, and 14 are distributed amongst the cells 18 of accumulating register 20 to reduce the number of inputs of any adder.

Whilst the above multiplier constitutes a significant improvement over that described in the European patent

PCT/US86/02751

WO 88/04805

<img file="AU625552B2_D0020.tif" />

-16application 0080528, the number of connections may be reduced further although the number of

J .

clock cycles required to generate the binary digits d. is increased. A multiplier for the ^x 5 field GF(2 ) is shown in figure 3 and is similar to that shown in figure 1. Accordingly the reference numerals used in the description of figure 1 and 2 will be used to identify like components with a prefix 100 added, i.e.

reference numeral 12 will become 112. The arrangement shown in figure 3 differs in two important ways, namely the provision for exchanging the contents of shift registers 112 and 114 as indicated by dashed lines 150, 152 and the nature of the connections between the cells 116 and cells 118. It will also be noted that the shift registers 112, 114 are controlled by a separate clock signal, indicated at clock 1, to the accumulating register 120 whose clock signal is indicated at clock 2.

The nature of the connections is established from a further manipulation of the terms representing the binary digits d^. Thus considering the binary digit d₄ above, this may be written as:

b₃c₃+b2C2⁺t&gt;₃Cg+b2C₄+b2C2+b2C₁+b2Cg+ ^b2^c4^+bl^c2^+bl^c4^+b0^c3^+b4^c3^+b4^c2^+b4^cl and rearranged as [όβc2*^C33 + [ββ^+βθΟβ] “h ^^3^4 + b₄c₃J + [b₂c₁ + b₁c₂l + b₂c₄ + b₄c₂l /

S..

<img file="AU625552B2_D0021.tif" />

<img file="AU625552B2_D0022.tif" />

', WO 88/04805

PCT/US86/02751

- 17 It will be observed that the terms within the brackets (] possess a symmetry such that i± one product term is of the form b.c. , the other product term is obtained by interchanging the suffixes, i.e. b.c.. It has been recognised that by implementing the logic to produce one product term of each pair, the other product term may be obtained from a simple interchange of the contents of the shift registers and by a repeated circuit operation each of the product terms of each pair may be obtained. Moreover, the offsetting principle still applies so that the terms of each binary digit will be generated in parallel. The expression for digit d. is ^b3^C3

<td></td><td> b₃c₂</td><td> +</td><td>^b2^C3</td>

<td> +</td><td> b_nc_n</td><td> +</td><td> b„ c-,</td>

<td></td><td> 3 0</td><td></td><td> 0 3</td>

<td> +</td><td> b.,c .</td><td> +</td><td> b . c_n</td>

<td></td><td> 3 4</td><td></td><td> 4 3</td>

<td> +</td><td> b_c _Ί</td><td> +</td><td> b-, c^</td>

<td></td><td> 2 1</td><td></td><td> 1 2</td>

<td> +</td><td> b_c„</td><td> +</td><td> b„c„</td>

<td></td><td> 2 0</td><td></td><td> 0 2</td>

<td> +</td><td> D-.C .</td><td> +</td><td> b . c„</td>

<td></td><td> 2 4</td><td></td><td> 4 2</td>

<td> +</td><td> D , C _Λ</td><td> +</td><td> b . c _</td>

<td></td><td> 1 4</td><td></td><td> 4 1</td>

i.

The product terms in column Y are then selected and like terms grouped as discussed above with reference to figure 1. Thus column Y may be expressed as b^ic^ + οθ + c^) + ^b2^°l ^{+ C}0 ^{+ c}&lt;p ^{+ b}l^C4 implementing the logic to generate these terms in successive cells 118 of accumulating register 120, the terms of column Z will also be generated after interchange of the shift registers 112, 114 by a second pass

I:

WO 88/04805

PCT/US86/02751 “

<img file="AU625552B2_D0023.tif" />

- 18 through the accumulating cells. The odd term of column X may be generated during one of the two passes through the cells 118 with its generation inhibited during the other pass.

It will be noted that the grouped terms of column Y ' would require 3 inputs to two of the ADDERS whilst only 3 of the accumulating cells 118 are utilised. In order to spread the connections evenly between the cells 118, the expression is modified to select one of each pair of product terms but obtain _ a different grouping. Thus, in the example above, the third and sixth product terms are selected from column Z rather than Y so that the expression b^ (c₂ + c_Q) + ^(c^ + c₂) + b₂ (^ci ^{+ c}0&gt; ⁺ ^l^c4 ^to b^e implemented.. This increases the number of cells 118 utilised and reduces the number of ^: connections to some of the ADDERS. .

’ ί

Referring therefore to figure 3, the final term ' b^Cj is implemented in the cell 118 designated d_Q(referred to hereafter as 118 [d_Q] ) by connecting cell 116 of shift register 112 containing binary digit b^ and cell 116 of shift register 114 containing binary digit c^ to the AND gate 128. The connections to the second of cells 118 is established from a second term with the suffixes of the binary digits increased by 1, Modulo 5 i.e. b^(c₂ + c^) and in general the jth cell 118 accumulates a jth term of the expression with suffixes increased by j-1 (Modulo m).

Connections are also established to implement the odd ' | term b^c^ of col .un X in cell 118 designated d^ . The ' connections to d^ are modified to Include an AND gate 154 to . I . . . ' ' , φ I . . . . . . : {

I

L

WO 88/04805

PCT/US86/02751

- 19 inhibit the accumulation of the add terms e.g. b^c^. The AND gate 154 is located between the cell 116 designated c^ and ADDER 160 and receives as one input the output of cell 116 and as its other input an inhibit signal 156 derived from the clock signal. When the inhibit signal 156 is logic level 0, the output of AND gate 154 will be zero so that zero will be added by ADDER 130 to the contents of the latch 136 of the previous cell 118 [d₃l.

With the connections established, the binary digits b„ to b. and c_n to c, are loaded in respective cells 116 0 4 0 4 of shift registers 112, 114. The contents of each cell 118 is cleared so that each latch 132 contains 0 and the inhibit signal 156 is held at logic level 0 to force the output of AND gate 154 to also be zero.

The contents of the shift registers 112, 114 and the cells 118 are then rotated one bit position rightwards by successive clock cycles so that after m clock cycles one of each part of the paired product terms is accumulated in respective cells 118. The generation of the terms is shown in table 1 below.

PCT/US86/02751

WO 88/04805

<img file="AU625552B2_D0024.tif" />

- 20 Thus, it will be seen that the terms in d^ correspond to the rewritten expression for one of each of the pairs of product terms.

After five clock cycles, registers 112, 114 will have undergone a complete rotation so that binary digits b^ and c . will be stored in the cells 116 in which they were 1 initially loaded.

Now the contents of the shift registers 112 and 114 are exchanged through connections 150, 152. This may be accomplished by shifting the contents of both registers 112, 114 for five clock cycles as a serial, circular exchange or alternately could be achieved by parallel connections between cells 116. Serial exchange is shown in Figure 4 and is easiest to implement for large values of m. During the exchange, clock 1 goes through five cycles while clock 2 is held low to prevent unwanted terms accumulating in register 120. When binary digits d^ pass through accumulating cells, both clock signals are identica1.

After the exchange of binary digits, the inhibit signal 156 is set to logic level 1 so that AND gate 154 passes the input from cell 116 to the input of ADDER 160. The circuit operation then continues as exemplified by the table below for the next five clock cycles. Again, it will be seen that the terms of each of the binary digits d^ are accumulated in each of the cells 118 in parallel so that after 2m clock cycles of computation the binary digits of D are available in the cells 118 of accumulating

<img file="AU625552B2_D0025.tif" />

pcr/us

ΪΟ ίΰ·?ΰ ; _t,,

86/02751 · / 04 JANIXfr register 12C. because of'the'need to exchange the contents cf the shirt registers 112, 114, additional clock cycles are required to complete the computation. However, the number of the connections between the shift registers and the accumulating register in the multiplier of Figure 3 is less than those shown in the multiplier of Figure 1 to compensate for this.

The implementation shown in Figure 3 has been used to illustrate the generality cf the above principle. However, in practical implementations particularly for large values of m, the connections may be simplified further by’¹ selecting the »

grouped terms in ascending order of the coefficient b^ or c . . In this manner a maximum of two connections between each cell of one of the shift reg is ters. and the accumulating register

In order to reduce the time taken to compute the binary digits d,. , the multiplier of Figure 3 can be further modified as shown in Figure 4. Again like components will be identified by like reference numerals with a prefix 2 added for clarity. Figure 4 shows a multiplier for generating the binary digits in the field GF(2^). It will be noted that the shift registers 212 and 214 have been segmented into 3 units, 212a, b, or c and 214 a, b or c respectively, each having two cells 116. Similarly, the accumulating register 220 is segmented into 3 units 220 a, b or c each having two cells. It will be noted that each of the shift register units 212 a, b, and c is connected to a corresponding shift register unit 214

SUBSTITUTE SHEET

IPEA/US

<img file="AU625552B2_D0026.tif" />

WO 88/04805

PCT/US86/02751

- 22 a, b and c by paths 250 a, b, c, and 252 a, b, c respectively. The paths 250,252 are utilised to exchange the contents of the registers 212, 214 between units a, b and c rather than through the entire shift register. In this way the number of clock cycles necessary to transfer the contents of the shift register is reduced from m to the number of cells 216 in each unit.

β

The binary digit d^ of product D in GF (2 ) is given by

<td>^b5^C5 ⁺</td><td>^b5^C4</td><td> + b .c 4</td><td> 5</td>

<td> +</td><td>^b2^C5</td><td> +</td><td> b₅c₂</td>

<td> +</td><td>^b0^C5</td><td> +</td><td>^b50</td>

<td> +</td><td>^bl^C2</td><td> +</td><td>^b2^cl</td>

<td> +</td><td>^b3^Cl</td><td></td><td>^bl^o3</td>

<td> +</td><td>^b4^C2</td><td> +</td><td>^b2^c4</td>

<td> +</td><td>^b0^C3</td><td> +</td><td>^b3^c0</td>

<td> +</td><td>^b2^C0</td><td> +</td><td>^b0^C2</td>

Thus by implementing the expression ^b0 ^(C3 ^{+ C}5^{} + b}l^C2 ^{+ b}2 ^(C0 ^{+ C}5^ ^{+ b}3^Cl ⁺ b₄c₂ + b(. (c^ + c₅) the binary digits d.^ of the normal basis representation of the product D can be generated. It is believed to be apparent from the above discussion that the initial connections to be established are as follows:

ί

Ί

- WO 88/04805

<img file="AU625552B2_D0027.tif" />

PCT/US86/02751

<img file="AU625552B2_D0028.tif" />

- 23 cell 118 physical connection ^b0^(C3 ^{+ C}5^{J b}2^C3 b₄(c₂ + cp ^b0^C4 ^b2^C0 ^b4^(C3 ^{+ C}4&gt;

In this case, the odd term is generated initially in [d$] and the input to the adder 236 associated with [dg] that is initially from the cell 216 containing is inhibited after the first pass through the cell 218 cell 218 digit c^ accumulating register 220 by use of an AND gate in a manner similar to that shown in Figure 3.

The operation of the multiplier of figure 4 is similar to that described above with reference to figure 3. However, exchange of the contents of the registers 212, 214 occurs over the lines 250, 252 to reduce from 6 to 2 the number of clock cycles necessary to complete the exchange.

It is believed the above examples clearly and explicitly explain the operation of GF(2^m) the multiplier. Relatively small values of m have been selected for the sake of Simplicity but it will be apparent that the above principles apply for large values of m usually employed in encryption.

However, for the larger values of m usually utilised in encryption, the number of product terms in the expression for binary digit d may increase quadratically with the value of

<img file="AU625552B2_D0029.tif" />

iSSaiftffiiash

WO 88/04805

PCT/US86/0275'l

- 24 m. This renders the implementation of a multiplier imprar- cal because of the large number of connections necessary. For those values of m listed in Table 3 there does exist an optimal normal basis in the sense that it yields an expression dthat has 2m-l product terms, the smallest number possible. Each of the integers m has an indication of type for use in the computer program discussed below. The binary digits b^c.. of the binary digit αθ of the product vector B for the optimal normal basis of a value of m listed in Table 3 may be obtained executing the computer program listed in appendix 1. By running the program for m=6 the following results were obtained:

WO 88/04805

PCT/US86/02751

- 25 which yields the equation for dg as:

^d0 ^b5^C5 ^{+ b}0^+Cl ^{+ &amp;}l^C0 ^{+ b}4^Cl ^{+ b}l^C4 ^{+ +b}3^5 ^{+ b}4^&lt;2 ^{+ b} 2 *“ 4 ^{+ b}3ⁱ2 ^{+ b}2^3

Figure 5 shows the implementation of this expression for the segmented GF(2^) multiplier shown in Figure 4 with appropriate modifications to the connections to implement the above. The rearrangement of άθ to obtain these connections will be apparent from the above and consideration of Figure 5.

An optimal multiplier design exists for every value of m listed in Table 3 such that every accumulating cell 218 has a single input from same shift register cell 216. Thus, m modulo-two ADDERS are eliminated as compared to the multipliers of Figures 1, 3 and 4 further simplifying the circuitry.

In addition, the applicants believe that the maximum number of connections to the output of any shift register cell

216 is three.

The above description has utilised block diagram representations of che registers 12, 14, 20 and the adders and logic functions. However, it is believed that the selection and operation of the components to perform the functions discussed above will be apparent to a person skilled in the art of digital logic design and that further particularis Lon of the components is not necessary.

Clearly different offset patterns may be chosen whilst utilising the principle of parallel generation of terms of each of the binary digits of cL· .

CLOCK

CYCLE ^{1 b}l^C4

0^+b0^c3 b₁(c₀+^c3⁾^+b4^c2

d.

^b3^(c2^+Cl^J bjC₄+b₂ (^c2+^c0) ^bQ^C3 bj(c₀+c₄)

TABLE 1 b₁(^c0+c₄) ^b1(c₀+c₃) b₃(c2+cp+ bt(c₀+c₄) + b₀(c₄+c₃) ^b0(c₄+c₂) ^bl^C4^+b2 b₄(c₃+c₂) b₀(c₄4c₃) αΧί «

I ^bi(^Co^+C4 ^+b0^(c4^+C2^}^b3^Cl ^bl^^c0^+c3^^{+ b}4^C2+ ^b0^(C4^+C3⁾ b₀^c3^+b1 &lt;c₀+^c4) +b₃ (Cj+cp ^bl^c4^+b2 (^cl+c₀)+ ^b4 ^(c3^+c2⁾baC^+cp o

bjJCQ+c^J+O ^bl^(c0^+c4⁾⁺^b3 (CjXCj bo&lt;C₄+^c3)+ ^b4

<img file="AU625552B2_D0030.tif" />

WO 88/04805 b₃(^c2^+ci⁵+b₀&lt;^c4+c₃) +b₄ (cycp ^+b2^c0 ^bl^(C0^+C4^{) +}b₀(c₄+c₂) + ^b3^Cl⁺b₄ (c₃+c-2 b₀c₃₊ b₄c₂+ b₁(c₀+c₄)+ ^bO^(c4^+C3⁾ b,(_C +C.) ^b7^(Cl^+C4) ^bl^C4^+b2 · (c₁₊c₀)+b₄lc₃+c₂)'+b₃^(c2^+C0^;

4~3 ΛΙ“ϋ» .S-i-i

TABLE 2

<td> CLOCK</td><td>^do</td><td>^di</td><td>^d2</td><td>^d3</td><td>^d4</td>

<td> CYCLE</td><td></td><td></td><td></td><td></td><td></td>

<td> 6</td><td> b,c.+b 14 2</td><td> b₃(c₂*cp₊</td><td>^bl«=O*=4’ *</td><td>^bi&lt;^co’^H:3^H</td><td>^b0^C3^+bl</td>

<td></td><td> '^cr^co”</td><td>^bo W*</td><td>^b0^(C4^2^,+</td><td>^b4^C2 ⁺</td><td>^(C0^4^&gt;+b3</td>

<td></td><td> b,&lt;^c3«=₂)</td><td>^b4 +</td><td>^b3^Cl^+b4</td><td> b₀(^c44c₃) ₊</td><td> (Gj+ep+bj</td>

<td></td><td> +^b3(c₂.c₀)</td><td>^b2^C0^+C3</td><td> (^c3+c₂) ⁺</td><td>^b2^(cl*^Co’</td><td> (C|+C₄) +</td>

<td></td><td>^+cl^b4</td><td>^(b2^+b?</td><td>^cl‘^b0*^b4’</td><td> ’H=₁(b₀+b₃i</td><td>^c2^b2</td>

<td> 7</td><td>^b0^C3 ⁺</td><td>^bl^C4^+b2</td><td> b₃(c₂+cp +</td><td>^bl^^c0^+C4^⁺</td><td>^bl^(cCT^c2*</td>

<td></td><td>^bl^(c0^+C4^,+</td><td>^(ci^+coJ ⁺</td><td>^b0^&lt;c4^4c3⁾</td><td>^b0&lt;^c4-h=₂) +</td><td>^b4^C2+^b0</td>

<td></td><td> b₃(c₂*cp +</td><td> b^ (c_v+cp +</td><td> b₄ (c₃+cp +</td><td> b₃c₁+b'₄</td><td> &lt;c₄-«c₃)+b₄</td>

<td></td><td>^b2^(Cl^+C4⁾⁺</td><td>^b3 +</td><td>^b2^C0^+C3</td><td> (c₃+c₂) +C^</td><td> (cpcp+c^</td>

<td></td><td> c₂^b2b3</td><td>^Cl^b4 ⁺</td><td> (b₂+bp+c₀</td><td> (^bo^+b4)^+co</td><td> (b₀+b₃)+</td>

<td></td><td></td><td> c₂(bp</td><td> Cb₄+b₃)</td><td> (bpb₂,</td><td>^cl^bl</td>

<td></td><td></td><td>^bo&gt;</td><td></td><td></td><td></td>

<td> 8</td><td>^bl^(c0^+c3&gt;</td><td>^b0^c3</td><td>^bl^C4</td><td> b₃(c₁₊c₂)</td><td></td>

<td></td><td>^+b4^C2</td><td>^bl^|c0^+c4&gt;</td><td>^+b2^(Cl^+Co’</td><td>^b0^(C4«3'</td><td>^boW</td>

<td></td><td>^tbO^|c4*^c3’</td><td>^b3 L^l¹</td><td>^b4(^c3«₂)</td><td> +b₄(c₃+c₁)</td><td>^b3^Cl’^b4</td>

<td></td><td>^b4 (c₃+c₂)</td><td> +b₂(c₁+c₄,</td><td> +b₃(c₂+c₀)+</td><td></td><td>^c0 -^b4 ⁺^2^</td>

<td></td><td></td><td>^C2^b2⁺</td><td> Sl^b4 ⁺</td><td>^(bl^+b2^{) +}</td><td> -*-c.b. 0 0</td>

<td></td><td>^+cl^bl</td><td>^C0^b3^+Cl</td><td>^C2&lt;^bl^+b0’</td><td>^CO^(b3^+b4^{) +}</td><td></td>

<td></td><td>^+c4^b2</td><td>^(b0^+b4&gt;</td><td>^+c4(b₂+b₃)</td><td> c₄ (bp-bp</td><td></td>

WO 88/04805 PCT/US86/02751

<img file="AU625552B2_D0031.tif" />

TABLE 2 CONTINUED

CLOCK _d°0

CYCLE

<img file="AU625552B2_D0032.tif" />

h) c

Ef

Cf&gt;

H

J εζ

H

N

X n

J

<td> 4^0^4¹</td><td> bpc^cp*</td><td>^b0^C3 ⁺</td>

<td>^b0^(c4^+C2^,+</td><td>^b4^C2^+b0</td><td></td>

<td> b₃^ci+</td><td> (c₄+c₃)+</td><td> +b₃ (Cj+cp</td>

<td>^b4 (&lt;=₃+c₂) +</td><td>^b4 ^3^2⁵</td><td>^+b2 t^cl^+c4&gt;</td>

<td>^cl.(b₀+b₄ ) +</td><td>^+cl(^b0⁺b₃)</td><td> +c₉b₉+</td>

<td>^C0^(b4^+b2^,+</td><td>^+Cl^bl^+C4</td><td> W</td>

<td>^co^bo⁺</td><td>^b2«0^&lt;b3 ⁺</td><td> C.(b_n+bj +</td>

^c3^bl ^b4 /' c₃(b₁₊b₂)

<td>^d3</td><td>^d4</td>

<td>^bl^C4</td><td>^b3^(cpc₂)</td>

<td> +b₂(cpc₀)</td><td>^b0 ^4+^3)</td>

<td>^b4^ic3^4c2⁾</td><td> +^b4&lt;^c3+Ci)</td>

<td> +b₃(c₂4c₀)+</td><td>^+b2^co·**^</td>

<td>^cl^b4 ⁺</td><td> (bp-bp+</td>

<td>^c2(^bi₊b₀)</td><td>^C0^ib3^+b4^,+</td>

<td> ♦c, (bp-bp</td><td> c₄ (fop-bp</td>

<td>^c3&lt;^b0^+b2^J</td><td> +c₄b₄</td>

I tc co

I

<td>^b3 ^^ci^+c2^</td><td> 4&lt;c₀+0,)</td>

<td>^b0^,C4^+C3’</td><td>^bo^,c4^&lt;c2’</td>

<td>^+b4 •'a*'?</td><td>^b3^cl⁺</td>

<td>^4b2^c0^+c3</td><td>^b4(c₃+c₂)</td>

<td> (bj+bj).</td><td>^Cl^,bO^+b4&gt;</td>

<td>^c0^&lt;b3^+b4^H</td><td>^CO^,b4^+b2’</td>

<td>^c4^,bl^+b3’</td><td> W</td>

<td>^+C4^b4</td><td>^C3^bl ^c4^&lt;b2^+b3’</td>

b₁(c₀-K:₃) + b ,C_+b~

2 0 ^4+^3,+ ^b4(^c3-H:₂) ^+cl^(b0^+b3’ *W^C4

WV ^b4&gt;

C^bg+b^

<td>^b0^c3⁺</td><td>^bl^C4</td>

<td>^bl^^C0^+C4^</td><td>^+b2^&lt;Cl^+co’</td>

<td> +b₃ (cpp</td><td>^b4 &lt;^c3^2&gt;</td>

<td>^+b2^(cl^+C4&gt;</td><td> +^b3&lt;c_2+Co)+</td>

<td>^+C2^b2⁺</td><td>^Cl^b4 ⁺</td>

<td>^C0^b3 ⁺</td><td>^C2^&lt;bl^+b0&gt;</td>

<td>^cl«^b0^+b4⁾⁺</td><td> ^4^2^3¹</td>

<td>^C3^(bl^+b2’</td><td>^C3^(b0^+b2’</td>

<td></td><td></td>

WO 88/04805 PCT/US86/02751

WO 88/04805

PCT/US86/02751

-29TAfltt 1 η

<td> 2</td><td> -</td><td> ΓΥΡΕ</td><td> 1</td><td> 3</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 6</td><td> -</td><td> rrpe</td><td> 2</td><td> 9</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 1 2</td><td> -</td><td> ttpe</td><td> 1</td><td> 1 4</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 26</td><td> -</td><td> rrpe</td><td> 2</td><td> 2a</td><td> -</td><td> rrpe</td><td> 1</td>

<td> 33</td><td> -</td><td> rrpe</td><td> 2</td><td> 35</td><td> -</td><td> rrpe</td><td> 2</td>

<td> A 1</td><td> -</td><td> Trpe</td><td> 2</td><td> 50</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 53</td><td> -</td><td> Trpe</td><td> 2</td><td> sa</td><td> -</td><td> TYPE</td><td> J</td>

<td> 66</td><td> -</td><td> Trpe</td><td> 1</td><td> 69</td><td></td><td> rrpe</td><td> 2</td>

<td> Β2</td><td> -</td><td> rrpe</td><td> 1</td><td> 03</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 9 0</td><td> -</td><td> rrpe</td><td> 2</td><td> 95</td><td> -</td><td> rrpe</td><td> 2</td>

<td> IQO</td><td> -</td><td> rrpe</td><td> 1</td><td> 105</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 1 19</td><td> -</td><td> rrpe</td><td> 2</td><td> 130</td><td> -</td><td> rrpe</td><td> 1</td>

<td> »35</td><td> -</td><td> rrpe</td><td> 2</td><td> 13fl</td><td> -</td><td> rrpe</td><td> 1</td>

<td> »55</td><td> -</td><td> Trpe</td><td> 2</td><td> 15a</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 173</td><td> -</td><td> type</td><td> 2</td><td> 174</td><td> -</td><td> rrpe</td><td> 2</td>

<td> iao</td><td> -</td><td> Trpe</td><td> 1</td><td> 133</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 19»</td><td> -</td><td> rrpe</td><td> 2</td><td> 194</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 210</td><td> -</td><td> rrpe</td><td> 1</td><td> 221</td><td> -</td><td> Trpe</td><td> 2</td>

<td> 23 1</td><td> -</td><td> rrpe</td><td> 2</td><td> 233</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 24 5</td><td> -</td><td> rrpe</td><td> 2</td><td> 25 1</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 2όβ</td><td> -</td><td> rrpe</td><td> 1</td><td> 270</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 2ai</td><td> -</td><td> Trpe</td><td> 2</td><td> 292</td><td> -</td><td> rrpe</td><td> 1</td>

<td> 303</td><td> -</td><td> rrpe</td><td> 2</td><td> 306</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 323</td><td> -</td><td> ttpc</td><td> 2</td><td> 326</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 333</td><td> -</td><td> rrpe</td><td> 2</td><td> 346</td><td> -</td><td> TYPE</td><td> 1</td>

<td> 35 4</td><td> -</td><td> rrpe</td><td> 2</td><td> 559</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 375</td><td> -</td><td> rrpe</td><td> 2</td><td> 373</td><td> -</td><td> TYPE</td><td> 1</td>

<td> 393</td><td></td><td> rrpe</td><td> 2</td><td> 39a</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 4 »3</td><td> -</td><td> rrpe</td><td> 2</td><td> 4 14</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 420</td><td></td><td> Trpe</td><td> 1</td><td> 426</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 4 3a</td><td> -</td><td> rrpe</td><td> 2</td><td> 44 I</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 453</td><td> -</td><td> Trpe</td><td> 2</td><td> 460</td><td> -</td><td> TYPE</td><td> 1</td>

<td> 473</td><td> -</td><td> rrpe</td><td> 2</td><td> 433</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 495</td><td> -</td><td> TYPE</td><td> 2</td><td> soa</td><td> -</td><td> rrpe</td><td> 1</td>

<td> 5 19</td><td> -</td><td> rrpe</td><td> 2</td><td> 522</td><td> -</td><td> rrpe</td><td> 1</td>

<td> 54Q</td><td> -</td><td> Trpe</td><td> 1</td><td> 543</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 554</td><td> •</td><td> rrpe</td><td> 2</td><td> 556</td><td> -</td><td> rrpe</td><td> 1</td>

<td> 562</td><td> -</td><td> rrpe</td><td> 1</td><td> 575</td><td> -</td><td> Trpe</td><td> 2</td>

<td> 59 5</td><td> -</td><td> rrpe</td><td> 2</td><td> 606</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 6 I 4</td><td> —</td><td> rrpe</td><td> 2</td><td> 6 1 5</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 63a</td><td></td><td> rrpe</td><td> 2</td><td> 639</td><td> -</td><td> Type</td><td> 2</td>

<td> 6 50</td><td></td><td> rrpe</td><td> 2</td><td> 65 1</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 6 5a</td><td> -</td><td> rrpe</td><td> 1</td><td> 6 5 9</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 6</td><td> -</td><td> rrpe</td><td> 1</td><td> 5^:</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 10</td><td> -</td><td> TYPE</td><td> 1</td><td> I 1</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 13</td><td> -</td><td> rrpe</td><td> 1</td><td> 23</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 29</td><td> -</td><td> rrpe</td><td> 2</td><td> 30</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 36</td><td> -</td><td> rrpe</td><td> 1</td><td> 39</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 5 1</td><td> -</td><td> rrpe</td><td> 2</td><td> 52</td><td> -</td><td> rrpe</td><td> 1</td>

<td> 60</td><td></td><td> rrpe</td><td> 1</td><td> 65</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 74</td><td> . -</td><td> rrpe</td><td> 2</td><td> β 1</td><td> -</td><td> TYPE</td><td> 2</td>

<td> ae,</td><td> -</td><td> rrpe</td><td> 2</td><td> 69</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 9a</td><td> -</td><td> rrpe</td><td> 2</td><td> 99</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 106</td><td> -</td><td> rrpe</td><td> 1</td><td> 1 13</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 131</td><td> -</td><td> TYPE</td><td> 2</td><td> 134</td><td> -</td><td> TYPE</td><td> .2</td>

<td> 146</td><td> -</td><td> TYPE</td><td> 2</td><td> 143</td><td> -</td><td> TYPE</td><td> 1</td>

<td> 162</td><td> -</td><td> TYPE</td><td> 1</td><td> 172</td><td> -</td><td> rrpe</td><td> 1</td>

<td> 17a</td><td> -</td><td> TYPE</td><td> 1</td><td> 179</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 136</td><td> -</td><td> TYPE</td><td> 2</td><td> 169</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 196</td><td> -</td><td> TYPE</td><td> 1</td><td> 209</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 226</td><td> -</td><td> rrpe</td><td> 1</td><td> 230</td><td> -</td><td> type</td><td> 2</td>

<td> 239</td><td> -</td><td> TYPE</td><td> 2</td><td> 243</td><td> -</td><td> ΓΥΡΕ</td><td> 2</td>

<td> 254</td><td> -</td><td> TYPE</td><td> 2</td><td> 26 1</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 273</td><td> -</td><td> TYPE</td><td> 2</td><td> 276</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 293</td><td> -</td><td> TYPE</td><td> 2</td><td> 299</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 309</td><td> -</td><td> TYPE</td><td> 2</td><td> 3 16</td><td> -</td><td> rrpe</td><td> 1</td>

<td> 329</td><td> -</td><td> TYPE</td><td> 2</td><td> 330</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 5&lt;a</td><td> -</td><td> TYPE</td><td> 1</td><td> 350</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 371</td><td> -</td><td> TYPE</td><td> 2</td><td> 372</td><td> -</td><td> rrpe</td><td> 1</td>

<td> 366</td><td> -</td><td> TYPE</td><td> 2</td><td> 333</td><td> -</td><td> TYPE</td><td> 1</td>

<td> 4 10</td><td> -</td><td> TYPE</td><td> 2</td><td> 41 1</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 4 ιβ</td><td> -</td><td> TYPE</td><td> 1</td><td> 419</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 429</td><td> -</td><td> rrpe</td><td> 2</td><td> 431</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 442</td><td> -</td><td> rrpe</td><td> 1</td><td> 443</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 466</td><td> -</td><td> rrpe</td><td> 1</td><td> 470</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 490</td><td> -</td><td> rrpe</td><td> 1</td><td> 491</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 509</td><td> -</td><td> rrpe</td><td> 2</td><td> 5 1 5</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 530</td><td> -</td><td> TYPE</td><td> 2</td><td> 531</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 545</td><td> -</td><td> rypE</td><td> 2</td><td> 546</td><td> -</td><td> rrpe</td><td> 1</td>

<td> is a</td><td> -</td><td> rrpe</td><td> 2</td><td> 56 1</td><td> -</td><td> type</td><td> 2</td>

<td> sas</td><td> -</td><td> ttpe</td><td> 2</td><td> 5β6</td><td> -</td><td> ήρε</td><td> 1</td>

<td> 6 1 1</td><td> -</td><td> rrpe</td><td> 2</td><td> 6 1 2</td><td> -</td><td> type</td><td> 1</td>

<td> 6 ia</td><td> -</td><td> type</td><td> 1</td><td> 629</td><td> -</td><td> rrpe</td><td> 2</td>

<td> 64 )</td><td> -</td><td> type</td><td> 2</td><td> 645</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 652</td><td> -</td><td> rrpe</td><td> 1</td><td> 653</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 660</td><td> -</td><td> TYPE</td><td> 1</td><td> 6 76</td><td> -</td><td> TYPE</td><td> 1</td>

I

WO 88/04805

PGT/US86/02751

-30jn «Sai

700

725 746

761 7 74 766 ao9 826 854

666 679 9Q6 933 940 965 909

14 103 I 1049 1070 1106 1» 19 1134 1 166 1)05 1211 1226 1230 1269 1276 1290 13 10 1 3 30 1 353 1372 140 1 1425 14 43

1.4 5 4 143 1 Γ4 9 9 .15 10 15 3 9

7 0

TYPE 2 τυγε i TYPE 2 type 2 TYPE' 2 ΓΥΡΕ 2. ΓΥΡΕ 1* TYPE 2 TYPE 1 TYPE 2 TYPE 2 TYPE 2 TYPE 1 TYPE 2 TYPE 1 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 ΓΥΡΕ 1 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 1 TYPE 2 TYPE 2 TYPE 1 TYPE 1 TYPE 2 TYPE 2 TYPE 2 Type i Type 2 TYPE 2 Type 2 TYPE 2 TYPE 2 TrPE 2 TYPE 2 TYPE 2 TYPE 1 m

666

713 726

4 9

765 779 79 1 610 626

646

070 002 '

911 935 946 974

993 1010 1034· 1055 '&gt; 1090 “

1110 1121 1146 1169 1106 1212 1229 1251 1271 &gt;

1276 1295 1323 134 1 1 355 1360 1409 1426 14S0 1463 1462 1 505 1 522 154 1 1563 ryfE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 1 TYPE 2 TYPE 2 TYPE 1 TYPE 2 TYPE 2 TYPE 1 TYPE 2 TYPE 2 TYPE 1 TYPE 2 TYPE 2 TYPE 1 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 1 TYPE 1 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 1 TYPE. 2 TYPE 1 TYPE 1 TYPE 2 TYPE 1 TYPE 2 TYPE 1 TYPE 2 type 2 m

690

19 74 1

755 77 1 703 796 010 031 052 073 091 923 930 950 975 990 .1019 1041 1060 1103 1116 1122 1154 1170 1194 1210 1233 1250 1274 1202 1300 1329 1346 1359 1394 1410 1430 14 5, 1469 1492 1 509 1 53Q 1 546 1593

TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 1 TYPE 2 TYPE 2 TYPE 1 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 1 TYPE 2 TYPE 1 TYPE 1 TYPE 2 TYPE 1 TYPE 2 TYPE 2 TYPE 2 TYPE 1 TYPE 2 TYPE 1 TYPE 1 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 1 TYPE 2 TYPE 1 TYPE 1 TYPE 2 • m·

700 723 743 756 772 705

003 020 033 050 076 093 930 939 953 906 1013 1026 1043 1065 1 106 1110 1133 1155 1170 1199 1223 1236 1265 1275 1209 1306 1331 1349 1370 1396 1421 1439 1452 1476 1496 .15 11 1 533 1 559 160 1

TYPE 1 TYPE 2 TYPE 2 TYPE 1 TYPE 1 TYPE 2 TYPE 2 TYPE 1 TYPE 2 TYPE 1 TYPE 1 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE 1 TYPE 2 TYPE 2 TYPE 2 TYPE 1 TYPE 2 TYPE 2 TYPE 2 TYPE 2 TYPE TYPE

TYPE 1 TYPE 2 TYPE 1 TYPE 2 TYPE 2 TYPE 2 TYPE 2 • WO 88/04805

PCT/US86/02751

-31π&gt; · ra jn m

<td> i6 ι a</td><td> -</td><td> type</td><td> I</td><td> 1620</td><td> -</td><td> TYPE</td><td> 1</td><td> 1626</td><td> -</td><td> TYPE</td><td> 2</td><td> 1636</td><td> -</td><td> TYPE</td><td> 1</td>

<td> 1649</td><td> -</td><td> TYPE</td><td> 2</td><td> 1653</td><td> -</td><td> TYP E</td><td> 2</td><td> 1659</td><td> -</td><td> TYPE</td><td> 2</td><td> 166 1</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 1666</td><td> -</td><td> type</td><td> 1</td><td> 1660</td><td> -</td><td> TYPE</td><td> 1</td><td> 167 3</td><td> -</td><td> TYPE</td><td> 2</td><td> 1679</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 1605</td><td> -</td><td> ΓΥΡΕ</td><td> 2</td><td> 1692</td><td> -</td><td> TYPE</td><td> 1</td><td> 1 703</td><td> -</td><td> TYPE</td><td> 2</td><td> 1 7Q6</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 1 730</td><td> -</td><td> Type</td><td> 2</td><td> 1732</td><td> -</td><td> TYPE</td><td> 1</td><td> 1733</td><td> -</td><td> TYPE</td><td> 2</td><td> 1734</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 1 740</td><td> -</td><td> type</td><td> 1.</td><td> 1745</td><td> -</td><td> TYPE</td><td> 2</td><td> 1746</td><td> -</td><td> TYPE</td><td> 1</td><td> 1 749</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 1755</td><td> -</td><td> type</td><td> 2</td><td> 1750</td><td> -</td><td> TYPE</td><td> 2</td><td> 1763</td><td> -</td><td> TYPE</td><td> 2</td><td> 1766</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 1 769</td><td> -</td><td> TYPE</td><td> 2</td><td> 1773</td><td> -</td><td> TYPE</td><td> 2</td><td> 1 770</td><td> -</td><td> TYPE</td><td> 2</td><td> 1779</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 1 705</td><td> -</td><td> TYPE</td><td> 2</td><td> 1706</td><td> -</td><td> TYPE</td><td> 1</td><td> 1 790</td><td> -</td><td> TYPE</td><td> 2</td><td> 1 79 1</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 1 006</td><td> -</td><td> TYPE</td><td> 2</td><td> 10 11</td><td> -</td><td> ΓΥΡΕ</td><td> 2</td><td> 10 10</td><td> -</td><td> TYPE</td><td> 2</td><td> 102 1</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 1029</td><td> -</td><td> TYPE</td><td> 2</td><td> 1035</td><td> -</td><td> TYPE</td><td> 2</td><td> 1030</td><td> -</td><td> TYPE</td><td> 2</td><td> 1045</td><td> •</td><td> TYPE</td><td> 2'</td>

<td> 1050</td><td> -</td><td> TYPE</td><td> 2</td><td> 1054</td><td> -</td><td> TYPE</td><td> 2</td><td> 1059</td><td> -</td><td> TYPE</td><td> 2</td><td> 1 060</td><td> -</td><td> TYPE</td><td> 1</td>

<td> 1063</td><td> -</td><td> TYPE</td><td> 2</td><td> 1 066</td><td> -</td><td> TYPE</td><td> 1</td><td> 1076</td><td> -</td><td> TYPE</td><td> 1</td><td> 1003</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 1009</td><td> -</td><td> TYPE</td><td> 2</td><td> 1 090</td><td> -</td><td> TYPE</td><td> 2</td><td> 1900</td><td> -</td><td> ΓΥΡΕ</td><td> 1</td><td> 1901</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 1 906</td><td> -</td><td> TYPE</td><td> 1</td><td> 1 923</td><td> -</td><td> TYPE</td><td> 2</td><td> 1925</td><td> -</td><td> TYPE</td><td> 2</td><td> 1926</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 1930</td><td> -</td><td> TYPE</td><td> 1</td><td> 193 1</td><td> -</td><td> TYPE</td><td> 2</td><td> 1930</td><td> -</td><td> TYPE</td><td> 2</td><td> 1940</td><td> -</td><td> TYPE</td><td> 1</td>

<td> 1953</td><td> -</td><td> TYPE</td><td> 2</td><td> 1955</td><td> -</td><td> TYPE</td><td> 2</td><td> 1950</td><td> -</td><td> TYPE</td><td> 2</td><td> 1959</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 1 96 1</td><td> -</td><td> TYPE</td><td> 2</td><td> 1965</td><td> -</td><td> TYPE</td><td> 2</td><td> 1972</td><td> -</td><td> ΓΥΡΕ</td><td> 1</td><td> 1973</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 1970</td><td></td><td> TYPE</td><td> 1</td><td> 1 903</td><td> -</td><td> TYPE</td><td> 2</td><td> 1906</td><td> -</td><td> TYPE</td><td> 1</td><td> 1994</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 1996</td><td> -</td><td> TYPE</td><td> 1</td><td> 200 1 &gt;</td><td> -</td><td> TYPE</td><td> 2</td><td> 2003</td><td> -</td><td> TYPE</td><td> 2</td><td> 2006</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 2009</td><td> -</td><td> TYPE</td><td> 2</td><td> 2010</td><td> -</td><td> TYPE</td><td> 2</td><td> 2026</td><td> -</td><td> TYPE</td><td> 1</td><td> 2020</td><td> -</td><td> TYPE</td><td> 1</td>

<td> 2039</td><td> -</td><td> TYPE</td><td> 2</td><td> 204 5</td><td> -</td><td> TYPE</td><td> 2</td><td> 2046</td><td> *»</td><td> TYPE</td><td> 2</td><td> 2049</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 2052</td><td> -</td><td> TYPE</td><td> 1</td><td> 2055</td><td> -</td><td> TYPE</td><td> 2</td><td> 2063</td><td> -</td><td> TYPE</td><td> 2</td><td> 2066</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 2060</td><td></td><td> TYPE</td><td> 1</td><td> 2069</td><td> -</td><td> TYPE</td><td> 2</td><td> 2070</td><td> -</td><td> TYPE</td><td> 2</td><td> 2079</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 2002</td><td> -</td><td> TYPE</td><td> 1</td><td> 2090</td><td> -</td><td> TYPE</td><td> 1</td><td> 2109</td><td> -</td><td> ΓΥΡΕ</td><td> 2</td><td> 2114</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 2115</td><td> -</td><td> TYPE</td><td> 2</td><td> 2 12 1</td><td> -</td><td> TYPE</td><td> 2</td><td> 2126</td><td> -</td><td> TYPE</td><td> 2</td><td> 2129</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 2 130</td><td> -</td><td> TYPE</td><td> 1</td><td> 2 140</td><td> -</td><td> TYPE</td><td> 1</td><td> 2141</td><td> -</td><td> TYPE</td><td> 2</td><td> 2163</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 2 174</td><td> —</td><td> TYPE</td><td> 2</td><td> 2170</td><td> -</td><td> TYPE</td><td> 2</td><td> 2101</td><td> -</td><td> TYPE</td><td> 2</td><td> 2106</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 2195</td><td> -</td><td> TYPE</td><td> 2</td><td> 2 190</td><td> -</td><td> TYPE</td><td> 2</td><td> 2212</td><td> -</td><td> TYPE</td><td> 1</td><td> 2220</td><td> -</td><td> TYPE</td><td> 1</td>

<td> 2223</td><td> -</td><td> TYPE</td><td> 2</td><td> 2225</td><td> r</td><td> TYPE</td><td> 2</td><td> 2231</td><td> -</td><td> TYPE</td><td> 2</td><td> 2236</td><td> -</td><td> TYPE</td><td> 1</td>

<td> 224 1</td><td> -</td><td> TYPE</td><td> 2</td><td> 2242</td><td> -</td><td> TYPE</td><td> 1</td><td> 2246</td><td> -</td><td> TYPE</td><td> 2</td><td> 2253</td><td></td><td> TYPE</td><td> 2</td>

<td> 22 5 0</td><td> -</td><td> TYPE</td><td> 2</td><td> 2266</td><td> -</td><td> TYPE</td><td> 1</td><td> 2260</td><td> -</td><td> TYPE</td><td> 1</td><td> 2273</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 229 1</td><td> -</td><td> TYPE</td><td> 2</td><td> 2292</td><td> -</td><td> TYPE</td><td> 1</td><td> 2295</td><td> -</td><td> TYPE</td><td> 2</td><td> 2301</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 2300</td><td> -</td><td> TYPE</td><td> 1</td><td> 23 10</td><td> -</td><td> TYPE</td><td> 2</td><td> 23 10</td><td> -</td><td> TYPE</td><td> 2</td><td> 2319</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 2332</td><td> -</td><td> TYPE</td><td> 1</td><td> 2330</td><td> -</td><td> TYPE</td><td> 1</td><td> 2339</td><td> -</td><td> TYPE</td><td> 2</td><td> 2345</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 235 1</td><td> :-</td><td> TYPE</td><td> 2</td><td> 2356</td><td> -</td><td> TYPE</td><td> 1</td><td> 2361</td><td> -</td><td> TYPE</td><td> 2</td><td> 2370</td><td> -</td><td> TYPE</td><td> 1</td>

<td> 2300</td><td> -</td><td> TYPE</td><td> 1</td><td> 239 1</td><td> -</td><td> TYPE</td><td> 2</td><td> 2393</td><td> -</td><td> TYPE</td><td> 2</td><td> 2394</td><td> -</td><td> TYPE</td><td> 2</td>

<td> 2399</td><td> -</td><td> TYPE</td><td> 2</td><td> • 2406</td><td> -</td><td> TYPE</td><td> 2</td><td> 2415</td><td> -</td><td> TYPE</td><td> 2</td><td> 2436</td><td> -</td><td> TYPE</td><td> 1'</td>

<td> 2430</td><td> -</td><td> TYPE</td><td> 2</td><td> 245 1</td><td> -</td><td> TYPE</td><td> 2</td><td> 2450</td><td> -</td><td> TYPE</td><td> 1</td><td> 2459</td><td> - .</td><td> TYPE</td><td> 2</td>

<td> 2466</td><td> —</td><td> TYPE</td><td> 1</td><td> 247 1</td><td> -</td><td> TYPE</td><td> 2</td><td> 2475</td><td> -</td><td> TYPE</td><td> 2</td><td> 2476</td><td> -</td><td> TYPE</td><td> 1</td>

<td> 2478</td><td> •</td><td> TYPE</td><td> 2</td><td> 2403</td><td> -</td><td> TYPE</td><td> 2</td><td> 2406</td><td> -</td><td> TYPE</td><td> 2</td><td> 2493</td><td> -</td><td> TYPE</td><td> 2</td>

* ’5?&lt;5τιτ·ι ιτετ eurrr.

PCT/US86/02751

WO 88/04805

-3 2APPENDIX I

<img file="AU625552B2_D0033.tif" />

<td> 1include</td><td> &lt; s t d i o . h &gt;</td><td></td><td></td><td></td><td></td>

<td> βde( i ne 8 de f i ne 9 de i i ne 8 de f i n e</td><td> MA&gt; N MAXN 32 UOKD HE X8 (uns</td><td> 2 5 60 80 32 igned) 0X80000000</td><td> / « / » / ·</td><td colspan="2"> maximum field degree array width « / word size in b i t a · / / χ most sig bit in</td>

<td> 8 de f i ne</td><td> HE X4</td><td> 0X40000000</td><td> / «</td><td> second most</td><td> word sig bit a wo rd</td>

<td> 8de f i ne 8 de f i ne</td><td> ONE ALl-ONE</td><td> 01 0 X F F F F F F F F</td><td> / * / *</td><td> least sig bi alt ones vec</td><td> t (octal) tor * /</td>

«/ a

» / i n « / * / int N' int N32;

unsigned poIyCMAXN32 li ma i n( argoargv ) int a rgc; char « a r gvC]» &lt;

Program to compute the coefficients b and c of an optimal multiply equation for digit dQ of product vector D = B « C where B,C, and 0 are the normal basis representations of.elements in the Galois Field GF(2*»m).

Source Language : C under UNIX 0/S

Author : Ivan M. Onyszchuk

Date Last Modified : May 24/ 1935 2:04 am

Modification : Documentation added

Execution &lt;programname&gt; m type

Kesult : dQ multiply equation, 2m-1 pairs of coefficients b and c. IF an invalid value of m or type is entered/ an error message is printed.

*/

V ι

I

WO 88/04805 PCT/US86/0275!

-3 3-

<td> /ft</td><td colspan="2"> variable declarations</td><td> « /</td>

<td> u n s</td><td> i g η b d</td><td> «BPC ΓΙΑΧΝ 3;</td><td></td>

<td> uns</td><td> i gned</td><td> «ΟΡΕ I1AXN 3)</td><td></td>

<td> u n s</td><td> igned</td><td> ’ Β I C (1A X N 3 ;</td><td></td>

<td> uns</td><td> i gned</td><td> mask)</td><td></td>

<td> i n t</td><td colspan="2"> terras/ out/ o u t 1 / b /</td><td></td>

<td> i n t</td><td> t ype</td><td></td><td></td>

<td> uns</td><td> igned</td><td> »swap/</td><td></td>

<td> reg</td><td> i s t e r</td><td> int i )</td><td></td>

<td> rc Q</td><td> i a ter</td><td> int j )</td><td></td>

<td> reg</td><td> ister</td><td> int k</td><td></td>

<td> re g</td><td> i a t e r</td><td> int I /</td><td></td>

<td> i n t</td><td> t 1/</td><td> t2)</td><td></td>

<td> reg</td><td> i s t e r</td><td> unsigned «bp/ »«bl/</td><td> « « b 2 /</td>

<td> reg</td><td> i s t e r</td><td> unsigned «dp/ « b 3 / «</td><td> b 4 /</td>

<td> reg</td><td> i s ter</td><td> unsigned temp/ terap2</td><td> z</td>

<td> uns</td><td> igned</td><td> beta1CMAXN323/’</td><td></td>

<td> uns</td><td> igned</td><td> beta2C(1AXN323/'</td><td></td>

<td> uns</td><td> igned</td><td> oneC(lAXN323/’</td><td></td>

<td> uns</td><td> Igned</td><td> twoC MAXN 32 3)</td><td></td>

<td> /«</td><td colspan="2"> Read in value of m and</td><td> type</td>

Ν = atci (argvC13)) type = atoi ( a r g v C 2 3 ) &lt;’

N32 = ( N - 1 ) / WORD + 1;

for (i = o; i &lt; = N32; i+t) polyCi3 = oneCi3 = twoCi3 = beta1Ci3 = 0;

Compute generating polynomial » / if (( type ! = 1 ) &amp; &amp; ( type != 2)) goto next) i f &lt; t ype == 2 ) &lt;

’two = HExa;

’one = HEX8 ! HEX4) for(i=i;i&lt;N)i++)&lt;

•poly = «two ^A («one &gt;&gt; 1 );

lor(j=o;j&lt;N32;j+t)

POIyC j 3 = twot j 3 ^A ((oneCj-13 δ ONE) ?

(oneC j 3 &gt; &gt; 1 : HE Xti ) _: | (oneCj3 &gt;&gt;!)))

TOTS SHEET

WO 88/04805 PCT/US86/02751

-34tor (j=D; j &lt; N32/ j++) &lt;

t woC j 3 = oneC j 3/ ο n « C j 3 - ρ ο I y C j 3;

&gt;

&gt;

&gt;

<td> i f (</td><td> type -= 1 ) &lt;</td><td></td><td></td><td></td>

<td></td><td> f o r ( j = 1 /' j</td><td> &lt; N 3 2 /' j + ♦ )</td><td></td><td></td>

<td></td><td> ρο I yCj- 1 '</td><td> 3 = allone;</td><td></td><td></td>

<td></td><td> ροIyC N 3 2 - 1 3 =</td><td> 0X3000000(3 ?&gt; (</td><td> N ’</td><td> WORD );</td>

<td> &gt;</td><td></td><td></td><td></td><td></td>

<td> for</td><td> ( i = o; i &lt; n;</td><td> i ♦ t ) (</td><td></td><td></td>

<td> BPC ί</td><td> i 3</td><td> = funs i ailed</td><td> « )</td><td> cat Ioc</td><td> ( N32z</td><td> s i xeofC u n s igned ) ) /'</td>

<td> DPC i</td><td> ί 3</td><td> = (unsigned</td><td> « )</td><td> Cat I o c</td><td> C N32z</td><td> s i zeofC uns igned ) );</td>

<td> BIC i</td><td> i 3</td><td> = (unsigned</td><td> * )</td><td> cal Io c</td><td> ( N32z</td><td> s i zeofC uns igned ) )/'</td>

for ( i = Ο; i &lt; N 32 i ·» + ) &lt; «(beta! + i ) = 0;

* ( be t a 2 + i ) = 0 z &gt;

«betal = HEX43

Construct matrices for η οiu s I basis « / for ( i = Oz bp - «BP; i &lt; N 32/ i ♦ + / bp + + ) «bp = «( ba t a 1 t i &gt;;

multi (betel/ b e t a 1 z «DP);

for li = 1; i &lt; N; &gt;♦τ ) { mult2 (BPCi-13/ BPCi-13/ BPCi 3 )) mult2 (BPC03/ BP£ ' 3z QPCi3&gt;;

&gt;

for ( i = □; i &lt; n; for (j = o; j

BIC i 3C j 3 BIC i 3Ci/UORD 3 &gt;

<td colspan="2"> i * + ) (</td>

<td> &lt; N32; = o;</td><td> j ++ )</td>

<td> = h e x a</td><td> &gt; &gt; ( i ·/. WORD);</td>

t

.....ci t.bjctiti itc........currt (5

WO 83/04805

PCT/US86/02751

-35Ga u«9i an eIίIn·t i on «ec 11on .· « / for ( i - 0' i N. i tt ) ί if &lt;(*&lt;BPCi3 + i / UORO) &lt;&lt; i X UORO &amp; HEXS) = = 0 ) f o r ( j = i t 1; j &lt; n; jtt) if C«&lt;BPCj3 + i / WORD) &lt;&lt; i X WORD 4 HEXS) &lt;

swap = BPC i 3;

BPC i 3 = BPC j 3;

BPC j 3 = swap, swap = ΒIC i 3r BIC i 3 = B I C j 3;

B IC j 3 = swap; break/ if ( ( «( BPC i 3' t i / WORD) &lt;&lt; i 7. WORD &amp; HEXS) == 0) &lt; p r i n t f( Error - Matrix is not invertible! \n ); goto next;

&gt;

for (j = i t 1; i &lt; N; jtt) if ( «(BPC j 3 t ΐ f WORD J &lt;&lt; i 7. WORD &amp; HEXS) &lt;

lor (k = 5 / UORO; k &lt;N32; ktt) *( SPC j 3 + k ) ^Λ= *( BPC i 3 t k );

For ( k - 0; k &lt; N32; ktt ) *C etC j 3 t k) »(BlCi3 t k);

&gt;

&lt; o r ( i = 0; i &lt; N; i t + ) for(j=i-i;j&gt;=o;j--) if ( *( BPC j 3 t i / UORO ) &lt;&lt; i 7.

WORD &amp; HEXS) { for (k = i / word; k &lt; N32; ktt )

BPC j3 t k) -= w(BPCi 3 + k);

for (k = 0; k &lt; N32; ktt) ’(BICj3 t k) ^Λ = - ( Β IC i 3 t k ) ;

Perform matrix transpose for ( i

0, bi =

BI; i &lt; N; i t +, b11 + ) for (j = 0, b2 = Bi; j &lt; i; j + t, b2t+) &lt;

temp = ( ( «b 1 )C j/WORD 3 &lt; &lt; (j X WORD)) .4 HEXS, t e p &gt; &gt; = i 7. WORD;

te«p2 = ( &lt; «b2 )C i/WORD 3 &lt;&lt; (i X WORD)) 4 HEXI teep2 &gt;&gt;= j 7. WORD;

( «bi )C j/UORO 3 = &lt; ( «b1 )C )/WORD 3 4 ’(HEXS &gt;&gt; j XUORO ) ) ! t e«p2;

&lt; «b2 )C i/UORO 3 = ( ( »b2 )C i/WORD 3 4 '(HEXS &gt;&gt;

&gt; (XUORO)) ! temp;

ΠΤΙΪΤΕ SHEET

WO 88/04805

PCT/US86/02751

<td> prInt f(\n</td><td> Product</td><td> digit dO multiply \n</td><td> );</td>

<td colspan="2"> p r In t 1(. equation</td><td> coefficients \η\n ) /</td><td></td>

<td> p ri n t 1 ( </td><td> b</td><td> c \n \n )z</td><td></td>

<td> print? (\n</td><td> XAd</td><td> ,XAd \nz N-1z N-1</td><td></td>

<td> Compute..and</td><td> print ο u</td><td> t bz c coefficients</td><td> «/</td>

<td> for ( 1 = 0 z</td><td> b 1 = DP</td><td> ; ι &lt; n ; ι + +, b i + + ) &lt;</td><td></td>

<td> for ( J</td><td> = Oz b2</td><td colspan="2"> - ui; j &lt; ι; j+ + z b2++ ) &lt;</td>

o u t = 0 f for, (k =(). b3 = «b1z bA = »b2z' k &lt;

out ^Aon t 1 = 0;

f ο· p ( k = U z out 1 ^A *b3 t, * b A

K &lt; word; kf+z out it 1;

out &gt; &gt; = 1 ) next: z' &gt;

( ou t 1 ) &lt;

t 1 = ( N i 2 - ( N + print? ( print/ ( j ) x n; i -. j ) x n ;

XAd

XAd

XAd \nz XAd \n, t 1 z t2z t2 ); t 1 )/· /· Element multiply subroutine »/ mul t 2( azbzC ) unsigned * a z »bz « c (

<td> re g 1</td><td> a t e r</td><td> int 1 ;</td><td></td>

<td> reel</td><td> s ter</td><td> Int j :</td><td></td>

<td> r e g 1</td><td> s ter</td><td> unsigned * e t</td><td></td>

<td> uni 1</td><td> gn e d</td><td> EC MAXN32 3)</td><td></td>

<td> un « 1</td><td> gn e d</td><td> FCMAXN32 J;</td><td></td>

<td colspan="2"> uns i on e d</td><td> feed:</td><td></td>

<td> for</td><td> ( i =</td><td> □ z e = E z i &lt;</td><td> N 3 2 z 1+ + , e + + , a + + z b+ + , c + +)</td>

<td></td><td> »e =</td><td> « b z</td><td></td>

<td></td><td> ·( F</td><td> ♦ 1 ) = «a z</td><td></td>

<td> )</td><td> »c =</td><td> o;</td><td></td>

<td> for</td><td> ( 1 =</td><td> 0 z‘ 1 &lt; N; i + +</td><td> ) (</td>

<td></td><td> 1 f (</td><td> ·( F + I /WORD )</td><td> &lt;&lt; 1 X WORD &amp; HEX8 )</td>

<td></td><td></td><td> for ( J = 0, _t</td><td> -= N 3 2 z e = E z J &lt; N 3 2 /' J++,</td>

<td></td><td></td><td></td><td> C++, e++)</td>

<td></td><td></td><td> * c ^A = « e :</td><td></td>

<td> feed</td><td> = «(</td><td> e = E + (N-1 )/</td><td> WORD) &lt;&lt; ((N - 1) X WORD)</td>

<td> for</td><td> &lt; j =</td><td> N 3 2 - 1; J &gt; o</td><td> &amp; HExa; z J-^-, e — )</td>

<td></td><td> « e =</td><td> ( ( « e &gt; &gt; 1)1((</td><td> *(e-1) a ONE) &lt;&lt; WORO~1))^Z'(</td>

<td> &gt;</td><td> * e </td><td> = ( * o &gt; &gt; 1 ) Λ (</td><td> feed ? po I yC j 3 : Q ); feed ? *poly ; Q ) ;</td>

I iv

I

C! IRGtTSTI

<img file="AU625552B2_D0034.tif" />

PCT/us 86/0275137 °4 JAN 1983

<img file="AU625552B2_D0035.tif" />