Polynomial that maps an integer subset to itself 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?
 A: $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$.  
A: 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).
