RSA Weak?

[Robert J. Hansen]

Alexander W. Janssen wrote:
> Apparently P and NP doesn't mean the same to you and me.

P:  the set of all decision problems that can be solved in polynomial
    time on a deterministic Turing machine.
NP: the set of all decision problems that can be solved in polynomial
    time on a nondeterministic Turing machine.

Equivalently:

NP: the set of all decision problems whose answers can be verified
    in polynomial time on a deterministic Turing machine.

We're handwaving a little bit by using phrases like P and NP to talk
about finding prime factors of composites.  Factorization is a function
problem as opposed to a decision problem; their analogues are FP and
FNP.  However, the logic still holds, since polynomial-time function
problems can be reduced in polytime to decision problems.

>> 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...

Not 'if they're special primes'.  /Any/ prime.  Factoring any prime is a
special case for factorization.  You don't have to do anything: you just
give the number back.