# 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.

194 questions
Filter by
Sorted by
Tagged with
55 views

### I need a hash function that will give all values from $0$ to $2^n - 1$. Will $f(x) = \frac{x^2 + x}{2} \; \text{mod} \; 2^n$ do the job?

I need a hash function that will give all values from $0$ to $2^n - 1$. I want to know if this function does what is needed? $$f(x) = \frac{x^2 + x}{2} \; \text{mod} \; 2^n$$ the values of $x$ are ...
25 views

### Probability distribution for collisions / birthday problem

Let's say I have a source of randomly produced values from a range $M$. I want to test if the source is a uniform distribution by examining a sample sequence of $n$ values $m_1, m_2,\dots,m_n$. ...
21 views

### Probability a near universal hash function $ax \mod p \mod m$ produces an output from inputs equal modulo $m$

For a given near universal hash function $f(x) = ax \mod p \mod m$ where $p$ is prime and $m < p$, what is the probability that given $x_r \in \{ x | x \mod p \mod m =r\}$, $f(x_r) = s$? That is, ...
27 views

### show that $h(k)=\left \lfloor{\frac{k}{m}}\right \rfloor \mod m$ is a bad hash function where $m$ is prime

A "good" hash function should make use of all slots with equal frequency. In this case the ammount of slots is given with $m$. Also keys which are similar should be distributed as broadly as possible....
9 views

30 views

### Existence of a Perfect Cryptographic Hash Function

Is there a hash function that satisfies all the following properties: 1. It is 1 to 1 (no collisions). 2. It can take any size input. 3. For any input, and some desired set of characters, there ...
328 views

### Representing a String of n characters, as a unique integer

So I have been following the lecture series on algorithms from MIT. I got to the part on Rolling Hashes and Karp-Rabin algorithm Karp Rabin Notes The way I understand it is in order to represent ...