Full Disclosure
mailing list archives
Re: Time Expiry Alogorithm??
From: Georgi Guninski <guninski () guninski com>
Date: Mon, 22 Nov 2004 12:34:00 +0200
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 NPcomplete.
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
_______________________________________________
FullDisclosure  We believe in it.
Charter: http://lists.netsys.com/fulldisclosurecharter.html
By Date
By Thread
Current thread:
 Re: Time Expiry Alogorithm??, (continued)
