Skip to main content
19 events
when toggle format what by license comment
Nov 16, 2021 at 14:55 history edited kjetil b halvorsen CC BY-SA 4.0
fixed silly typo
Apr 20, 2018 at 10:53 history edited Martin Sleziak CC BY-SA 3.0
minor typo
Jan 21, 2018 at 17:32 comment added Christopher King @NajibIdrissi part of correction for these algorithms is not only the correct result, but also correct security properties.
Jan 21, 2018 at 17:31 comment added Najib Idrissi The algorithm would "work" correctly, it would simply be easier to bypass...
Jan 21, 2018 at 15:28 comment added Christopher King @NajibIdrissi for a security algorithm to work correctly, malicious agents mustn't have access to it. This might not be the case if $P=NP$.
Jan 21, 2018 at 8:13 comment added Najib Idrissi What machine depends on $P \neq NP$ for its correct functioning? This sentence confuses me. The fact that these machines seem to work correctly would then prove the conjecture...?
Jan 20, 2018 at 0:02 comment added Christopher King @Wojowu most applied mathematicians do assume this though, which was sort of the point. It probably wouldn't immediatly break all security, but it would at least require cryptographers to redo and recheck all their algorithms (and rethink how to prove an algorithm secure).
Jan 20, 2018 at 0:02 comment added DanaJ Using the AKS algorithm from the paper on a 1000 digit input, r ~ 11 million. This means you loop 11 million times, each one doing a modular exponentiation on a degree-11-million polynomial. With Bernstein's 4.1 variant there are fewer than 1 million loops, but we also have loads of upfront trial division and Fermat tests required.
Jan 19, 2018 at 22:10 comment added Wojowu @Bakuriu I haven't implemented it myself, but other people did and they have researched the real-time running time. I have found this plot, which indicates that even for a 100-digit prime the AKS running time gets into hours.
Jan 19, 2018 at 22:03 comment added DanaJ @Bakuriu, you keep saying this, but you have never shared your results. These numbers you give are wildly different than any other published results. It is stunningly easy to write an incorrect AKS implementation that looks like it works, but isn't actually the AKS test.
Jan 19, 2018 at 22:02 comment added Bakuriu @Wojowu I have implemented AKS and used it on numbers from hundreds to 10k digits without many issues. It runs in the order of seconds to some minutes so it is not impractical, just slower. If you need such numbers for real-time encrypted sockets it's too slow, but it's fine for creating certificates/ssh keys (it could even take an hour it would not make much difference in that case).
Jan 19, 2018 at 21:35 comment added Wojowu @Bakuriu I have never heard of using AKS for generating RSA primes, to my knowledge probabilistic algorithms are used. Do you have a reference for AKS being used?
Jan 19, 2018 at 21:30 comment added Bakuriu @Wojowu AKS can be used with numbers with thousands of decimal digits. sure, you are not going to find the biggest prime in this way but it can be 100% used for practical applications like generating RSA keys etc. So: I think you chose a bad example for a big constant algorithm...
Jan 19, 2018 at 8:24 comment added Wojowu Of course this is your question and your rules, but my understanding of how the question is posed is that all that should matter is the conjecture itself, not hypothetical means of its (dis)proofs. By themselves, P=NP and its negation have basically zero impact on security, for reasons in my other comment.
Jan 19, 2018 at 0:15 history made wiki Post Made Community Wiki by Todd Trimble
Jan 18, 2018 at 21:31 comment added Christopher King @CarloBeenakker That's why I said "depending on the details of the proof".
Jan 18, 2018 at 21:29 comment added Wojowu I second Carlo's comment. Just knowing that P=NP doesn't let us (for example) factor numbers effectively, for a variety of reasons. Among others, 1. the proof might not be constructive, so it doesn't give us a relevant algorithm, 2. the polynomial algorithm might have horrible constant which make it unusable in practice (that happened with AKS primality test, which, while polynomial time, is to this day too slow to be remotely efficient).
Jan 18, 2018 at 21:26 comment added Carlo Beenakker I think you are confusing $P=NP$ with "we can efficiently solve all NP problems".
Jan 18, 2018 at 21:19 history answered Christopher King CC BY-SA 3.0