Polynomial hashing

Details Polynomial hashing Polynomial hashing

1983-12-30

1986-05-13

Roskoski, Bernard

Communications: electrical

Audible indication

Percussion-type sound producer

H03M 700

Patent

active

045889856

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.

REFERENCES:
patent: 4295124 (1981-10-01), Roybal
New Hash Functions and Their Use in Authentication and Set Equality, by Mark N. Wegman and J. Lawrence Carter, Journal of Computer and System Sciences, vol. 22, No. 3, Jun. 1981.
Universal Classes of Hash Functions, by J. Lawrence Carter and Mark N. Wegman, Journal of Computer and System Sciences, vol. 18, No. 2, Apr. 1979.

Affiliated with

Also associated with

Rating

Polynomial hashing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Polynomial hashing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial hashing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1772752