Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
The internet is amazing, and so are you sir. –  Simon Cave Dec 12 '12 at 0:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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