Factoring may be easier than we think (2016) • Hacker News Board

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

#161

Post by scottlocklin » Mon, Jul 01, 2019, 1:55 PM UTC

doubleunplussed wrote: post #155

scottlocklin wrote: post #116

Earlier quoted context omitted.

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."

The qbits and unitaries don't have to be perfect - it's about how things scale when you add qbits. Quantum error correction shows that you can add more qbits to make up for imperfection, and still be left with a quantum computer, i. e. the imperfection hasn't demoted the thing to a classical computer. Of course they haven't built one yet, but none of the difficulties encountered so far have involved discovering new p…

You've just regurgitated Aaronson's statement on the topic. Aaronson never studied physics, and has probably never fiddled with an op-amp or tried to make entangled anything in the world of matter. There's zero evidence quantum error correction will work; it's just an idea with no basis in the world of matter. There's zero evidence you can meaningfully and usefully manipulate quantum coherent states, let alone manipulate an exponentially huge number of them with a polynomially large number of computational elements, which is the essential claim of quantum computing. They make great claims: great claims need evidence; not theoretical wankery. Building a couple of scalable error corrected qubits would be a great start; it might even cause me to shut up about it.

Never in the history of the human race has something as complex as a computer architecture existed in the theoretical world before it exists in some form in the physical world, let alone one for which we define complexity classes.

The entire field is intensely silly, and the last time I said so in a public place, the waiter turned out to be some dude who just got his Ph.D. in the subject. He didn't agree with me exactly, but the fact the dude had a job bringing people steaks for a living is a decent argument I'm right.

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

#162

Post by waynecochran » Mon, Jul 01, 2019, 2:42 PM UTC

nneonneo wrote: post #98

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 b…

The primality test has been whittled down to O(n^6) ... it seems that solutions to problems in P with high degree always get optimized over time.

Also, even a O(n^100) sol'n is way better than O(2^n) since (usually) I can parallelize polynomial time algorithms to something more practical: e.g., http://cds.iisc.ac.in/faculty/vss/courses/PPP2014/projects/p...

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

#163

Post by cr0sh » Mon, Jul 01, 2019, 4:38 PM UTC

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 would publish it immediately, after checking as best I could that it was actually a working solution. But here's the twist:

I would publish it in such a way that it would appear to have been released/solved by the worst person I didn't like; a world-known dictator or similar would be ideal. Nobody would believe it, but maybe their narcissism wouldn't let them not play along. It very well might screw their life over in ways unknown.

The uproar around the world would be very interesting to watch.

But I'd definitely make sure I wasn't connected in any way - you would likely have a target on your head (because if you could do that - what else could you know or do?)...

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

#164

Post by simonebrunozzi » Mon, Jul 01, 2019, 5:29 PM UTC

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…

I am not sure I'd ever want to reveal my identity, ever. Becoming famous for something like this would make my life way too dangerous, forever.

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

#165

Post by doubleunplussed » Mon, Jul 01, 2019, 6:04 PM UTC

scottlocklin wrote: post #161

doubleunplussed wrote: post #155

Earlier quoted context omitted.

The qbits and unitaries don't have to be perfect - it's about how things scale when you add qbits. Quantum error correction shows that you can add more qbits to make up for imperfection, and still be left with a quantum computer, i. e. the imperfection hasn't demoted the thing to a classical computer. Of course they haven't built one yet, but none of the difficulties encountered so far have involved discovering new p…

You've just regurgitated Aaronson's statement on the topic. Aaronson never studied physics, and has probably never fiddled with an op-amp or tried to make entangled anything in the world of matter. There's zero evidence quantum error correction will work; it's just an idea with no basis in the world of matter. There's zero evidence you can meaningfully and usefully manipulate quantum coherent states, let alone manipu…

My arguments are my own. I am an atomic physicist, and I meaningfully and usefully manipulate coherent quantum states every day. Not for making a quantum computer mind you, but quantum states nonetheless. Quantum mechanics works. The atoms do exactly what the Schrödinger equation says they should, however much entanglement is added. We are yet to see it break down. Plenty of my colleagues are working on quantum computers, with atoms, ions, photons, and solid state systems, and from where I stand it doesn't look like nonsense. It looks steady progress, and if there are insurmountable barriers, they have not yet been encountered.

