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.
_______________________________________________
Gnupg-users mailing list
Gnupg-users@gnupg.org
http://lists.gnupg.org/mailman/listinfo/gnupg-users
