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

141–150 of 174 posts

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

#141

Post by empath75 »

gshubert17 wrote: post #135
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…

Author Charles Stross explored a similar question in his short story "Antibodies": what happens to encryption or machine intelligence when the proof that P == NP is published? https://www.antipope.org/charlie/blog-static/fiction/toast/t...

Nothing if it’s non constructive.

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

#142

Post by daveFNbuck »

scottlocklin wrote: post #116
daveFNbuck wrote: post #109

Earlier quoted context omitted.

Which statement are you saying demonstrates why people shouldn't take quantum complexity theory seriously?

BQP doesn't exist: there are no quantum computers. Saying BQP is like saying "magic fairy dust perfect unitary transformers that effectively encode a perfect complex number in the same sense a protractor theoretically can solve NP-complete problems by encoding real numbers."

So we shouldn't take research into things that don't exist yet seriously?

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

#143

Post by PhantomGremlin »

Nobody yet has mentioned a film that was premised on the invention of a black box "capable of breaking the encryption of nearly every computer system".

IIRC the movie plot was somewhat convoluted and confusing and I don't have any desire to see it again. I'm bringing it up because there are a number of "what would you do if" posts here.

In the end, the "sneakers" use the box to cause: the sudden bankruptcy of the Republican National Committee, and the simultaneous receipt of large anonymous donations by Amnesty International, Greenpeace, and the United Negro College Fund.

https://en.wikipedia.org/wiki/Sneakers_(1992_film)

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

#144

Post by inflatableDodo »

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…

You show it to someone in Hollywood and they then go and make the film 'Sneakers', probably. https://www.imdb.com/title/tt0105435/

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

#145

Post by inflatableDodo »

jahnu wrote: post #15
alexandercrohde wrote: post #6

Earlier quoted context omitted.

But if intelligence agencies broke factoring, would we know? Maybe they have.

If they have then they are using it exceedingly sparingly. I strongly suspect it would be impossible to use it to any moderate degree without being found out in one way or another. I know this is a very very poorly worded question :) but I wonder what the most amazing secret was that was held for the longest time?

>I wonder what the most amazing secret was that was held for the longest time?

I heard that the use of the golden ratio in projects such as the engineering of cathedrals, required that the first thing you do before you draw your plan is to draw a pentagram, in order to derive the ratio using simple drawing tools, and then carefully erase it, or in other words, make it occult. http://www.matematicasvisuales.com/english/html/geometry/gol...

Also, I'd really like to know who in the hell built the Ankythera device. https://en.wikipedia.org/wiki/Antikythera_mechanism

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

#146

Post by phkahler »

Ar-Curunir wrote: post #127
vbezhenar wrote: post #110

Earlier quoted context omitted.

1. Setup few servers operating in different countries, pay for a few years and set up a timer which will publish this algorithm on few public websites, then destroy all credentials, so it could not be undone. 2. Steal bitcoins from very old wallets with some small amounts. Supposedly those wallets are lost. Steal enough to have enough money to live a good life. Well, if for some reason I would have enough money, skip…

Factoring doesn't allow you to break discrete log; you won't be able to steal from old wallets.

It's been a long time since I looked at this but IIRC factoring and discreet log are equivalent.

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

#147

Post by inflatableDodo »

scottlocklin wrote: post #99
daveFNbuck wrote: post #31

Earlier quoted context omitted.

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…

I'm betting on n. Where n stands for us not fully understanding how causality works yet, or a lot about what the hell is going on in general. I'm also rooting for something interesting emerging unexpectedly from Umbral Moonshine, because who can't help but love the Monster Group? https://www.quantamagazine.org/mathematicians-chase-moonshin...

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

#148

Post by dvdkhlng »

phkahler wrote: post #146
Ar-Curunir wrote: post #127

Earlier quoted context omitted.

Factoring doesn't allow you to break discrete log; you won't be able to steal from old wallets.

It's been a long time since I looked at this but IIRC factoring and discreet log are equivalent.

It's also a long time since I looked at this, but I recall pretty clearly, that factoring is "easier" than DLP. "Easier" as in factoring is reducible [1] to the DLP.

I.e. if you could do DLP in polynomial time, then also factoring becomes polynomial (thanks to Shor's Algorithm [2]).

The reverse, however, is not currently known to be true AFAICS: having an oracle that computes the DLP does not help you to speed up factoring (at least not in a way that makes it polynomial).

[1] https://en.wikipedia.org/wiki/Reduction_(complexity)

[2] https://en.wikipedia.org/wiki/Shor%27s_algorithm

(EDIT: typo)

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

#149

Post by macintux »

cgriswald wrote: post #24
goerz wrote: post #13

Earlier quoted context omitted.

Unlikely, as they wouldn’t keep using methods that they’ve broken themselves

I doubt it, too; but using methods you've broken, but know others haven't, is a great way to convince people you haven't broken it either. And if you suspect they have, it's a great channel for misinformation.

You could also embed content with stronger security inside the wrapper you’ve broken, so even if someone else has figured it out, they can’t decrypt your real messages.

Hopefully.

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

#150

Post by ConcernedCoder »

vbezhenar wrote: post #110
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…

1. Setup few servers operating in different countries, pay for a few years and set up a timer which will publish this algorithm on few public websites, then destroy all credentials, so it could not be undone. 2. Steal bitcoins from very old wallets with some small amounts. Supposedly those wallets are lost. Steal enough to have enough money to live a good life. Well, if for some reason I would have enough money, skip…

possesses quite literally, the "keys to the kingdom"... steals lol
Post reply on HN