EP0149067A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Polynomial hash
Assignee: International Business Machines Corp
•
Filing: 1984-11-27
•
Granted: —
•
Expires: 2004-11-27
Abstract
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" class of functions. The data element to be hashed is separated into individual sub-strings x 1 through x n of no more than log 2 (b) bits in length, where b is an integer, and the hashing algorithm is a polynomial of the form f Y (x) = (y°x 1 + y 1 x 2 + ..... + y n-1 x n ) (mod b). In general, for a finite field of b = p k elements, where k is a positive integer, there will be a hash function defined by the formula f y (x) = y°x 1 + y 1 x 2 + .... + y n-1 x 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 z (fy(x)), where f y (x) is defined as above and g z is a function selected from a known "universal 2 " class of hash functions.
Inventors
- 👤 John L. Carter
- 👤 Mark N. Wegman
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-06 04:52
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0864; G06F16/00; G06F16/90; G06F16/901; G06F16/9014
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
102 words
A method of compressing an input data word x into a first output data word from a set of b possible output data words, b being an integer, said method comprising the steps of: separating said input data word x into n portions x i through x n ; generating said first output data word according to f y (x) = y 0 x 1 + y 1 x 2 + .... + y n-1 x n , where the addition and multiplication operations are those of a finite field of b elements, and where y is an element of the field.
Claim 2
Independent Claim
102 words
A method of compressing an input data word x into a first output data word from a set of b possible output data words, b being an integer, said method comprising the steps of: separating said input data word x into n portions x i through x n ; generating said first output data word according to f y (x) = y 0 x 1 + y 1 x 2 + .... + y n-1 x n , where the addition and multiplication operations are those of a finite field of b elements, and where y is an element of the field.
Claim 3
Dependent Claim
41 words
A method as defined in claim 1, wherein said generating step further comprises the steps of providing a set of b different values for said integer y, and selecting one of said different values for use in calculating f y (x).
Claim 4
Dependent Claim
23 words
A method as defined in claim 1, wherein said generating step comprises generating said first output data word according to the following formulae:
Claim 5
Dependent Claim
28 words
A method as claimed in claim 1 in which b is of the form p k where p is a prime number and k is a positive integer.
Claim 6
Dependent Claim
44 words
A method as defined in claim 4, wherein k = 1 and said generating step comprises generating said first output data word according to fy(x) = (y 0 x 1 + y 1 x 2 + .....+ y n-1 x n ) (mod b).
Claim 7
Dependent Claim
44 words
A method as defined in claim 1, wherein said first input data word x is a multi-bit data word, and said separating step comprises separating said multi-bit data word into a plurality of portions each having no more than a predetermined number of bits.
Claim 8
Dependent Claim
17 words
A method as defined in claim 6, wherein said predetermined number of bits is log 2 (b).
Claim 9
Dependent Claim
61 words
A method as defined in claim 1, wherein said first input data word x is a multi-digit data word, and said separating step comprises separating said multi-digit data word into a plurality of portions each having no more than a predetermined number of digits given by logr (b) where r represents the radix in which said data word x is represented.
Claim 10
Dependent Claim
13 words
A method as defined in claim 5, wherein 0 ≤ y < b.
Claim 11
Independent Claim
33 words
A method as defined in any preceding claim, wherein said method further comprises the step of generating a second output data word according to g (f (x)), where g is a hash function.
Claim 12
Independent Claim
54 words
A method as claimed in any preceding claim for a data processing system of the type wherein a first data word is represented by a multi-bit element x, said system including a memory having at least b storage locations, the method being applied to generate an address for said data word in said memory.
Claim 13
Independent Claim
99 words
A method as claimed in any preceding claim, applied to communicating a data message M, said data message M including a plurality of bits, said method comprising the steps of: separating said message M into said plurality of portions x 1 through x n , generating an authentication tag T for transmission with said message M, said authentication stage T being generated according to f (x) = (y 0 x 1 + y 1 x 2 + ....+ y n-1 x n ) (mod b), where y is an integer; and transmitting said message M and authentication tag T.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.