Patent ID: 8363825

Claim:
A device for collision-free hashing for near-match inputs, comprising: a) an adder, having a first input for receiving a user-definable value i representing a bit length of an input, having a second input for receiving a user-definable value cv representing a bit length of a check value, and having an output at which appears a value n that is greater than or equal to the sum of i and cv; b) a checker, having a first input connected to the output of the adder, having a second input for receiving a user-definable value d representing the number of bits between an input to be hashed and a subsequent input to be hashed that must differ before a collision can occur, having a third input for receiving a user-definable first polynomial for a cyclic code, and an output at which the first polynomial appears if the checker determines that the first polynomial is of degree proportional to d and divides x n +1; c) a factorization block for factoring the first polynomial into a second polynomial and a third polynomial, if possible, having an input connected to the output of the checker, having a first output at which appears the second polynomial, if any, and having a second output at which appears the third polynomial if any; d) a first division block for dividing an input of bit length i by the second polynomial to generate a first portion of the hash of the input, having a first input connected to the first output of the factorization block, having a second input for receiving the input, and having an output at which the first portion of the hash of the input appears; and e) a second division block for dividing the input by the third polynomial to generate a second portion of the hash of the input, having a first input connected to the second output of the factorization block, having a second input for receiving the input, and having an output at which the second portion of the hash of the input appears.