Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Factoring may be easier than we think (2016)

math.mit.edu

Post reply on HN
Print view View original

91–100 of 174 posts

Re: Factoring may be easier than we think (2016)

#91

Post by Khoth »

mokus wrote: post #35
wbl wrote: post #19

Earlier quoted context omitted.

What is the extended Church-Turing thesis? We already know quantum computers give speedups beyond classical lower bounds.

Do we know that quantum effects will actually scale large enough to realize those speed ups for arbitrarily-large problems though?

To paraphrase stuff from Scott Aaronson that I can't find right now: The currently known laws of physics say yes, and nobody's proposed any new laws of physics consistent with current observations which say no and don't allow even more computing power.

Re: Factoring may be easier than we think (2016)

#92

Post by bobbylarrybobby »

shoes_for_thee wrote: post #57
mabbo wrote: post #51

Earlier quoted context omitted.

The altruistic answers have already been posted, so here's what the devil on my shoulder recommends: I'd start a darknet web service, paid in crypto currency, that decrypts RSA. I'd adjust the price regularly to maximize my profit. The world would go crazy and very rapidly upgrade all software to not use prime factoring based encryption. I'd retire early to some lovely place, and never, ever, tell anyone how I got al…

You're going to have to launder a lot of money. What's your strategy there?

Is it illegal to break encryption by brute force?

Re: Factoring may be easier than we think (2016)

#96

Post by RealityVoid »

aykevl wrote: post #14
waynecochran wrote: post #7

Imagine what you would do if you discovered how to factor efficiently? Think carefully. You now how the power to decrypt much of the world's banking and internet traffic and spoof certificates. There are forces in this world that would kill you to have this power. Would you publish your findings for everlasting fame? Would you sell it to the NSA for money (remember you can prove your power without releasing your algo…

I once asked this a cryptographer. His response was that he would do the following things (if I remember correctly): * Discuss the result with a few cryptographers he trusts, to check whether he didn't make a mistake and to make sure he's not the only one who knows about it. * Write a paper. Put in all kinds of silly things, because it will get published anyway. * Publish proof of having found the algorithm, together…

What would happen if you publish publicly? The cat's already out of the bag, they could not possibly want anything more from you, the info is out in the open. Obviously, this isn't ethical but math isn't illegal so there would be no legal consequences. You would be infamous.

No, I think this is a danger to you as long as you, and only you know about it.

Now, in the case you were to immediately publish this after you find out,same thing, you'd be safe. The fallout would be sub-optimal though, you would gain no immediate cash, but you would gain notoriety (maybe not the best kind) and you would give NSA and other intelligence agencies who presumably collected encrypted data for later deciphering. The internet security would probably be compromised for a couple of months, until new algos would be in place.

I am not a cryptographer and I just have minimal understanding of these things, but I'll take a crack at saying what could be done:

1) Tell no one. POC is sufficient to deomnstrate it working.

Ethical path goto 4

Unethical path:

2) Build a helper program that can easily crack keys on demand

3) Put it out on the darknet that you decrypt stuff for a steep fee. Get rich.

4) Publish the finding, do not provide the algo, focus on maintaining anonymity and having impeccable OPSEC. Provide proof.

This will mean that everybody knows how unsafe their infrastructure is and there will be maximum effort to move everything to something else. But the algo is still contained and people can not yet have the power, _you_ have it. This, of course exposes you to maximal risks but also maximizes your potential financial reward. Maybe someone will soon find a way to crack it too, and then your show is off. Or maybe they will never find it and you remain a mystery, the _one_guy who could brake prime factoring. (unlikely, considering the number of smart people on this earth)

Re: Factoring may be easier than we think (2016)

#97

Post by nneonneo »

carapace wrote: post #93

Purely tangential, speculative questions: If you did prove that P = NP would you tell anyone? If so, how? Why?

Yes, I’d check the proof with some trusted colleagues, because odds are I’m wrong and I’d want to know why.

P=NP is a very hard problem and there have been a lot of failed solutions (including some that are flawed for very subtle reasons that can be easy to overlook). Even many famous, well known people have fallen into the trap of thinking they have a viable solution.

Re: Factoring may be easier than we think (2016)

#98

Post by nneonneo »

waynecochran wrote: post #7

Imagine what you would do if you discovered how to factor efficiently? Think carefully. You now how the power to decrypt much of the world's banking and internet traffic and spoof certificates. There are forces in this world that would kill you to have this power. Would you publish your findings for everlasting fame? Would you sell it to the NSA for money (remember you can prove your power without releasing your algo…

“Efficiently” has multiple meanings. In the context of P and NP, “efficiently” just means in P - it says nothing about how hard the algorithm would actually be to implement, nor how expensive the computation actually would be. O(n^100) is in P, but it’s thoroughly impractical in practice, even for the NSA.

Indeed, the authors who proved that primality testing was in P did so with, IIRC, an O(n^12) algorithm (with n being the number of bits), which is not much use in practice. Although, in that case the result was already widely suspected to be true, and fast, randomized (non-deterministic but highly accurate) polynomial-time algorithms were already known.

Re: Factoring may be easier than we think (2016)

#99

Post by scottlocklin »

daveFNbuck wrote: post #31
wbl wrote: post #19

Earlier quoted context omitted.

What is the extended Church-Turing thesis? We already know quantum computers give speedups beyond classical lower bounds.

It's basically that BPP captures all realistic polynomial-time computations. The speedup would have to be sufficient to show something like a problem in BQP that isn't in BPP. I don't think anyone has been able to show that unconditionally yet. You'd also need to accept that Quantum computers are realistic, which is why Aaronson's trilemma includes quantum computers being impossible.

This sort of statement is exactly why serious people shouldn't take "quantum complexity theory" seriously. The complexity class BQP is bullshit: there are no quantum computers, the end.

Feel free to prove me wrong by building one which does useful calculations. No time limit, until you die, in which case "time's up."

Edit add for downvoters: the strong Church Turing thesis is also almost certainly, and very obviously bullshit. How does that make you feel?

Post reply on HN