# How to create a 'hashing' function that maps up to 1 to N numbers uniquely to numbers 1 to N

I would like to use or create a hashing algorithm that takes K inputs from 1 to N and maps them uniquely to different numbers on 1 to N. K can be 1 to N. Ideally I would like the hashing alg to be able to be salted, but I'm not sure that is possible if some of these numbers must be prime.

Someone in #algorithms on libera suggested using $$g^i\bmod p$$ where $$p$$ is a prime and $$g$$ is a generator of the $$p$$ prime ring, but I never took an abstract algebra class, so this is a bit over my head. I have this:

uint64_t primeHash(uint64_t const& i, uint64_t const& p)
{
uint64_t g = 4294967311; // first prime after sqrt(p_max)
for (unsigned int _ = 0; _ < i; ++_)
g *= g;

return g % p;
}


and I am thinking I would set p to N, which would be p = 100, but p is then not prime and the first 3 numbers are not unique:

i: 1 gen: 128849019105         g^i mod p: 5
i: 2 gen: 57982058546625       g^i mod p: 25
i: 3 gen: 5870683425282890625  g^i mod p: 25


I am all mixed up. Where am I going wrong with my understanding? How do I bound my outputs to 1 to N (here 100) ?

• The function $f(i)= i \bmod N +1$ satisfies your requirements. Also your exponentiation function is slow prone to overflows. You can implement it in time $\approx \log i$ and keep the numbers small by using the relations $g^i \bmod p = 1$ if $i=0$, $g^i \bmod p =(g^{i/2} \bmod p)^2 \bmod p$ if $i \ge 2$ and $i$ is even, and $g^i \bmod p = \big( g ( g^{(i-1)/2} \bmod p)^2 \big) \bmod p$ if $i$ is odd. Nov 23, 2023 at 12:46
• – D.W.
Nov 24, 2023 at 23:57

## 1 Answer

Look for “linear congruential random number generator”. If you take a random number generator with range 0 <= r < n that’s basically what you want. And it’s quite fast.

• from the wikipedia article on them it looks like I have to choose a modulus that is prime to get the full period. So, if I want to generate numbers from 1 to 99, I can't use modulus 100 to get a period of m-1 and would have to use either 97 or 101 and will either not generate 97, 98, 99, or I will generate 100 when I don't want to. Is there a way to get a period that is uniform on 1 to N if N+1 isn't prime?
– Drew
Nov 25, 2023 at 11:14