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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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)$
Improve this answer
$\endgroup$
2
  • $\begingroup$ This is right when $p_0$ and $q_0$ are known. $\endgroup$
    – Lisbeth
    Commented 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 ♦
    Commented Jun 19, 2016 at 11:03

Your Answer

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

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