RSA Weak?

[Robert J. Hansen]

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.

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

Like most math problems, there are certain special forms of problems
that are easier to solve than others.  If I ask you to factor
2,147,483,647, well, that might take you a very long time.

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.

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.