US4588985A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Polynomial hashing
Assignee: International Business Machines Corp
•
Filing: 1983-12-30
•
Granted: 1986-05-13
•
Expires: 2003-12-30
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 2 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 0 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 0 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 (f y (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
US
Data Source
google_patents
Last Synchronized
2026-10-27 12:19
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: 27
Claim 1
Independent Claim
115 words
A method of compressing an input data word x into a first output data word form a set of b possible output data words, b being of the form p k where p is a prime number and k is a positive integer, said method comprising the steps of: separating said input data word x into n portions x 1 through x n ; selecting an element y from a finite field of b elements; and generating said first output data word according to fy(x)=y 0 x 1 +y 1 x 2 +. . . +y n-1 x n , where the addition and multiplication operations are those of said finite field of b elements.
Claim 2
Independent Claim
115 words
A method of compressing an input data word x into a first output data word form a set of b possible output data words, b being of the form p k where p is a prime number and k is a positive integer, said method comprising the steps of: separating said input data word x into n portions x 1 through x n ; selecting an element y from a finite field of b elements; and generating said first output data word according to fy(x)=y 0 x 1 +y 1 x 2 +. . . +y n-1 x n , where the addition and multiplication operations are those of said finite field of b elements.
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
37 words
A method as defined in claim 1, wherein said generating step comprises generating said first output data word according to the following formulae: t.sub.1 =x.sub.n t.sub.i =x.sub.n-i+1 +y (t.sub.i-1), for i=2, . . . n f.sub.y (x)=t.sub.n
Claim 5
Dependent Claim
41 words
A method as defined in claim 1, 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 6
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 7
Dependent Claim
17 words
A method as defined in claim 5, wherein said predetermined number of bits is log 2 (b).
Claim 8
Dependent Claim
44 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.
Claim 9
Dependent Claim
30 words
A method as defined in claim 5, wherein said predetermined number of digits is log r (b), where r represents the radix in which said data word x is represented.
Claim 10
Independent Claim
82 words
A method of compressing an input data word into an output data word from a set of b possible output data words, where b is an integer, said method comprising the steps of: separating said first input data word x into n portions x 1 through x n ; and generating said first output data word according to f y (x)=y 0 x 1 +y 1 x 2 +. . . +y n-1 x n (mod b), where y is an integer.
Claim 11
Independent Claim
82 words
A method of compressing an input data word into an output data word from a set of b possible output data words, where b is an integer, said method comprising the steps of: separating said first input data word x into n portions x 1 through x n ; and generating said first output data word according to f y (x)=y 0 x 1 +y 1 x 2 +. . . +y n-1 x n (mod b), where y is an integer.
Claim 12
Dependent Claim
9 words
A method as defined in claim 9, wherein 0≦y≦b.
Claim 13
Dependent Claim
37 words
A method as defined in claim 9, wherein said generating step comprises generating said first output data word according to the following formulae: t.sub.1 =x.sub.n t.sub.i =x.sub.n-i+1 +y (t.sub.i-1), for i=2, . . . n f.sub.y (x)=t.sub.n
Claim 14
Dependent Claim
41 words
A method as defined in claim 9, 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 15
Dependent Claim
13 words
A method as defined in claim 9, wherein b is a prime number.
Claim 16
Dependent Claim
43 words
A method as defined in claim 9, wherein said 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 17
Dependent Claim
20 words
A method as defined in claim 14, wherein said predetermined number of bits is no greater than log 2 (b).
Claim 18
Dependent Claim
43 words
A method as defined in claim 9, wherein said 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.
Claim 19
Dependent Claim
33 words
A method as defined in claim 16, wherein said predetermined number of digits is no greater than log r (b), where r represents the radix in which said data word x is represented.
Claim 20
Dependent Claim
35 words
A method as defined in claim 9, wherein said method further comprises the step of generating a second output data word according to g z (f y (x)), where g z is a hash function.
Claim 21
Independent Claim
96 words
A method of 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 a plurality of portions x 1 through x n , where n is an integer; and generating an authentication tag T for transmission with said message M, said authentication tag T being generated according to f y (x)=(y 0 x 1 +y 1 x 2 +. . . +y n-1 x n ) (mod b), where y is an integer; transmitting said message M and authentication tag T.
Claim 22
Independent Claim
96 words
A method of 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 a plurality of portions x 1 through x n , where n is an integer; and generating an authentication tag T for transmission with said message M, said authentication tag T being generated according to f y (x)=(y 0 x 1 +y 1 x 2 +. . . +y n-1 x n ) (mod b), where y is an integer; transmitting said message M and authentication tag T.
Claim 23
Dependent Claim
108 words
A method as defined in claim 19, wherein said message M and authentication tag T are transmitted to a receiving end, said method further comprising, at said receiving end, the steps of: receiving said message M and authentication tag T; separating said received message M into a plurality of portions x' 1 through x' n ; generating a receiving end authentication tag T' according to f y (x)=(y 0 x' 1 +y 1 x' 2 +. . . +y n-1 x' n ) (mod b), where y is said integer; and comparing said authentication tag T' with said received authentication tag T to authenticate said received message M.
Claim 24
Independent Claim
122 words
A method of storing data in a data processing system, said method including the steps of generating an address for each data word to be stored and storing each said data word at its respective generated address in a memory having at least b storage locations, said system being of the type wherein a first data word is represented by a multi-bit element x, said method comprising: separating said element x into n portions x 1 through x n ; generating a storage address in accordance with f y (x)=(y 0 x 1 +y 1 x 2 +. . . +y n-1 x n ) (mod b), where y is an integer; and storing said first data word at said storage address.
Claim 25
Independent Claim
122 words
A method of storing data in a data processing system, said method including the steps of generating an address for each data word to be stored and storing each said data word at its respective generated address in a memory having at least b storage locations, said system being of the type wherein a first data word is represented by a multi-bit element x, said method comprising: separating said element x into n portions x 1 through x n ; generating a storage address in accordance with f y (x)=(y 0 x 1 +y 1 x 2 +. . . +y n-1 x n ) (mod b), where y is an integer; and storing said first data word at said storage address.
Claim 26
Dependent Claim
27 words
A method as defined in claim 1, wherein said data word x belongs to a set of a input data words, and a is greater than b.
Claim 27
Dependent Claim
27 words
A method as defined in claim 9, wherein said input data word belongs to a set of a input data words, and a is greater than b.
References Cited (Backward Citations)
US4295124A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1989-05-12 | 1989-11-11 | 1990-05-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1993-05-12 | 1993-11-11 | 1994-05-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1997-05-12 | 1997-11-11 | 1998-05-13 | $7700.00 | Window Closed / Lapsed |