Finding an efficient way to reverse the Carmichael Lambda function.

Question

Given 966, for example, the solution must quickly give 967, or 2021, or some other number x that satisfies λ(x) = n. The solution must also be close to the original number in size. example of a solution that generates number at an adequate speed, the numbers are simply too large. Thanks in advance! og post: anyone know an efficient way to reverse the carmichael lambda function

Answer 1

We know that for prime powers $p^k$, $$ \lambda(p^k)=\begin{cases}2^{k-2}&p=2, k\ge 3\\p^{k-1}(p-1)&\text{otherwise}\end{cases}$$ and for composite $m$, $\lambda(m)$ is the lcm of all $\lambda(p^k)$ with $p^k\mid m$.

Now for given $n$, this allows us to enumerate all $p^k$ that can occur as prime powers dividing $m$ with $\lambda(m)=n$:

For odd primes $p$ with $p^k\mid m$, we need $p-1\mid n$. Hence we may enumerate all even divisors $d$ of $n$ (i.e., enumerate all divisors of $\frac n2$ and double them - this requires complete factorization of $\frac n2$ and is hence not a fully trivial task) and check if $d+1$ is prime. for each such $p:=d+1$, $p$ is a candidate prime factor of $m$ and may occur in $m$ form $0$th power (i.e., not at all) up to $(k+1)$th power if $p^k\|n$. In fact, when looking for small $m$, you need not bother with intermediate powers: Either you do not need $p$ at all (and some other prime powers take care of the factor $p-1$ in $n$), or you need only $p$ to the first power (and some other prime power takes care of a possible $p^k$ occurring in $n$), or you need $p^{k+1}$. Once you have collected all possible prime powers (including the powers of $2$, which need to be treated slightly differently) that may occur in $m$, and you already have "for free" the prime factorization of these $\lambda(p^k)$ in terms of the primes occuring in $n$, it is a matter of dynamic programming to gather such prime powers with the goal of making the lcm of their $\lambda$ values (i.e., the component-wise max of the corresponsing prime exponents) equal to $n$.