Suppose $p_0$ and $q_0$ are known prime numbers and define $p_i$ and $q_i$ as follows:

$$p_{i+1} = next\_prime(p_i^2 + q_i^2), \qquad i \ge 0$$ and

$$q_{i+1} = next\_prime(2p_iq_i), \qquad i \ge 0$$ and $$N_{i+1} = p_{i+1}q_{i+1}, \qquad i \ge 0$$

I want to know is there efficient algorithm to factor $N_{i}$? What happen when the $p_0$ and $q_0$ be unknown? So can we factor an integer $N_1$ for example for unknown $p_0$ and $q_0$?


1 Answer 1


If $p_0$ and $q_0$ are known then so are $p_i$ and $q_i$ by iterating.

To factor $N$, do the following:

  1. $(p,q) \gets (p_0,q_0)$
  2. while ($p \nmid N$) do $(p,q) \gets (next\_prime(p^2+q^2), next\_prime(2pq))$
  3. Return $(p,q)$
  • $\begingroup$ This is right when $p_0$ and $q_0$ are known. $\endgroup$
    – Lisbeth
    Jun 19, 2016 at 6:43
  • $\begingroup$ @Lisbeth Welcome Lisbeth. Don't forget to accept if this is the right answer. You stated that $p_0$ and $q_0$ were known, right? $\endgroup$
    – Maarten Bodewes
    Jun 19, 2016 at 11:03

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.