Method and Apparatus for Performing Hashing Operations using Galois Field Multiplication
The invention comprises a method and apparatus for performing a hashing operation on an N bit number under control of a prespecified N bit hashing constant which comprises performing N/K finite field partial multiplications of the object to be hashed by the hashing constant, utilizing K logic and combinatorial circuits all of which operate in parallel to completely evaluate the number in N/K operations.
Another feature of the present invention is that the hashing constant loaded into the system may be changed at will with a resultant changing of the hashing characteristics to suit a particular class of objects to be hashed. This is done by a "select" operation. In the "select" operation, the hashing constant is sequentially loaded into said K logic and combinatorial circuits, each of which comprises a feedback shift register (FSR), said feedback shift registers being so configured that at the end of K operational sequences each of said feedback shift registers contains said hashing constant shifted and permuted in accordance with the particular feedback configuration of said register, a number of bits proportional to its location in the sequence of feedback shift registers, such that the hashing constant in the shift register FSRi will be shifted in a predetermined direction (i-1) N/K bit positions. Each of the operational sequences referred to above comprises a hashing sequence which includes N/K shifts of the feedback shift registers.
J. L. Carter et al., "Method and Apparatus for Performing Hashing Operations using Galois Field Multiplication," U.S. Patents, International Business Machines Corporation, Aug 1985.
International Business Machines Corporation
Keywords and Phrases
Computing; Calculating; Counting; Electrical digital data processing
Patent Application Number
© 1985 International Business Machines Corporation, All rights reserved.