This problem was posed during a recently ended contest.

  • I am given a value for n and e. e = 65537. n is a 2048-bit number.
  • p is a 1024-bit prime number.
  • q is the modular inverse of e mod p. That's the mistake made in this problem. q is also non-prime.

Can I use this knowledge to simplify my calculation of the totient function?

  • $\begingroup$ Can you share which contest this is from? $\endgroup$
    – yyyyyyy
    Jun 28, 2022 at 15:19
  • $\begingroup$ @yyyyyyy: Gladly! Azure Assassin Alliance 2022 CTF. $\endgroup$ Jun 28, 2022 at 15:23
  • 1
    $\begingroup$ This is not important to the solution, but the key generation ensures that q is chosen to be prime $\endgroup$ Jun 28, 2022 at 15:53

1 Answer 1


Note that $q = e^{-1}\bmod p$ means there exists an integer $k$ such that $qe = 1 + kp$. Hence $$ne = pqe = p\cdot(1+kp)/e\cdot e = p + kp^2 \,\text. \label{n-eq}\tag{$\ast$}$$

From $qe=1+kp$, we further get $$1 \leq k = (qe-1)/p \leq pe/p = e = 65537 \,\text.$$

Thus, to recover $p$, we can iterate over all possible values of $k$ — between $1$ and $65537$ — and try to solve the quadratic equation $\eqref{n-eq}$ over the integers each time.

  • $\begingroup$ My math is a little shaky. For future reference could you explain how you went from qe=1+kp to 1≤k=(qe−1)/p≤pe/p. $\endgroup$ Jun 28, 2022 at 16:19
  • $\begingroup$ No worries. I'll work it out eventually. $\endgroup$ Jun 28, 2022 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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