RSA	AllPages RecentChanges Links to this page Edit this page Search Entry portal Advice For New Users

The RSA PKC relies on the assumption that factoring integers in general is hard. But in general, for a given random integer it's easy to find a factor. So what does this mean, exactly?

It means that at a given size we can find an instance of integer factoring that is "hard" - i.e. takes a long time with current technology. So in general when we use RSA we take two large primes, but not too large, that are similar in size, but not too close, and which are such that $(p-1)/2$ doesn't have lots of small factors.

There are factoring techniques that work well on a product $pq$ if $p$ and $q$ are very close, or if $(p-1)/2$ has lots of small factors.

So:

• Factoring integers in general isn't difficult;
• We can construct examples that are difficult;
• RSA relies on that.

Details: https://en.wikipedia.org/wiki/RSA_(cryptosystem)