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

-1
votes
0answers
30 views

Is there a function that will produce unique output based on two integers? [duplicate]

Presume two integers A and B are obtained. These integers may follow any rules as to their generation (i.e., if primes would be useful, then let them be primes) but cannot influence each other's ...
0
votes
1answer
29 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?
4
votes
1answer
46 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 ...
0
votes
0answers
4 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
21 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
24 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
45 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
517 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 ...
0
votes
1answer
32 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 ...
0
votes
0answers
33 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
22 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
56 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
12 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
82 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
53 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 ...
0
votes
1answer
49 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
39 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
27 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
26 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
38 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
29 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
71 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
39 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 ...
0
votes
0answers
25 views

higher order hash functions

I am trying to find a functions which can efficiently transform (input) N number to and Integer K (and uniformly distribute it over some range - will use this as hash function). It is kind of a hash ...
1
vote
1answer
53 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
96 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
451 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 ...
0
votes
0answers
18 views

How many torrents are required to have a 50% chance of a duplicate infohash?

So I was wondering how many torrents would need to be created so there would be a 50% probability of two different torrents having identical info-hashes. If you could give a general formula for ...
3
votes
0answers
73 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
81 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
227 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
154 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
136 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
487 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
257 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
347 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
120 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
175 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
97 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
129 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
55 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
61 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
215 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 ? ...
0
votes
1answer
124 views

Is this function reversible?

I have a function which takes an integer from within a range (for example, 0-9999 with a range of 10,000) which outputs another integer within the same range. To my understanding, this is a perfect ...
0
votes
1answer
186 views

Proof of calculating Minhash

I'm reading about MinHash technique to estimate the similarity between 2 sets: Given set A and B, h is the hash function and $h_\min(S)$ is the minimum hash of set S, i.e. $h_\min(S) = \min(h(s))$ for ...
3
votes
1answer
483 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$ ...
1
vote
1answer
895 views

hash function for matrices over finite field (Matlab)?

What is a good hash function for small nonsingular matrices over a field $\mathbb{F}_p$ for $p$ prime? I'm looking for an integer function which is close to being injective (but not necessarily ...
0
votes
1answer
609 views

Analogy of Binary subtraction to decimal subtraction [duplicate]

Possible Duplicate: How to do +, -, *, / with number in a base b? Subtraction of numbers with arbitrary bases This is a very basic question. But I come from non computer science ...