Polynomial hashing
US4588985A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Dec 30, 1983 |
| Grant date | May 13, 1986 |
| Priority date | — |
| Expiry date | Dec 30, 2003 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/9014
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Elements x in a domain A are hashed into a range B by selecting any one of a plurality of hashing functions which collectively form an almost universal.sub.2 class of functions. The data element to be hashed is separated into individual sub-strings x.sub.1 through x.sub.n of no more than log.sub.2 (b) bits in length, where b is an integer, and the hashing algorithm is a polynomial of the form f.sub.y (x)=(y.sup.0 x.sub.1 +y.sup.1 x.sub.2 + . . . +y.sup.n-1 x.sub.n) (mod b). In general, for a finite field of b=p.sup.k elements, where k is a positive integer, there will be a hash function defined by the formula f.sub.y (x)=y.sup.0 x.sub.1 +y.sup.1 x.sub.2 + . . . +y.sup.n-1 x.sub.n, where the addition and multiplication operations are those defined by the finite field and y is an element of the field. In a second embodiment, the hashing is a two-stage process defined by g.sub.z (f.sub.y (x)), where f.sub.y (x) is defined as above and g.sub.z is a function selected from a known universal.sub.2 class of hash functions.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.