Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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$.

share|improve this question
2  
Of course there are. A trivial example is the identity function except $f(0) = 1$. –  Henrick Hellström Feb 24 at 16:32
2  
@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 at 17:10
1  
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 at 17:12
2  
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 at 17:14
2  
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 at 17:53

1 Answer 1

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.

share|improve this answer
    
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 at 17:57
    
Also, testing if $x|0$ is just a matter of testing if $GCD(x,n) = 0$. –  Henrick Hellström Feb 24 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 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 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 at 18:16

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.