Name
Abstract | ||
|---|---|---|
Universal hash functions, discovered by Carter and Wegman in 1979, are of great importance in computer science with many applications. MMH* is a well-known ¿-universal hash function family, based on the evaluation of a dot product modulo a prime. In this paper, we introduce a generalization of MMH*, that we call GMMH*, using the same construction as MMH* but with an arbitrary integer modulus n 1 , and show that GMMH* is 1 p -almost-¿-universal, where p is the smallest prime divisor of n. This bound is tight. Universal hashing is connected to the number of solutions of linear congruences.The connection is made via a classical result of D.N. Lehmer.A generalization of MMH*, that we call GMMH*, is introduced.GMMH* uses the same construction as MMH* but with an arbitrary modulus n 1 .GMMH* is 1 p -almost-¿-universal, where p is the smallest prime divisor of n. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.ipl.2016.03.009 | Inf. Process. Lett. |
Keywords | Field | DocType |
Universal hashing,MMH⁎,GMMH⁎,Linear congruence,Cryptography | Prime (order theory),Integer,Discrete mathematics,Combinatorics,Modulo,Chinese remainder theorem,Universal hashing,Hash function,Dot product,Prime factor,Mathematics | Journal |
Volume | Issue | ISSN |
116 | 7 | Information Processing Letters 116 (2016), 481-483 |
Citations | PageRank | References |
3 | 0.48 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Khodakhast Bibak | 1 | 13 | 6.63 |
| Bruce M. Kapron | 2 | 308 | 26.02 |
| S. Venkatesh | 3 | 53 | 7.11 |