RSA Weak?

[Alexander W. Janssen]

On 11/2/07, Robert J. Hansen <rjh at sixdemonbag.org> wrote:
> Alexander W. Janssen wrote:
> >> Factoring prime numbers is most definitely in P.
> >
> > Hold on. Earlier you say "Factoring is known to be in NP". P is much
> > smaller. I'm not familiar to the latest outcomes. So what do you mean?
>
> If you have a proof that P is much smaller than NP, a million bucks is
> yours for the claiming.
>
> Factoring, in the general case, is in NP.

I think we have a problem in nomenclature. Or, let's say, I have one.
Apparently P and NP doesn't mean the same to you and me.
Considering that my complexity-classes are years ago and you seem to
know what you're talking about, I just assume you're right.
However, that means that I have to rethink everything I think to know...
Which is not a bad thing at all :)

> Factoring, /specifically applied to prime numbers/, is in Context-Free.

I still don't get what you mean with context-free in that context, but
I'll think about it.

> If I tell you that 2,147,483,647 is a prime number (the eighth Mersenne)
> and ask you to factor it, you don't have to do any computation at all:
> you just give the number back to me and you're done.  You can skip the
> entire computation step.

If they're special primes, that's for sure. Proved a long time ago...

> When numbers are in a special form, there often exist special purpose
> algorithms that are much more efficient than the general purpose
> algorithms one would otherwise be forced to use.

Right. But the p and q we use in RSA shouldn't be special :)

However. Since you just made me wonder about the meanings of P and NP,
I'll rethink and come back later.

Cheers, Alex.

-- 
"I am tired of all this sort of thing called science here... We have spent
millions in that sort of thing for the last few years, and it is time it
should be stopped."
 -- Simon Cameron, U.S. Senator, on the Smithsonian Institution, 1901.


.