0
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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)$
$\endgroup$
  • $\begingroup$ This is right when $p_0$ and $q_0$ are known. $\endgroup$ – Lisbeth Jun 19 '16 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 '16 at 11:03

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.