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.

learn more… | top users | synonyms

0
votes
0answers
18 views

Conceptual hashing function with quadratic probing

Lengthy question here so please bear with me. When inserting keys 3,4,2,5,1 in the order given into the hash table of length m=5 using hash function $$h(k) = k^2 \mod m$$ Using $h(k)$ as the ...
1
vote
0answers
25 views

Is MD5 hash a bijection for input length < $2^{128}$ bits

The MD5 hashes have a length of 128 bits. It seems therefore obvious that if we could get all hashes from MD5 for more than $2^{128}$ inputs, at least 2 hashes would be identical. But what if we ...
0
votes
0answers
11 views

Calculating the distribution H, H(X) when H is chosen uniformly from a family of hash funcitions

Suppose I have a family $H$ of hash functions from $A$ to $B$ such that for all $x\in A$, $h(x)$ distributes uniformly in $B$ (the probability is taken over h) Now, if $X$ is some distribution over ...
1
vote
0answers
32 views

Consistent hashing using modulo

Following my answer here: Suppose I have n servers, and I want to distribute files evenly between them (same number of files on each server). Initially n=2 and I use the following function to map a ...
1
vote
0answers
28 views

Probability of probing $t$ locations in a Cuckoo hash is $O(\frac{1}{2^{t/2}})$ locations in the worst case

Prove that the probability that an insertion into a cuckoo hash table probes $t$ array locations is $O(\frac{1}{2^{t/2}})$. Keep in mind that there are two tables, each with size $s \ge 2n$, ...
2
votes
2answers
53 views

Probability of 8 or 9 digit sequence colliding in the same place in two 65 digit numbers

I have two numbers: 3032643431333337636238613038343231383364303731376566303037663231 3861663464383131656131653461343961343364303737663565356561653361 36430373 ...
3
votes
1answer
38 views

Toy cryptographic hash function for education purposes?

I'm teaching some high school students about number theory and cryptography, and I'd like a hash function (or ideally, a family of hash functions) that I can use as simple demonstration for ...
0
votes
0answers
24 views

Proving modular hash function

I am having trouble getting started with the following problem : Suppose that keys are t-bit integers. For a modular hash function with prime M (the number of hash indexes), prove that each bit has ...
0
votes
1answer
32 views

Find a function that maps x,y to $[0, n ( n + 1) / 2)$

Can you find me a bijective function that maps positive integers $x, y$ such that $0 \leq x < y \leq n$ to integers in $[0, n(n+1)/2)$ to use as a hash function?
1
vote
1answer
62 views

Hashing With Chaining Collision

We have $1000$ elements with key=1 to 1000, and a hashing function $$ h(i)=i^3 \mbox{ mod } 10 $$ for an array with length $10$ (array index from $0$ to $9$) with chaining method. What is the ...
-1
votes
0answers
5 views

How to calculate radius density of observation using locality sensitive hashing?

How do I calculate radius density of observation using locality sensitive hashing? I am new to the locality sensitive hashing(LSH). LSH based learning and Querying was difficult to understand.
0
votes
0answers
22 views

Possibility for collision using 2 different Hash-Algorithms

I'm definitely no crack in mathematics so I hope you can help me. Hash algorithms provide functions for reducing big data to smaller ones. For instance, SHA-512 reduces a set of data down to 512 bit ...
0
votes
1answer
29 views

Hashing function probability of collision, is this solution wrong?

We hash n keys into k=1000 memory locations one by one. What is the probability that the first i records do not produce a collision. Assume each key is independently and uniformly hashed into the ...
1
vote
1answer
224 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(S1) = h(S2). If we imagine the rows permuted randomly, and we proceed from the top, ...
8
votes
6answers
529 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 ...
1
vote
1answer
49 views

hash function not using bitwise operations

I have a need for implementing an algorithm to validate that a given message is not altered after some operations (for instance after transmission over a medium). A typical way of doing this kind of ...
1
vote
1answer
52 views

Slot size bound for chaining

This is a question from CLRS Q) Suppose that we have a hash table with n slots, with collisions resolved by chain-ing, and suppose that $n$ keys are inserted into the table. Each key is equally ...
0
votes
0answers
26 views

Hash functions for unordered data

I am interested in stream hash functions for unordered data: Hash functions $g$ on lists which, given a two lists of integers $L_1, L_2$ where $L_2$ is a permutation of $L_1$, $g(L_1)=g(L_2)$. I can ...
1
vote
2answers
68 views

An “additive” cryptographic hash-function that allows calculating the hash of some data from the hashes of the parts of that data.

I want to use a cryptographic hash-function that allows calculating the hash of some data from the hashes of the parts of that data. This question was already asked on SO - "Additive" hash ...
0
votes
0answers
17 views

random hash function, compute the expected number of empty table entries..

I am working on hash tables.In hash tables we have wastage of space due to empty table entries. can we have any hash function that can compute expected number of empty entries. I have seen the same ...
2
votes
2answers
92 views

Is there a hashing algorithm that can be done on paper?

