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

  • $\begingroup$ brute force search using c code? $\endgroup$ – super Feb 11 '20 at 18:02
  • $\begingroup$ I suppose there must be a mathematical way and algorithm to calculate such values, and no brute force search ;) $\endgroup$ – arman haghighi Feb 11 '20 at 18:03
  • $\begingroup$ 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. $\endgroup$ – fgrieu Feb 11 '20 at 18:39
  • $\begingroup$ @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... $\endgroup$ – poncho Feb 11 '20 at 18:47
  • $\begingroup$ we know e and its factors $\endgroup$ – 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.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.