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

  • $\begingroup$ This follows immediately from the claim that it is injective (no collisions) by the pigeonhole theorem. The process of finding an actual inverse depends on finding an inverse of 479 mod 10000. Once you have that, use the same process (multiply by inverse, and mod 10000) to get the original number. $\endgroup$ – Mario Carneiro Dec 11 '12 at 23:09

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.

  • $\begingroup$ The internet is amazing, and so are you sir. $\endgroup$ – Simon Cave Dec 12 '12 at 0:00

Your Answer

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

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