I often want to explain to non-computer literates about MD5, or why any sort of hashing is done. Is there any type of simple hashing algorithm that can be done with a pen and piece of paper (possibly ...
0
votes
0answers
64 views

describe a vector with a single unique number

Is there a way to uniquely describe a vector with a single ( = easy to store) value? e.g. have a function $H(\vec{v}): \mathbb{R}^{130} \rightarrow \mathbb{R} $ I have a lot of vectors in ...
1
vote
1answer
53 views

Does reducing 512-bit blocks to 128-bit hashes lead to 1/4 chance of collision?

This is a quote from a cryptography book called Implementing SSL / TLS Using Cryptography and PKI By Joshua Davies. MD5 operates on 512-bit(64 byte) blocks of input. Each block is reduced to a ...
0
votes
1answer
44 views

Number of combinations of balls in slots

Assume there are 9 identical balls, and each can be placed in one of 10 numbered slots. All balls must be placed in exactly one slot (i.e., you can't leave a ball out). How many combinations are ...
0
votes
1answer
28 views

Distinguishing between hash function digest and message corruption

As an initial disclaimer, I know virtually nothing about coding theory. I apologize in advice for incorrect or inappropriate terminology. The problem space I'm exploring is ensuring the integrity of ...
0
votes
0answers
28 views

Proving that collision is less likely if the table size is prime in case modulo arithmetic is used

If suppose your hashCode function results in the following hashCodes among others {x , 2x, 3x, 4x, 5x, 6x...}, then all these are going to be clustered in just m number of buckets, ...
0
votes
0answers
27 views

Universal hashing proof

So I tried doing this proof but I do not know how to start it properly. I know I have to show that the hash function family has the consistent and random property. The first is rather obvious to ...
1
vote
0answers
43 views

Identity based encryption

I am implementing ID based encryption in c# right now i am having problem at the following mathematics $$H_1: \{0,1 \}^n \times \{0,1 \}^n \to \mathbb{Z}^*_p, \text{ what does this expression ...
0
votes
1answer
32 views

“Unique” number from several values

I'm trying to create a unique unsigned "long" number (64 bits) from a list of 4 other numerical values. Some function f(n1, n2, n3, n4) = x. The order of the values ...
2
votes
2answers
73 views

Calculate people needed to have all birthdays

for n people where n > 365, how can you calculate how many people you would need to expect that each of every distinct possible birthday would be had by at least one person at a given probability p? ...
1
vote
1answer
41 views

Polynomial division with reference to CRC32

The polynomials we're using will always have coefficients of either 1 or 0. We have a divisor polynomial which will always remain the same, we'll call this polynomial $D$. We have a dividend ...
1
vote
1answer
61 views

Calculate entropy of modified base32 hash

I am trying to develop a scheme for generating unique (probable within bounds) ids in a distributed application. I want the id to be easily remembered, easily spoken, and easily read. I chose base32 ...
1
vote
1answer
102 views

Searching for random items in a set of lists

This is a programming question, but I'm interested in the math behind it so I think it's better asked here. Say I have a list of items and I'm looking for one item in the list that satisfies a ...
1
vote
3answers
694 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 ...
3
votes
0answers
82 views

Finding collision for a hash function

Is there a way to find a collision for a given hash function without brute forcing? The particular hash function I'm talking about is the one used by Python (simplified version given below). It ...
1
vote
1answer
84 views

How can one gurantees the intersection of two set is empty with respect to its hash value?

Let's say we have sets A = {1,2,3} and B = {1,3,10} and our hash function is h(x) = 2x + 1(mod9) therefore H(A) = {3,5,7} H(B) = {3,7} Therefore if there is no intersection between the ...
1
vote
1answer
261 views

Probability of a slot having exactly $K$ elements

From this question asked in an interview: Consider a hash table with $M$ slots. Suppose hash value is uniformly distributed between $1$ to $M$. Suppose we put $N$ keys into this $M$-slotted ...
0
votes
3answers
181 views

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?
0
votes
0answers
82 views

Is Hash(bG) equal to b(Hash(G))?

Assume b is an integer, G is a basepoint in an elliptic curve, and Hash is a one-way hash function. Is Hash(bG) equal to b(Hash(G)) ? or not? Note: A hash function is any algorithm or subroutine ...
1
vote
1answer
145 views

Bit permutations and collisions of compression function

I'm having trouble finding a good method for solving the following problem: If $n$ is a positive integer, let $S_n$ denote the group of permutations of the set $\{1,2,\dots, n\}$. For a permutation ...
2
votes
1answer
648 views

Can someone offer an intuitive understanding of linear/quadratic probing and double hashing?

I'm reading through Introduction to Algorithms, and I'm having trouble grasping intuitively how linear probing, quadratic probing, and double hashing exactly work. I suspect my confusion lies within ...
2
votes
3answers
311 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 ...
3
votes
1answer
409 views

“Additive” hash function

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, ...
1
vote
1answer
122 views

How to create 2048 random bits from 256 bits?

Would merely repeating the same value 8 times be sufficient ? Or is there a more clever approach for doing this ? The 256 bit values would be generated from SHA256 of files.
2
votes
1answer
216 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 ...
1
vote
1answer
112 views

probability of repeating values in a hashmap

Suppose you have a hashmap where you store values. The hashmap is of size m and supports chaining. The hash function is simple uniform hashing assumption. I understand that the average length of a ...
0
votes
1answer
135 views

Universal hashing (bijection) with multiplication

I came across this question while thinking about a CS problem: Given a set $S = [a,b]$ , and a string $x \in S^{n}, x = r_1r_2 \cdots r_n$, under what conditions is $H(x) = r_1 * r_2 * \cdots * r_n$ ...
1
vote
1answer
59 views

Function for unique hash code

I am interested in finding $F(x,y)$, such that $x$ and $y$ $\in \mathbb Z^+$ and $F(x,y)$ is one to one function i.e., $F(x,y)$ is unique for any unique unordered pairs of $x$ and $y$. Regards, ...
0
votes
1answer
62 views

Hash Functions and Probabilty

We are considering bit strings of length 160. Let there be some input x, and hash function $H(x) \rightarrow \left \{ 0,1 \right \}^{160}$. How many turns at least it takes to make collision: ...
2
votes
1answer
230 views

Is the product of 2 unique prime number unique?

I am wondering if I take the product of 2 unique prime numbers, and will the product be unique ? any chance to have collision ? I mean will any other 2 unique prime numbers have the same product ? ...