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.
Re: Time Expiry Alogorithm?? Valdis . Kletnieks (Nov 19)
Re: Time Expiry Alogorithm?? Gary E. Miller (Nov 20)