Methods and apparatus for modular reduction circuits

A method for reducing a binary key having a plurality of bits into a binary residue, the method comprising:

• segmenting the binary keys in a plurality of partitions having first and second portions;
• routing the plurality of partitions based on a polynomial expression;
• retrieving precomputed values stored in a table indexed by the first portion of partitions;
• and
• summing the second portion of partitions and retrieved precomputed values to sum terms of the polynomial expression to form the binary residue.

A modular reduction circuit for reducing a binary key having a plurality of bits into a binary residue, the circuit comprising:

• means for segmenting the binary keys in a plurality of partitions having first and second portions based on a polynomial expression;
• means for retrieving precomputed values stored in a table indexed by the first portion of partitions;
• and
• means for summing the bits of the second portion of partitions and retrieved precomputed values to form the binary residue.

A high differential modular reduction circuit to reduce a key having a plurality of bits to a residue, the circuit comprising:

• a distributor for receiving a binary key, the distributor partitions the plurality of bits into a plurality of segments;
• one or more modular reduction circuits, each of the one or more modular reduction circuits receives one of the plurality of segments, respectively, each of the one or more modular reduction circuits reducing the plurality of segments, respectively, each of the one or more modular reduction circuits outputting a plurality of intermediate residues, the plurality of intermediate residues having a first and second portion;
• one or more lookup tables receiving the first portion, the one or more lookup tables containing precomputed values, one or more lookup tables outputting the precomputed values to a plurality of bit streams based on a polynomial expression;
• a plurality of compressors for compressing the plurality of bit streams by adding bits in the same position across the plurality of bit streams to result in at least two bits for each bit position found in the plurality of bit streams;
• each of the resulting at least two bits for each bit position are outputted to at least two compressor output streams;
• and
• a final adder for summing the at least two compressor output streams.