Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Let say we have $N=pq$ (Both $p$ and $q$ are safe primes, meaning $\gcd(p-1,q-1)=2$)
let's assume $e$ is an odd number which can be efficiently factored and assume that we know the $e$'th root of 1 modulo $N$ - call it $r$ - as well es $e$ and its prime-factorization. There is a claim that knowing the $e$'th root of 1 modulo $N$ we can find such $y>1$ and an odd prime $p_0$ such that $y^{p_0} = 1 \bmod N$.
How can we calculate $y$ and $p_0$?
If we know $e$, then it's easy.
If don't have to know the factors, but it does make it easier - as fgrieu pointed out, either $(p-1)/2$ or $(q-1)/2$ will appear as one of the prime factors, that will allow us to immediately recover $p, q$
Once we have that, then we know that we want:
$$y^{p_0} \equiv 1 \pmod p$$ $$y^{p_0} \equiv 1 \pmod q$$
If we have $y \equiv 4 \pmod p$ (or any other quadratic residue) and $p_0 = (p-1)/2$ (which is prime), then we satisfy the first equation.
If we have $y \equiv 1 \pmod q$, then we satisfy the second equation.
It's easy to find a $y$ that meets both modulii (as $p, q$ are relatively prime) using the Chinese Remainder Theorem, and so that's our answer.
We know by assumption that $$r^e\equiv 1\pmod N$$
then if $e$ is an odd prime, we're done and have $y=r, p_0=e$.
However if $e$ is a composite, it must only have odd prime factors - otherwise its factorization would contain $2$ which would make it even, so we arbitrarily pick any prime factor of $e$ and call it $p_0$ such that $e=e'p_0$. Then we're done with $y=r^{e'},p_0=p_0$ as $$r^{e}=r^{e'p_0}=\left(r^{e'}\right)^{p_0}\equiv 1\pmod N.$$
