Score:-5

RSA impossible to be factorized?

nl flag

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

kodlu avatar
sa flag
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.
poncho avatar
my flag
Actually, it's a fairly simple syllogism: "all primes are odd; all RSA modulii are odd; hence all RSA modulii are prime..."
fgrieu avatar
ng flag
Example: [RSA-250](https://en.wikipedia.org/wiki/RSA_numbers#RSA-250).
Score:1
in flag

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.

Score:0
it flag

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.

fgrieu avatar
ng flag
Counterexample: `p`=2 (which is prime), `q`=3 (which is prime), 2×3=6 (which is not odd).
Andre Coelho avatar
nl flag
THANKS dudes :)
Match Man avatar
it flag
> Counterexample: p=2 (which is prime), """" Fixed now.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.