Invent an efficient method to factor an RSA modulus of the form $n=pq$, if you happen to know that $p$ and $q$ are consecutive primes.

Bound the (expected or absolute) running time of your algorithm (as a function of the log of the input size).
(You might want to do some research on the distribution of prime to help)

  • $\begingroup$ And what is your question? If you expect us to solve this homework assignment for you, well, this isn't that type of service. If you have tried something, and gotten stuck, we might be willing to help... $\endgroup$ – poncho Oct 5 '17 at 18:03
  • $\begingroup$ I suggest using something like the term "factor RSA consecutive primes" in your searches. $\endgroup$ – SEJPM Oct 5 '17 at 18:18

This looks like a homework question, so I will just give some hints.

  1. If the primes are consecutive, what does it tell about their relative distance, i.e. the value of $|p-q|$ ?

  2. If primes are close, what is the relation of $p$, $q$ and $\sqrt{N}$ ?


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.