Re: [Newbie] Prime factorization question

From: Foo Bar (foobar965_at_hotmail.com)
Date: 10/10/03 

Date: Fri, 10 Oct 2003 13:39:00 GMT

Mxsmanic <mxsmanic@hotmail.com> writes:

> Gregory G Rose writes:
>
> > I think you have a problem understanding large
> > numbers. Yes, there is a chance of it happening.
> > But probably not in this universe.
>
<SNIP>
>
> If so, then I presume that a modulus that has more than two factors
> (i.e., that is the product of something other than exactly two primes)
> would still work for RSA, but with a far greater likelihood of failure,
> and with far greater susceptibility to cracking through factorization.

RSA Multiprime and the Takagi scheme.

> And conversely, it would also mean that even with ideal prime factors,
> RSA is not completely sound, because it can still fail if one of the
> factors of the modulus is also a factor of the message being encrypted.

Sure. This translates into a well known factoring algorithm for
factoring n:

1. Choose a number m<n
2. Check if gcd(m,n) > 1
3. Repeat

Do you think this is an efficient algorithm for RSA sized numbers? How
is the (in)efficiency of this algorithm related to the probability of
the failure you note?

/FB 

-- 
Foo Bar (foobar965@hotmail.com)

Relevant Pages