# 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. Commented Nov 23, 2023 at 12:46
• – D.W.
Commented Nov 24, 2023 at 23:57