2
$\begingroup$

If I have list of $n$ unbounded different random integers, is it always possible to find such integers $\alpha$, $\beta$ and $\gamma$, that function $$f(x)=((\alpha\times x+\beta)\mod\gamma)\mod n$$ will have different values for all numbers in the list?

If yes, is the same possible when $\beta=0$?

For example, for list $\{17, 1, 12, 4, 5, 0, 7\}$ such function exists:
$$f(x)=((25\times x)\mod29)\mod n$$ It returns following values: $\{5, 4, 3, 6, 2, 0, 1\}$.

However, for list $\{5, 13, 23, 37, 47, 61, 6, 7, 8, 9, 11, 12\}$ I'm not able to find such function, that means that there is no such or numbers are big enough to be not founded (I performed computer search for $0\lt\gamma\lt5000$). There must be problem in length $n=12$ and $61=12*5+1$, because when I change 61 to 62 - function is easy to find.

$\endgroup$
  • $\begingroup$ The values of $205x\mod 47$ are all different modulo $13$ for your list. $\endgroup$ – Steve Kass Apr 23 '15 at 21:36
  • $\begingroup$ @SteveKass That's cool, but I don't need $\mod13$, I need that last modulo is equal to length of list (12 in second example). EDIT: I've checked and it seems that they are not different - a lot of remainders repeat. $\endgroup$ – Somnium Apr 24 '15 at 6:32
  • $\begingroup$ Looks like I goofed up somewhere, sorry. Will check later when I'm back at the computer with my scratchwork file. $\endgroup$ – Steve Kass Apr 24 '15 at 17:30
  • 1
    $\begingroup$ I agree that there seems to be no perfect hash function here. Maybe this is worth posting again as a question about number theory or diophantine equations along the lines of “Sets $S\subset\mathbb{Z}$ where $f(x)=((a \times x)\mod b)\mod |S|$ is never one-to-one.” $\endgroup$ – Steve Kass Apr 25 '15 at 18:02

Your Answer

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

Browse other questions tagged or ask your own question.