[Courses] [security] Crypto Scientists Crack Prime Problem
raven at oneeyedcrow.net
Tue Aug 13 13:52:51 EST 2002
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