Apparatus performing modulo p addition, where operands are expressed as powers of a generator, using a reduced size zech look-up table

Claim 1

Apparatus for generating a representation module p-1 of the power index i to which a generator g has to be raised to give the value X+Y in modulo p arithmetic in response to the application to said apparatus of representations modulo p-1 of x, where g x =X, and y, were g y =Y, which apparatus has first and second inputs for the representations of X and Y, respectively, and an output for the representation of i and comprises (a) a subtractor circuit, having (i) first and second inputs coupled to the first and second inputs, respectively, of the apparatus, and (ii) an output, at which the subtractor circuit generates a representation module p-1 of x-y, (b) a look-up table circuit having (i) an input coupled to the output of the subtractor circuit, and (ii) an output at which the look-up table circuit generates a representation modulo p-1 of the power index j to which g has to be raised to give the value g k +l in modulo p arithmetic in response to the application to said input of a representation modulo p-1 of any member of a set of values k, and (c) an adder circuit having (i) first and second inputs to which are coupled the second input of the apparatus and the output of the look-up table circuit, respectively, and (ii) an output at which the adder generates a representation modulo p-1 of m+j in response to the application to the first and second inputs of the adder circuit of residue representations modulo p-1 of m and j, respectively, which output constitutes the output of the apparatus, wherein the improvement comprises: (d) a multiplexer circuit having (i) a first multiplexer input, (ii) a second multiplexer input, (iii) a control input, and (iv) a multiplexer output, which multiplexer circuit, in response to a control signal to said control input, couples either the first multiplexer input to the multiplexer output or the second multiplexer input to the multiplexer output, the first multiplexer input being coupled to the first input of the apparatus and the coupling from the second input of the apparatus to the first input of the adder circuit being though said multiplexer circuit from the second multiplexer input to the multiplexer output, (e) a converter circuit, coupled between the output of the subtractor circuit and the input of the look-up table circuit, for converting each representation of at least one specific value x-y generated by the subtractor circuit to a representation modulo p-1 of y-x, and (f) means, coupled between the output of the subtractor circuit and the control input of the multiplexer circuit, for supplying a control signal to the multiplexer circuit to cause the multiplexer circuit to couple its first input to its output in response at least tot he presence at the subtractor circuit output of any representation which will be so converted by the converter circuit.