# A number theory problem in RSA

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

• brute force search using c code? – super Feb 11 '20 at 18:02
• I suppose there must be a mathematical way and algorithm to calculate such values, and no brute force search ;) – arman haghighi Feb 11 '20 at 18:03
• Do we know $e$? If we do, and there's a non-trivial root of unity, then one of the prime factors $f$ of $e$ if $(p-1)/2$ or $(q-1)/2$, hence we can factor $N$, which makes the problem easier. – fgrieu Feb 11 '20 at 18:39
• @fgrieu: if we don't know $e$, then it might not be doable (e.g. if $e = (p-1)(q-1)$, then all values r.p. to $N$ are root of unity (although one could claim it fails the 'easy to factor' criteria). On the other hand, once we factor $N$, it's straight-forward from there... – poncho Feb 11 '20 at 18:47
• we know e and its factors – arman haghighi Feb 11 '20 at 19:01

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