Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If someone or some group found an efficient way to factor large composites with two distinct prime divisors, would this make it easier to decode any messages?

share|improve this question
Please add some details to your question: What cryptosystem are you using? – Paŭlo Ebermann May 2 '14 at 20:22
up vote 0 down vote accepted

I guess it depends on which scenario you are referring to. If it is RSA, being able to factorize $n = pq$ would compromise the security of that crypto-system.

This is because one could compute $\phi(n) = \phi(p)·\phi(q) = (p-1)·(q-1)$ since $p$, $q$ are two distinct primes and could calculate the private key $d$ from the public key $e$ by using the equation $e \cdot d = 1 \mod \phi(n)$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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