Questions tagged [hash-function]

For questions about hash functions: functions from a big set to a smaller one such that the same output $f(x_1)=f(x_2)$ for different input $x_1\ne x_2$ is unlikely, especially if $x_2$ differs from $x_1$ by a random error or is crafted by an adversary.

176 questions
1k views

Curious Properties of 33

Because my explanation has so many words, I'll start with my question and then you can read the explanation if you need to: The Bernstein Hash method uses the number 33 as a multiplier. From what I'...
498 views

How to attack universal hash function based on finite-field arithmetic?

As per the Recursive n-gram hashing is pairwise independent, at best paper, I want to use the algorithm described in chapter 6 and 7 (page 7 - 10). The hash works as follows: Define a random function ...
1k views

Hide my invoice number

I'm not a mathematician, so please forgive any ignorance. I have a small business - I'm generating invoices incrementally. I'm currently on about invoice number 4000. I guess I don't want my ...
11k views

How can I convert this unique string of characters into a unique number?

I have an unusual programming problem and the math side of it has me stumped. It's probably a simple answer but math isn't my strongest area. I've generated a unique string of 7 characters which are ...
82 views

Bloom Filter with an interval input

I have been trying to design a variant of a bloom filter that can insert an interval of values at once, as well as query if a certain interval is in the bloom filter. I haven't been able to think of a ...
225 views

Bloom filter optimization on an interval of inputs

I'v been tackling a problem with bloom filters. I have a basic version working on paper, but I need to be able to put a large interval of numbers into the filter at a given time. Let ...
1k views

Birthday Problem applied to collisions

I'm trying to extend the birthday problem to detect collision probability in a hashing scheme. Here is my problem. I use the letters and numbers [A-Z][a-z][0-9] to make a set of keys by randomly ...
1k views

Universal Hashing

to my current understanding Universal Hashing is a method whereby the hash function is chosen randomly at runtime in order to guarantee reasonable performance for any kind of input. I understand we ...
1k views

I need a hash function that is easily computable in parallel(think of MapReduce framework), so such hash function must be "additive". I.e. given such function f, ...
264 views

An efficient way to find anagrams

Consider a set of words where you want to divide the set into subsets of words, where all members of each subset are anagrams (same letters, different arrangement). You can do this computationally in ...
485 views

Where do hash functions come from?

I have some basic understanding of how hash functions work, however, I have no idea of how mathematicians created them. Were them a byproduct of a non cryptografics related research or were them a ...
9k views

Calculate unique Integer representing a pair of integers

I have a pair of positive integers $(x, y)$, with $(x, y)$ being different from $(y, x)$, and I'd like to calculate an integer "key" representing them in order that for a unique $(x, y)$ there is an ...
768 views

Hash with Chaining Problems

I ran into an example in Computer Science Course. suppose we use Hashing with chanining and use table of size m. the hash function map record with key ...
2k views

Difference between universal and k-universal

After reading definitions of universal and k-universal (or k-independent) hash function families, I can't get the difference between them. Also, I couldn't find any examples of hash function families ...
501 views

Help in understanding the properties of prime numbers

I was reading about hashing. The oldest/standard approach is to use a prime number to produce the hash. At first I couldn't get why use a prime when I came to this Why hash functions use primes: ...
1k views

Do hashing functions have a probability distribution calculated for their output?

This question might look strange, so I will try to be clear. Consider a hashing function $f : M \mapsto H$ which takes a message with arbitrary length $m \in M$ as input and returns a hash $h \in H$ ...
48 views

268 views

How many SHA-256 hashes of emails are duplicates of each other?

There are $5$ billion unique email addresses in the World. If I created a database containing their SHA-256 hashes, how any unique hashes would we expect that database to contain? By my crude methods,...
1k views

Math behind perfect hash

I am reading material on cryptographic hash functions and it says "Collision resistant property : for a hash of length L, a perfect hash would take $2^{L/2}$ attempts." Can someone explain why? ...
329 views

Probability of $k$ collisions

Say we have $m$ buckets. We select a random bucket and put a ball in it, we repeat this $n$ times. In the end what is the probability of having at least one bucket with exactly $k$ balls? I have ...
2k views

How Jaccard similarity can be approximated with minhash similarity?

In Page 81 of this book, Mining of Massive Data Sets. It says the following: Now, consider the probability that $h(S_1) = h(S_2)$. If we imagine the rows permuted randomly, and we proceed from the ...