0
$\begingroup$

Why do we use prime factors in asymmetric algorithms compared to other factors?

For example:

lets say we use two prime numbers p = 53 and q = 59 our public key in RSA algorithm would be p * q = 3127

while it is difficult to find the private key from this using prime
factorisation, I feel it is equally difficult to find the factors for some normal number too

like p = 52, q = 58 where public key would be p * q = 3016

but why is prime number preferred over the others, is it because how the algorithm works? Think I am missing something trivial.

$\endgroup$
  • $\begingroup$ Well for one, I can tell by just looking at the last digit of your number that one of the factors is 2. $\endgroup$ – Maeher Apr 25 '18 at 6:43
  • $\begingroup$ sorry, but what does knowing 2 as one the factors has to do with the algorithm? should I not have to find 52 and 58 ? $\endgroup$ – par Apr 25 '18 at 6:53
  • $\begingroup$ Finding the factors of a normal number can be easier when the factors have more than two factors (a.k.a. are not prime), for example $52*58$ can also be represented by $2*26*58$ which again can be broken down to even smaller numbers which will eventually result in a bunch of prime numbers. However, when at least two prime factors are big, it is hard to find all factors. $\endgroup$ – VincBreaker Apr 25 '18 at 13:22
2
$\begingroup$

If one of the number has small factors, then it is easy to factorize everything. For example, $52 = 2 \times 2 \times 13$. Once this is computed, the other factor can also be found. Bottom line: factoring algorithms work very well when the prime factors are not too large, so the the "hardest" factoring problem is with two prime factors only (of equal size).

| improve this answer | |
$\endgroup$
3
$\begingroup$

The problem are not prime factors, the problem are large prime factors. There are many rather efficient factorization algorithms (such as Pollard's rho) that are good at finding small factors. Actually in RSA we want $p, q$ to be approximately of the same size so this disproportion cannot be leveraged to factor $p*q$.

If you have a $p, q$ primes then $p*q$ has only two factors, smallest one is equal to $p$ or $q$. If $p,q$ are composite then the smallest factor of $p*q$ is smaller (upper bound on the factor is only $min(\sqrt{p}, \sqrt{q})$). Thus using composite numbers reduces your problem to much smaller instance. Moreover if your numbers have really small factors (such as $2$) then the reduction is even more straightforward (e.g. I can decide to divide $3016$ by $8$ just by looking at binary representation of $3016$, then it remains to factor $377$ which is almost 10 times smaller).

| improve this answer | |
$\endgroup$

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.