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 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
Current thread:
- Re: Time Expiry Alogorithm??, (continued)
- Re: Time Expiry Alogorithm?? Andrew Farmer (Nov 20)
- Re: [Full-Dev-Server] Time Expiry Alogorithm?? Michael Simpson (Nov 19)
- Re: Time Expiry Alogorithm?? Pavel Kankovsky (Nov 19)
- Re: Time Expiry Alogorithm?? Anders Langworthy (Nov 19)
- Re: Time Expiry Alogorithm?? Andrew Farmer (Nov 20)
- Re: Time Expiry Alogorithm?? Anders Langworthy (Nov 20)
- Re: Time Expiry Alogorithm?? Anders Langworthy (Nov 20)
- Re: Time Expiry Alogorithm?? Pavel Kankovsky (Nov 21)
- RE: Time Expiry Alogorithm?? Tiago Halm (Nov 21)
- Re: Time Expiry Alogorithm?? Andrew Farmer (Nov 21)
- Re: Time Expiry Alogorithm?? Anders Langworthy (Nov 19)
- Re: Time Expiry Alogorithm?? Georgi Guninski (Nov 22)
- Re: Time Expiry Alogorithm?? Florian Weimer (Nov 22)
- Re: Time Expiry Alogorithm?? Andrew Farmer (Nov 23)
- Re: Time Expiry Alogorithm?? Florian Weimer (Nov 23)
- Re: Time Expiry Alogorithm?? Andrew Farmer (Nov 23)
- Re: Time Expiry Alogorithm?? Florian Weimer (Nov 29)
- Re: Time Expiry Alogorithm?? Pavel Kankovsky (Nov 23)
- Re: Time Expiry Alogorithm?? Vincent Archer (Nov 22)
- Re: Time Expiry Alogorithm?? Gautam R. Singh (Nov 20)