1

I am trying to map the integers in [0, 999,999] to themselves uniquely, using something a little more advanced than n -> (na + b) mod 1,000,000, where a and b are positive integers and a and 1,000,000 are relatively prime.

How do I find a polynomial of degree > 1 such that, for each integer n in [0, 999,999], (a[0] + a[1] n + a[2] n^2 + ... + a[k] n^k) mod 1,000,000 returns a unique integer, given k > 1, all a[] values are integers, and a[k] > 0?

Don Del Grande
  • 111
  • You seem to mean "to positive integers", not "to themselves", and that different inputs give different outputs. – zyx Nov 03 '16 at 18:17

2 Answers2

1

$f(x) = 100000\,{x}^{3}+200000\,{x}^{2}+100001\,x+300000$ will do.

EDIT: Note that $f(x) = 10^5 g(x) + x$, where $g(x) = x^3 + 2 x^2 + x + 3$. The $g$ doesn't really matter, any polynomial with integer coefficients would do!

If we write $x = 10 y + j$, $y \in \{0, \ldots, 99999\}$, $j \in \{0,\ldots, 9\}$, then $g(x) \equiv g(j) \mod 10$ and $f(x) \equiv 10^5 g(j) + 10 y + j \mod 10^6$. To get any value $f(x) \equiv z \mod 10^6$, take $j$ so $j \equiv z \mod 10$, and then you just need $y \equiv (z-j)/10 - 10^5 g(j)$.

For a maybe slightly more impressive-looking example, try $f(x) = 10 x^3 + 20 x^2 + 11 x + 30$. The reason this works is just slightly more complicated. Again, we could actually use $f(x) = 10 g(x) + x$ for any polynomial $g$ with integer coefficients.

Suppose $f(x) \equiv f(y) \mod 10^6$. Since $f(X) \equiv X \mod 10$, that implies $x \equiv y \mod 10$. Let $k$ be the greatest integer such that $x \equiv y \mod 10^k$. I claim $k \ge 6$. Since $x \equiv y \mod 10^k$, $g(x) \equiv g(y) \mod 10^k$. Thus $f(x) - f(y) = 10 (g(x) - g(y)) + (x-y) \equiv (x-y) \mod 10^{k+1}$, so if $k < 6$ we would get $f(x) - f(y) \not \equiv 0 \mod 10^6$, contradiction.

A still more sophisticated example is $f(x) = 6 x^6 + 2 x^3 + x $. A reason this works is that on the integers mod $10$, $f$ is one-to-one with $\gcd(f'(x),10) = 1$.

Robert Israel
  • 448,999
0

You are probably looking for something simpler, and I think there is probably a cleaner solution, but I don't know enough number theory to give it. But I wanted to point out that you can use Lagrange polynomials to get any such map, if you are willing to have a 999,999th-order polynomial. Randomly shuffle the integers in your list, apply the Lagrange polynomial construction, and expand each term to get $a_k$.

Of course, as I said, this probably won't work for you, because, among other things, you will run into huge numerical issues. Evaluating $\text{999,999}^\text{999,999}$ is problematic, for example (though you only need it $\text{mod 1,000,000}$, so it might be okay).

sasquires
  • 1,650
  • Calculating a^b mod c (for positive integers a, b, c) is easy (otherwise, things like RSA would be far too time-consuming); convert b to binary, then, starting with x = 1, and taking each binary digit in b starting with the leftmost 1, replace x with (x^2 mod c), then, if the binary digit is 1, replace x with (ax mod c). – Don Del Grande Nov 03 '16 at 17:00
  • @DonDelGrande: You're right. I was not thinking (imagining doing arithmetic in a completely naive way) when I was thinking about the computational difficulties involved. But suffice to say, this solution is still much more computationally intensive than one would expect from, say, an answer using a low-order (e.g. quadratic) polynomial. – sasquires Dec 05 '16 at 05:44