From: jamesd@netcom.com (James A. Donald)
Date: Thu, 14 Jul 94 22:44:14 PDT
To: cypherpunks@toad.com
Subject: Re: Key length security (calculations!)
In-Reply-To: <199407141909.MAA01482@netcom9.netcom.com>
Message-ID: <199407150536.WAA26322@netcom8.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


Timothy C. May writes
> Factoring is suspected to be in the class NP (or
> even harder, some suspect), but it has not yet been proved to be so.

Those who have studied the matter generally believe that factoring
is NP, but is not NP complete.

Factoring cannot be "even harder than NP" since a simple minded
brute force attack is 2^(n/2), which is only NP

As Timothy May points out, if factoring is NP, then modest increases
in key length can easily defeat enormous improvements in factoring.


> ... if P = NP, then fast factoring
> methods may be found (fast = polynomial in length). 

In the highly unlikely event that P = NP then we have also solved, as
an almost trivial special case, the problems of true artificial
intelligence, artificial consciousness, and artificial perception,
and the failure of one particular form of crypto will not be noticed
in the midst of such radical changes.

-- 
 ---------------------------------------------------------------------
We have the right to defend ourselves and our
property, because of the kind of animals that we              James A. Donald
are.  True law derives from this right, not from
the arbitrary power of the omnipotent state.                jamesd@netcom.com