# factorization of an integer $N$ that is in special format

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

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)$
• This is right when $p_0$ and $q_0$ are known. – Lisbeth Jun 19 '16 at 6:43
• @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? – Maarten Bodewes Jun 19 '16 at 11:03