# Carmichael's function in Cryptography

The Carmichael's function says that for $a\in \mathbb{Z}_n^*$, if $gcd(a,n)=1$, then $$a^{\lambda(n)} \equiv 1 \;(mod\; n).$$ My aim is to find $a$ if factorization of $n$ is known? Since it is a polynomial equation of degee $\lambda(n)$, so it has $\lambda(n)$ solution. Suppose any how we are able to find all solution of the equation, how can we find the exact $a$? Can any one help me to proceed further?

• What do you mean with find $a?$. All $a\in \mathbb{Z}_n^*$ are solutions, i.e. there are $\phi(n)$ solutions. – gammatester Jun 8 '16 at 8:15
• "Since it is a polynomial equation of degee λ(n), so it has λ(n) solution" No, it does not, because 1) $\mathbf{Z}_n$ is not an integral domain; and 2) there may be repeated roots. – fkraiem Jun 8 '16 at 9:18

If you are only given $a^{\lambda(n)} = 1$, then it is obviously impossible to recover $a$, since this is true for all $a$. To take a simpler example, say I tell you that the square of a number is $4$, and ask you to find what the number is. This is impossible, because you are not given enough information to tell whether the number is $2$ or $-2$.
• An example closer to the OP's question: Find $a$ given $a^0=1$. – CodesInChaos Jun 8 '16 at 10:28
• Suppose I have a relation $D=r^{2\lambda(n)}\; mod\;n$, where $D$ and factorization of $n$ is known and $r$ is chosen randomly from $QR_n$, the group of quadratic residues modulo $n$ and it is unknown. How to find this particular $r$? Is the above relation holds if and only if $D=1$? – Pinkimani Goswami Jun 8 '16 at 11:27
• @PinkimaniGoswami You have been told that $a^{\lambda(n)} \equiv 1 \pmod n$ for all $a \in \mathbf{Z}_n^*$; there is nothing more to say. You seem very weak in elementary number theory, so I suggest you study it seriously. – fkraiem Jun 9 '16 at 2:09