$\begingroup$

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 hash function. Each input within the range maps to another integer within the range without collisions.

prime = 479
range = 10000
shuffle(input, prime, range) = (input * prime) % range

An input of 123 with a prime of 479 in a range of 10000 will return 8917.

Is this function reversible? Given the output, the range and the prime, can I determine the original input (123)?

$\endgroup$ 1

1 Answer

$\begingroup$

Assuming your givens (prime and range) are not known beforehand, the simplest way to compute the inverse of prime is the Euclidean algorithm, which involves repeated application of the division algorithm. Example:

$$10000=479\cdot20+420$$ $$479=420\cdot1+59$$ $$420=59\cdot7+7$$ $$59=7\cdot8+3$$ $$7=3\cdot2+1$$

Thus, $$1=7-3\cdot2$$ $$1=7-(59-7\cdot8)\cdot2=7\cdot17-59\cdot2$$ $$1=(420-59\cdot7)\cdot17-59\cdot2=420\cdot17-59\cdot121$$ $$1=420\cdot17-(479-420\cdot1)\cdot121=420\cdot138-479\cdot121$$ $$1=(10000-479\cdot20)\cdot138-479\cdot121=10000\cdot138-479\cdot2881$$ $$1=10000\cdot(138-479)+479\cdot(10000-2881)=479\cdot7119-10000\cdot341$$

The last step is not part of the canonical Euclidean algorithm, but was done so that the coefficient of $479$ was in the range $[0,10000)$. The moral of the story is that $479\cdot7119=3410001$ so that $479\cdot7119\mod 10000=1$.

This means that if (123 * 479) % 10000 = 8917, then (8917 * 7119) % 10000 = 123.

$\endgroup$ 1

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy