>>7
I know, but I don't know any asymmetric cryptographic algorithm that relies on an EXPTIME-complete problem (actually, I don't know many problem in EXPTIME other than chess, go, and other board games, but that's my lack of education), so if P=NP all of them would break.
>>9
Problems in EXPTIME take O(2NK) time. I meant I don't know asymmetric cryptographic algorithms that rely on EXPTIME-complete problems, only on NP-complete ones.
Name:
Anonymous2011-07-17 12:09
>>10
There are asymmetric cryptography algorithms that are thought to be not in BQP. I don't remember any keywords though.
However it seems that P=NP breaks all asymmetric algorithms, because you can basically check all possible private keys to see if any matches the public key (and signature) as fast as you can decrypt/verify with a single key.
>>12 huh? >>6 This is a stupid question: no. Technically, any algorithm that uses factorization can be broken with a quantum computer.
As I said, not every asymmetric cryptography algorithm uses integer factorisation or discrete inverse logarithm that are solvable in polynomial time on Quantum Computers (theoretically).
Then, first, the precise relation between BQP (Bounded Quantum Polynomial) and NP is not known.
Second, BQP does not seem to allow you to "check all possible private keys to see if any matches the public key (and signature) as fast as you can decrypt/verify with a single key". It might be more powerful than NP in some cases (though not in integer factorization and such), but it seems to be less powerful for those other asymmetric cryptography algorithms.
>>13
The ``no'' was for Is it possible for any of them to survive to P=NP?
The rest was just a remark.
Name:
Anonymous2011-07-18 7:13
>>17 The ``no'' was for Is it possible for any of them to survive to P=NP?Think again. Assuming that NP-complete problems start getting solved by O(N2) algorithms, even if you build a 3SAT out of the relationships between the variables, the runtime will still be O(N2) relative to the runtime of the verifier algorithm.
Name:
Anonymous2011-07-18 7:49
>>17 The rest was just a remark.
You fundamentally misunderstand how discussion works, you poor autism. When someone asks "Is XYZ possible", the "No. Unrelated fact." is not a valid answer, even if XYZ indeed turns out to be impossible. Bare assertions add nothing to the discussion, neither the explanation why XYZ is impossible, nor even any confidence that XYZ is in fact impossible since you can be a lying autistic nigger.
>>18 Polynomial differences are usually disregarded, for obvious reasons. There is an intriguing possibility that the polynomial in question has a really really big degree, but that's not what OP asked.
>>19 Polynomial differences are usually disregarded, for obvious reasons. There is an intriguing possibility that the polynomial in question has a really really big degree, but that's not what OP asked.
I disagree. Even if there is a O(N6) algorithm that solves 3SAT (which implies that P=NP), it still won't break any of today's cryptosystems.
>>20
Why, it would take only few hours to crack a 1024 bit RSA key on some of the current most powerful supercomputers or several minutes on the bitcoin network (if they don't lie about their performance). I mean, it might turn out to be some months rather a few hours, or maybe just seconds instead, anyway, it's well within reach. And that's on a general-purpose hardware, without anything resembling such a strong incentive.
Name:
Anonymous2011-07-18 11:31
Chaparral slake mount! Persona weedy lanky. Predatory award prepare Swarthmore 10th tuba Meier.
Ferric high relay Carlo gunny sacral grumble Karachi participate mediocre. Corvus.
Name:
Anonymous2011-07-18 12:45
>>21
Excuse me. Allow me to fix my post: I disagree. Even if there is a O(N6) algorithm that solves 3SAT (which implies that P=NP), it still won't break any of today's cryptosystems except those based on factoring a rather large number -- every other cryptosystem I can think of has a gigantic logical circuit between the private and public components.
Name:
Anonymous2011-07-19 2:15
bump because I am a huge faggot please rape my face