Mathematics Stack Exchange
Mathematics Stack Exchange

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.

245 questions
1
vote
2 answers

Can I reverse any hash algorithms to find a set of the possible orginals?

If I map 1024 bits onto a 16 bit hash (just random numbers for conversation sake), I will have an average of 64 collisions per hash (assuming a good algorithm). I wonder if anyone knows any hash algorithms around today in which I could take a hash…
David Parks
  • 445
1
vote
3 answers

Chance that first 6 characters of a SHA-1 hash matching another SHA-1 hash?

Just what the question says -- what is the chance that the first six characters of a SHA-1 hash will match the first six characters of any given SHA-1 hash?
JDS
  • 113
1
vote
0 answers

Is $(i+1) \text{ mod } n$ a hash algorithm with strong universality?

Please correct me if I got it wrong. I am trying to learn MinHash algorithm by implementing one. The hash function needs better to be min-wise independent instead of pairwise independent. I'm testing both to understand the different effects on the…
dz902
  • 113
1
vote
1 answer

Possibility of duplicates in hash table

I have a problem where I am trying to find the relationship between parts and the parts that make them up. Like if a boiler is made with two side plates and one bottom plate, and the side plates have five bolts and the bottom four, than a tractor…
kleineg
  • 1,795
1
vote
0 answers

What is the formula for calculating load factor of hash table when collisions are handled by many different techniques?

I am in a rush to submit some assignment, may I have the formula for calculating the load factor of hash tables when collisions are handled by linear probing, quadratic probing and double hashing? I understand that for separate chaining the formula…
Mireodon
  • 23
1
vote
2 answers

Why are those hash functions considered a bad choice?

Given Hashtable $T[0,..,m-1]$ and $U = \{0, . . . , n − 1 \}$ set of possible keys $k$ with $m \ll n$ Let $$h: U \rightarrow \{0, . . . , m − 1 \} $$ I am trying to understand why the hash functions $$h_{1}(k) =\Big\lfloor…
yarafoudah
  • 333
1
vote
0 answers

Hash without overflow

I am trying to hash an $n$-character string into one of $m$ slots by treating the string as radix-128 number without overflowing a 32-bit word, where $0 < m < 2^{31}$. I utilize the properties of modular arithmetic and horner's method for computing…
sma
  • 336
1
vote
1 answer

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 exists a third set characters that can be appended to…
William Grannis
  • 1,844
1
vote
1 answer

Hash function to determine whether two vectors had an equal entry on some row

Do you know about a hash function, that approximates (in probability) the following function: Original function: Two vectors collide if there is a row where their entries are equal. $$ \text{E.g.,…
ndrizza
  • 1,348
1
vote
0 answers

How to randomly hash a 64-bit int

I am trying to write a hash function to map a 64-bit integer to another "random-looking" 64 bit integer. Here are my requirements: I can only use /, *, +, -, and mod. I can choose arbitrary constants, but they are fixed (in order for this to be a…
Brandon
  • 465
  • 4
  • 15
1
vote
1 answer

Monotone one-way hash function

I am sitting on a contradictory requirement in which I would need a function that is a one-way hash, but that is also monotone. One-way: if $y=h(x)$, then computing $x=h^{-1}(y)$ is intractable, or at least, difficult. A textbook example could be…
erik
  • 61
0
votes
0 answers

Does storing the password in two separate bcrypt hashes with different keys make it easier to crack the password?

I use bcrypt to hash and store user passwords, and then again to generate unique access tokens, both of which are salted. In the first case, I simply hash the password + a salt (one randomly generated salt per user) In the second case, I hash, with…
moonman239
  • 553
0
votes
0 answers

Generate a function f() which maps a known set to another known set

I have a set S of random positive integers that is of known size n. Is there a way to generate a hashing function which perfectly maps each value of S uniquely onto the set P where P consists of values 0 to n-1. For example: Given: S = { 345, 69205,…
TheBat
  • 101
0
votes
0 answers

Perfect Hash Function that detects invalid inputs?

I work in hardware/electronics where everything is power of 2. To avoid storing the key along with the value, I can find a perfect hash function for the known-in-advance keys. Nevertheless, the PHF doesn't tell me if a key is invalid (not part of…
None
  • 101
  • 2
0
votes
1 answer

Hash collision probability

I am trying to show that the probability of a hash collision with a simple uniform 32-bit hash function is at least 50% if the number of keys is at least 77164. I have figured out how to plot a graph on python and then read off the values and…
acme_2020
  • 71
1
2
3