I am not certain that quantum computers are possible, but I am certain that you are wildly overconfident that they are not.

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

#166

Post by doubleunplussed » Mon, Jul 01, 2019, 6:07 PM UTC

scottlocklin wrote: post #160

daveFNbuck wrote: post #142

Earlier quoted context omitted.

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

Designing algorithms for a computer architecture that assumes matter behaves in a fairly trivially unphysical way sure seems like a glass bead game to me. Especially considering the hype and baloney around this particular one. There are zero actual quantum computer designs (aka error corrected and capable of factoring large or even small integers into primes) under construction: but everyone runs around like chicken…

At what odds would you bet that we won't see a quantum computer outperforming a classical computer on any problems in the next, say, 20 years?

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

#167

Post by hinkley » Mon, Jul 01, 2019, 7:31 PM UTC

Ar-Curunir wrote: post #133

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…

Most cryptanalytic advances occur in tiny baby steps; there's rarely a big break that entirely lowers a long-standing problem from hard to not-hard. Even when this occurs, the earliest iterations of these algorithms are intensely technical, and very slow. Of course, followup research often rapidly improves on these numbers, but that usually happens in collaboration with other authors. So all-in-all, it is unlikely th…

The odds that a modern genius will eclipse the work of 2200 years’ worth of previous work are far smaller.

Improve on the old record? Possible. Shatter it at this late date? That’ll take a mode of thinking that nobody has tried.

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

#168

Post by DoctorOetker » Mon, Jul 01, 2019, 8:25 PM UTC

empath75 wrote: post #141

gshubert17 wrote: post #135

Earlier quoted context omitted.

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.

... in the case of a non constructive proof, there would still be a significant change: it would dramatically ramp up the search for a constructive proof

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

#169

Post by scottlocklin » Mon, Jul 01, 2019, 10:27 PM UTC

doubleunplussed wrote: post #165

scottlocklin wrote: post #161

Earlier quoted context omitted.

You've just regurgitated Aaronson's statement on the topic. Aaronson never studied physics, and has probably never fiddled with an op-amp or tried to make entangled anything in the world of matter. There's zero evidence quantum error correction will work; it's just an idea with no basis in the world of matter. There's zero evidence you can meaningfully and usefully manipulate quantum coherent states, let alone manipu…

My arguments are my own. I am an atomic physicist, and I meaningfully and usefully manipulate coherent quantum states every day. Not for making a quantum computer mind you, but quantum states nonetheless. Quantum mechanics works. The atoms do exactly what the Schrödinger equation says they should, however much entanglement is added. We are yet to see it break down. Plenty of my colleagues are working on quantum compu…

How much money are you willing to stake on that statement? I'll make a market for you; if you think your education gives you an edge over the wildly overconfident guy -we can even stick it on a blockchain that is quantum future proof if you like. Your choice.

Saying "quantum mechanics works" is not the same as saying "I can manipulate exponential QM states with polynomial imperfect physical devices." In the early days, people sketched out optical quantum computers that totally worked, but had exponential growth in elements with quantum states. Which, I bet, is how the universe is always going to work.

Money where your mouth is: I haven't found any other good shorts for this shitty idea.

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

#170

Post by seppel » Mon, Jul 01, 2019, 11:48 PM UTC

enedil wrote: post #134

seppel wrote: post #47

Earlier quoted context omitted.

True, it could still be impossible to break RSA keys used in the wild with one normal PC. But still, you could factor smaller numbers faster than any other algorithm which would give you the confidence that it works. > _I_ still wouldn’t be able to crack any RSA keys at all. Everybody can crack RSA keys if the modulos is small enough. You just need to factor a number :) There actually nice list of numbers to try: htt…

In short, no. There's a reason that General Number Sieve is only used for numbers bigger that 10^80 and Elliptic Curve Method (ECM) is used instead. If number is smaller, than you don't benefit from the better complexity. This invalidates your point, because it might happen that your hardware is fast enough to factor a number using ECM and not fast enough to do the same with GNFS. So practically speaking, you don't h…

I agree in principle. But I disagree that you cannot test GNFS on small numbers. You can do this, but you are right that you might have trouble to easily verify that it has a better asymtotic complexity than other algorithms.