# $f : \mathbb{Z}_n \rightarrow \mathbb{Z}^\times_n$?

Is there any function $f : \mathbb{Z}_n \rightarrow \mathbb{Z}^\times_n$ that is invertible?

By invertible, I mean it given $y \in \mathbb{Z}^\times_n$, it should be easy to find $x \in \mathbb{Z}_n$ such that $f(x)=y$.

-
Of course there are. A trivial example is the identity function except $f(0) = 1$. –  Henrick Hellström Feb 24 '14 at 16:32
@sadnoe : You also need to give us an idea of what you mean by "invertible". 'How' invertible does it need to be? Also, this graph might help: you're going to have trouble making an invertible function with such a difference –  figlesquidge Feb 24 '14 at 17:10
If it does invalidate the 'invertible' term, then, by the pigeon hole principle, there are no functions that satisfy the criterion in the question. –  Henrick Hellström Feb 24 '14 at 17:12
Sounds like we have an answer for both possible definitions of "invertible". 1) yes - with 2 examples; 2) no - by the pigeon hole principle. –  mikeazo Feb 24 '14 at 17:14
Please clarify your question. As it stands, your parenthesis does not correspond to any notion of inversion that I am familiar with. Also please define your notation, e.g., the $\mathbb{Z}_n^\times$ notation. And why is this a cryptography question? Please add some context or motivation, and tell us what you've tried to do on your understand to figure out the answer for yourself. Have you reviewed standard material on modular arithmetic? –  D.W. Feb 24 '14 at 17:53

Firstly, $|\mathbb Z_n|=n$, whereas $|\mathbb Z_n^*|=\varphi(n)<n$. So, by the pigeon-hole principal there cannot be a mathematically invertible function $f:\mathbb Z_n\to\mathbb Z_n^*$.

So, lets relax our idea of what 'invertible' means a bit. How about ensuring every element of $\mathbb Z_n^*$ has a preimage? Yep, we can do that. To use a couple of examples from my and Henrick's comments: $$f(x)=\begin{cases} 1 & x|0 \\x &\text{else} \end{cases} \qquad\text{or}\qquad g(x)=\begin{cases} g(x+1) & x|0 \\x & \text{else} \end{cases}$$ The first is much easier to study. With the exception of $1$, each preimage is unique, which is nice. However, $1$ may have an incredibly large number of preimages (roughly $n-\varphi(n)$). By contrast, the second scheme should mitigate this difficult behaviour at zero, but you pay for it by sacrificing the uniqueness of other preimages.

Just what sort of scheme you require (and if such a scheme exists) really does depend on your specific use case.

One possible use might be that you have to invert the function $f$, and you have a second function that will confirm if you have the 'correct' preimage. In this case, an intuitive inverter would be return $x$ if $x\neq1$, or if $x=1$ sequentially test all possible preimages.

How bad would the 'brute force' section of these algorithms be? Well,$n+1-\phi(n)$ (ie the number of preimages of zero) is maximal when $\phi(n)$ is minimal and is always less than $n$. However, for certain 'bad' choices of $n$ (values who's prime factors occur with small exponents) this value may (compared to $n$) be very small indeed.

-
The value of $n - \varphi(n)$ is highest for $n$ that consist of a product of the smallest primes, each with exponent $1$. For $n = 2\times3\times5\times7\times11\times13\times17\times19\times23$ it is approximately $5/6$. –  Henrick Hellström Feb 24 '14 at 17:57
Also, testing if $x|0$ is just a matter of testing if $GCD(x,n) = 0$. –  Henrick Hellström Feb 24 '14 at 18:01
Re 1: for 2^n it's half. Re #2: I don't see your point? Certainly they are Quick to calculate, but inverting is harder –  figlesquidge Feb 24 '14 at 18:05
If $GCD(x-1,n) \neq 0$, then $f^{-1}(x) = x$. Otherwise, if $GCD(x-2,n) \neq 0$, then $f^{-1}(x) = \{x-1,x\}$ etc. I think this recursion has an estimate worst case running time of $ln(n)$. –  Henrick Hellström Feb 24 '14 at 18:11
$n$ that is a product of the smallest primes is a 'worse' case than powers of $2$. –  Henrick Hellström Feb 24 '14 at 18:16