Question

is it true if there is no good way to factor large integers then rsa is guaranteed to be secure?

Answer 1

Two steps included in RSA algorithm are:-

• Choose 2 distinct prime number p & q.
• compute n=pq

Assume we have number 15 whose factors are 3 and 5. This is very simple for 15 as it is very small number but for large numbers there is no effective way to find their factors.

Now if we take a number 32

32=2^5 or 2*2*2*2*2

Now make possible combinations,

(32,0) / (2,16) / (4,8) / (8,4) / (16,2) / (32,0) & one of these combination must be right.

IT is complicated with bigger numbers too, but still quite easy. So basically if those numbers are not primes, then you can just split up n as much as possible and from there you have an easier way to find p and q. If both are primes you have to try values for p and q until you find exactly the right values.