Home page logo

fulldisclosure logo 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 NP-complete.

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

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:


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

  By Date           By Thread  

Current thread:
[ Nmap | Sec Tools | Mailing Lists | Site News | About/Contact | Advertising | Privacy ]