If the RSA numbers are odd, how can they be factorized by two primes, since a prime is only divisible by itself and 1?

  • 2
    $\begingroup$ I think you need to study some basic divisibility of integers. you have it reversed. the RSA moduli are not prime, they are products of two randomly chosen large primes. Maybe read the wikipedia pages on RSA and on factorisation at the very least. $\endgroup$
    – kodlu
    Sep 19 at 0:13
  • $\begingroup$ Actually, it's a fairly simple syllogism: "all primes are odd; all RSA modulii are odd; hence all RSA modulii are prime..." $\endgroup$
    – poncho
    Sep 19 at 3:05
  • $\begingroup$ Example: RSA-250. $\endgroup$
    – fgrieu
    Sep 19 at 8:46

All prime numbers other than 2 are odd. Yet the vast majority of odd numbers are not prime. E.g take the primes 3 and 5, their product is 15 and can be used as an (insecure) RSA modulus. 15 is an odd composite number. Composite means it has multiple prime factors. Natural numbers greater than 1 are all either prime or composite.

For secure RSA we use much larger primes. But the principle is the same We multiply to large odd primes and get a large odd composite modulus $n$.

Finding the factors of such a large composite can be very hard. In some cases beyond what is currently possible. But hard to factorize doesn't mean the factorization doesn't exist. And in fact with the help of the private key it's even easy.

So impossible to factorize might mean, not practical even by a nation state spending a billion dollars. With this definition RSA 4096 is impossible to factorize. But if you mean impossible as in not possible, even with unlimited compute, or a futuristic quantom computer. Than all RSA moduls are composite and thus possible to factorize.

P.s - factorize might be defined to allow "factorization" of primes, which is easy just detect that it is prime, using e.g Miller-Rabin and if so return a list containing only the input number.


A prime p greater than 2 multiplied by a prime q of course generate an odd number and not an even one, if you are talking about n.

2 is the only even prime, which makes it out of RSA scope anyway.

  • 2
    $\begingroup$ Counterexample: p=2 (which is prime), q=3 (which is prime), 2×3=6 (which is not odd). $\endgroup$
    – fgrieu
    Sep 19 at 8:44
  • $\begingroup$ THANKS dudes :) $\endgroup$ Sep 20 at 2:35
  • $\begingroup$ > Counterexample: p=2 (which is prime), """" Fixed now. $\endgroup$
    – Match Man
    Sep 20 at 18:44

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.