[Courses] [security] Crypto Scientists Crack Prime Problem

Raven Alder raven at oneeyedcrow.net
Tue Aug 13 13:52:51 EST 2002

Heya --

Quoth Mary (Tue, Aug 13, 2002 at 09:36:13PM +1000):
> 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.

	Yep.  Any number that can be divided into two smaller whole
numbers that are not 1 isn't prime.  Primes are by definition only
evenly divisible by themselves and one.  I didn't catch that error
when I read the article; thanks for pointing it out so we could
clear up any confusion. 

"Do you know where the RSA t-shirt is?"
"Well, I need the algorithm, so I'm doing laundry."
  -- me and RavenBlack

More information about the Courses mailing list