# Tag Info

Accepted

### Why is it best to use a prime number as a mod in a hashing function?

Consider the set of keys $K=\{0,1,...,100\}$ and a hash table where the number of buckets is $m=12$. Since $3$ is a factor of $12$, the keys that are multiples of $3$ will be hashed to buckets that ...
• 3,734

### Do passwords need a max length?

No. There is no* limit on the length of the input to for most* good cryptographic hash functions. As a result, password hashing can support passwords of unlimited length and do not need to impose a ...
• 162k
Accepted

### What is the point in hashing a value?

The purpose of a hash in this scenario to be able to uniquely identify an entity. It's not strictly unique, only probabilistically unique. Hashes are not reversible functions, so your client can't ...
• 649
Accepted

### Hashing using Hornerâ€™s Rule

Let's prove by induction that after $i$ iterations, $$r = \sum_{j=1}^i 256^{i-j} c[j] \bmod m,$$ where $m$ is the size of the table. The base case is $i = 0$, where $r = 0 = 0 \bmod m$. Now suppose ...
• 278k

### Do passwords need a max length?

Yes, passwords need maximum length, but not because of collision risk (see other answers regarding collisions). Reason for setting maximum length - possibility of denial of service attack. Someone ...
Accepted

• 162k
Accepted

### Surprisingly high collision rates when hashing a short list with few buckets

Depending on how you count collisions, we can expect either about 2000 collisions, or about 1472 collisions. The latter is in close agreement with what you observe, so yes, 1500 collisions looks ...
• 162k

### Method for eliminating spent hashes from a large collection?

There is no lossless way to compress a set of arbitrary numbers where the size of the set is unbounded to a fixed number of bits. Cryptography won't help with that. If you're okay with the storage ...

### Can we do 4-sum algorithm in O(n^2)?

You are right, but Jeff's answer in the link you provided works in the "linear decision tree model". You cannot use hashing in that model.
• 126

### is modulo of hash function is evenly distributed?

if I take the result of a 32bit hash function(the param is random string) and apply module N on the result - will the values be evenly distributed? It depends on the hash function. For a good hash ...
• 13.3k

### Store a n-bit string using only O(log n) space

There are $2^n$ many $n$-bit strings, but only polynomially many strings of length $O(\log n)$.
• 278k
Accepted

### Self referential hash function possible?

Yes. You can construct such a function. Let $g:\{0,1\}^* \to \{0,1\}^k$ be any hash function. We will define $f$ as follows. On input $x = x_1 \cdots x_n$, compute: For $i := 1,2,3,\dots,n$, do: ...
• 162k
Accepted

### Hash functions producing uniform outputs

What are the quadratic residues in $\mathbb{Z}_{10}$? What about the cubic residues? What are the orders of $[11]$ and $[12]$ in the group $(\mathbb{Z}_{10}, +)$? A brief solution follows. For the ...
• 4,272