1
$\begingroup$

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) ?

$\endgroup$
2

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Drew
    Nov 25, 2023 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.