Robert J. Hansen
rjh at sixdemonbag.org
Fri Nov 2 22:27:02 CET 2007
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.
More information about the Gnupg-users