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
8
votes
6 answers

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 customers knowing how much business I'm doing (i.e. if…
Eamorr
  • 225
6
votes
3 answers

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 unique key and no other pair $(w, z)$ could…
IggY
  • 207
5
votes
2 answers

How can I convert this unique string of characters into a unique number?

I have an unusual programming problem and the math side of it has me stumped. It's probably a simple answer but math isn't my strongest area. I've generated a unique string of 7 characters which are each randomly selected from these possibilities:…
J.Todd
  • 253
4
votes
1 answer

Reversible hash function for mapping a set of integers to another set

I'm looking for a reversible hash function that would map any 64-bit integer to another, with 1-to-1 correspondence, i.e. one number in one set maps to only one number in another set, both ways. It is also important that the mapping is…
mojuba
  • 183
4
votes
2 answers

"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, another function g must exist, having the property g(f(X),f(Y))=f(X||Y), where ||…
Nya
  • 141
4
votes
1 answer

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 being universal, but not k-universal (it's…
aplavin
  • 591
2
votes
2 answers

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 a calculator) that I can use to help explain…
IQAndreas
  • 143
2
votes
1 answer

Is there some reversible mapping that as uniform as a hash?

I am looking for a mapping to encode a n-bits information into n-x+m bits. The (n-x) bits need to be as uniform as posible, and I can accept a small mount of data to achieve this (such as a nxn matrix). The m bits are free to be in any…
Galaxy
  • 125
2
votes
1 answer

Colliding pairs - hash functions

Let $h:D\to [m]$ be a hash function that maps some object from the set $D$ to a natural number $k$ ($1 \leq k \leq m$) with probability $1/m$ for every $k\in [m].$ A falsely colliding pair are two elements $d_1, d_2 \in D$ with $d_1 \neq d_2$ but…
Hilberto1
  • 1,046
2
votes
0 answers

Is this a good method for deterministically randomising the order of two names?

In English speaking culture, when a man and a woman get married, the woman traditionally takes the man's surname. My brother took his wife's surname, but he is the exception, not the rule. Some people have said that this system is unfair because it…
CJ Dennis
  • 654
2
votes
4 answers

Can different source files produce the same hash value?

It is often said in judicial opinions and legal briefs that the hash value derived from a file is like a fingerprint that uniquely corresponds to the source file. While this may be true in a practical sense, I question whether it is literally true.…
GAS4
  • 23
2
votes
0 answers

What enables hash function to produce uniform distribution given any distribution of input

I always take the uniformity of hash output as a given and didn't think much of it. Now I am kind of curious, how does good hash function like sha guarantees output uniformity. Intuitively, given 1:1 input cardinality to output cardinality, the same…
Jal
  • 121
2
votes
0 answers

Universal Hashing - probability of collision

I can't seem to get my head around a following conclusion: Def: H is a finite set of hashing functions from U to [m] (set of size m). We'll call H universal if: $\forall x,y; x\ne y $ there exists $\frac{|H|}m$ functions $h\in H$ such that…
Quimby
  • 168
2
votes
2 answers

How to implement a hash function intentionally prone to preimage attacks? (and hence pseudo-reversible)

I need to design a hash function such that it is possible to enumerate all possible 'candidate' input strings (preimages) for a given hash (image). It must otherwise be a normal hash function [i.e. small differences in input (preimage) --> large…
Ala
  • 21
2
votes
0 answers

Minimal perfect hash function

If I have list of $n$ unbounded different random integers, is it always possible to find such integers $\alpha$, $\beta$ and $\gamma$, that function $$f(x)=((\alpha\times x+\beta)\mod\gamma)\mod n$$ will have different values for all numbers in the…
Somnium
  • 1,567
  • 1
  • 13
  • 27
1
2 3