Efficient universal hashing method
First Claim
Patent Images
1. A method for producing a shortened representation of a collection of bits, comprising the steps of:
- inputting the collection of “
n”
bits;
summing a key having at least “
n”
bits with the collection of bits to produce a sum;
squaring the sum to produce a squared sum;
performing a modular “
p”
operation on the squared sum, where “
p”
is at least as large as a first prime number greater than 2n to produce a modular “
p”
result;
performing a modular 2l operation on the modular “
p”
result to produce a modular 2l result where, “
l”
is less than “
n”
; and
outputting the modular 2l result.
10 Assignments
0 Petitions
Accused Products
Abstract
An efficient hashing technique uses
operations to hash a string “w” words long rather than the w2 operations of the prior art. This efficiency is achieved by squaring the sum of the key and the string to be hashed rather than forming a product of the key and the string to be hashed
h(m)=((m+a)2 mod p)mod 21.
11 Citations
3 Claims
-
1. A method for producing a shortened representation of a collection of bits, comprising the steps of:
-
inputting the collection of “
n”
bits;summing a key having at least “
n”
bits with the collection of bits to produce a sum;squaring the sum to produce a squared sum; performing a modular “
p”
operation on the squared sum, where “
p”
is at least as large as a first prime number greater than 2n to produce a modular “
p”
result;performing a modular 2l operation on the modular “
p”
result to produce a modular 2l result where, “
l”
is less than “
n”
; andoutputting the modular 2l result.
-
-
2. A method for producing a shortened representation of a collection of bits, comprising the steps of:
-
inputting the collection of “
n”
bits;summing a first key having at least “
n”
bits with the collection of bits to produce a first sum;squaring the first sum to produce a squared sum; summing the squared sum with a second key having at least “
n”
bits to produce a second sum;performing a modular “
p”
operation on the second sum, where “
p”
is at least as large as a first prime number greater than 2n to produce a modular “
p”
result;performing a modular 2l operation on the modular “
p”
result to produce a modular 2l result where, “
l”
is less than “
n”
; andoutputting the modular 2l result.
-
-
3. A method for producing a shortened representation of a collection of bits, comprising the steps of:
-
inputting a collection of “
n”
bits;summing a key having at least “
n”
bits with the collection of bits to produce a sum;squaring the sum to produce a squared sum; repeating the previous three steps at least once to produce a plurality of squared sums, where a different key is used each time the steps are repeated; summing the plurality of squared sums to produce a summation; performing a modular “
p”
operation on the summation, where “
p”
is at least as large as a first prime number greater than 2n to produce a modular “
p”
result;performing a modular 2l operation on the modular “
p”
result to produce a modular 2l result where, “
l”
is less than “
n”
; andoutputting the modular 2l result.
-
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
-
Current AssigneeRPX Corporation
-
Original AssigneeLucent Technologies, Inc. (Nokia Corporation)
-
InventorsPatel, Sarvar, Ramzan, Zulfikar Amin
-
Primary Examiner(s)Barrón, Jr.; Gilberto
-
Assistant Examiner(s)PERUNGAVOOR, VENKATANARAY
-
Application NumberUS09/175,178Time in Patent Office3,031 DaysField of Search380/28, 380/29US Class Current380/28CPC Class CodesH03M 7/30 Compression speech analysis...
