# Is this function reversible?

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

-
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. –  Mario Carneiro Dec 11 '12 at 23:09

$$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$.