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

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

#171

Post by phkahler » Tue, Jul 02, 2019, 12:46 AM UTC

dvdkhlng wrote: post #148

phkahler wrote: post #146

Earlier quoted context omitted.

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

>> I.e. if you could do DLP in polynomial time, then also factoring becomes polynomial

That is what I remembered. You don't need Shor's Algorithm though. DLP would help finding roots, in particular if the log of a number is even, you can compute the square root of the original number which is useful for finding quadratic congruences (the goal of the quadratic sieve). The reverse (factoring enables DLP) does not appear to be true.

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

#172

Post by pas » Tue, Jul 02, 2019, 6:56 AM UTC

garmaine wrote: post #87

DanBC wrote: post #25

Earlier quoted context omitted.

> it went over a century as one of mathematics hardest unsolved problems, and in reality all it took was one guy dedicating a couple of months of exclusive work to it. Six years, not a couple of months. There were plenty of people who tackled this problem and who failed to make any headway. {Edit: I phrased this last sentence really clumsily, sorry.}

By his own report, it was a few months of tackling the problem from various angles until he found the pathway that would eventually bear fruit, and formalizing that and fixing little problems along the way was what the next six years were spent on.

He was the lucky one. Many many mathematicians thought they saw a path. And spent years. And it did not lead anywhere/there in the end.

See also the many P = NP proof attempts. (Sure, most of them are complete crackpot garbage, but that doesn't mean serious attempts are not made, and probably more serious attempts are made that then go nowhere so the author doesn't disclose it.)

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

#173

Post by doubleunplussed » Tue, Jul 02, 2019, 1:48 PM UTC

scottlocklin wrote: post #169

doubleunplussed wrote: post #165

Earlier quoted context omitted.

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

I asked you elsewhere in the thread what odds you're willing to bet at, so absolutely I'm willing to put my money where my mouth is. I'll happily bet that there will be a demonstration of 'quantum supremacy' within 20 years - that is, a quantum computer computing something faster than a classical computer, whether it's Grover's algorithm or factoring or something else. Let's say by the 1st of July 2039.

I'm not super confident there will be quantum computers, whereas you seem very confident there will not be. What do you think the probability of quantum supremacy within 20 years is? If you think it's 5 % and I think it's 50 %, perhaps we can take the geometric mean and bet at 6:1 odds (~15% chance).

Will you give me those odds? Let's say I stake $200. Then I'd give you that if I lose, and you'd give me $1200 if I win. Or we can increase the amount a bit. Today's dollars, we can inflation adjust since it'll be 20 years.

The terms might sound favourable to me, but you seem very confident that there won't be quantum computers ever, so less than 15% chance in the next 20 years seems consistent with your belief.

I wouldn't know how to put the bet on a blockchain, but if you know about that and want to, I'm happy. Otherwise I am happy to just take your word.

We can also shorten the duration of the bet, but I would want to shift the odds a bit since although I think quantum computers have a decent chance of being possible, there is considerable uncertainty in how long it would take to get to the point of demonstrating quantum supremacy. Probably I would accept doubling the odds if the duration of the bet were halved and so on.

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

#174

Post by scottlocklin » Wed, Jul 03, 2019, 11:44 AM UTC

doubleunplussed wrote: post #173

scottlocklin wrote: post #169

Earlier quoted context omitted.

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

I asked you elsewhere in the thread what odds you're willing to bet at, so absolutely I'm willing to put my money where my mouth is. I'll happily bet that there will be a demonstration of 'quantum supremacy' within 20 years - that is, a quantum computer computing something faster than a classical computer, whether it's Grover's algorithm or factoring or something else. Let's say by the 1st of July 2039. I'm not super…

We'd need a hard definition of "quantum supremacy" -I believe there have been several press releases claiming this already, and I think you agree with me that there are no such machines at hand.

There's this ethereum thing called Augur we could use to place the bet, though that's an interesting bet in itself (ethereum and auger being around in 20 years is not a sure thing). I suppose also "long bets." If you google my name you can find my contact info.