[Courses] [security] Crypto Scientists Crack Prime Problem

[Mary]

On Tue, Aug 13, 2002, Hamster wrote:
> I thought that if you multiplied *any* two numbers together, the
> result could *never* be prime because you now have instantly at least
> 4 factors - 1, itself and the two numbers you just multiplied.  Is
> this correct? Or have I somehow missed a second definition of prime?

No that's correct. In RSA, the two numbers are multiplied to produce a
large *composite* (not prime, has non-unit factors) number. Even before
this result, it was possibly to show that it is *likely* that number X
is a prime fairly quickly. The slow bit is factorising a large composite
number into its smaller prime factors, and this is why breaking RSA by
brute force is slow.

-Mary