Re: [Full-Disclosure] Time Expiry Alogorithm??

On Sun, Nov 21, 2004 at 07:55:35PM +0100, Pavel Kankovsky wrote:
> > Mathematically, this is a very remote possibility, as factoring primes 
> > is probably an NP problem, and P is probably not NP.  Neither of these 
> > has been proven, however.
>
> According to my vague recollection of what I heard from people more 
> skilled at the complexity theory, P != NP implies the existence of an
> infinite scale of complexity classes between P and NP and factorization
> (of composite numbers of course, factorization of primes is trivial...
> unless you are Bill Gates (*)) is suspected to represent one of those
> classes more complex than P but less complex than NP-complete.

i admit i am crypto and math lamer, but i believe P vs NP just obfuscates the
problem.

would prefer to keep my secrets encrypted with algorithm whose breaking
requires *provable* average runtime x^4242 or even x^42 instead of 
*suspected runtime* 2^(x/4). (due to lameness the previous statement may be
incorrect but hope the idea is clear). afaik crypto algorithms don't exists
with provable average breaking time in suitable P.

is there any FAQ that explains this?

> (*) Bill Gates, "The Road Ahead," p. 265:
> The obvious mathematical breakthrough [to break modern encryption]
> would be development of an easy way to factor large prime numbers.

more quotes from this thought titan are available at:
http://en.wikiquote.org/wiki/Bill_Gates

-- 
georgi

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.netsys.com/full-disclosure-charter.html