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

31–40 of 174 posts

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

#31

Post by daveFNbuck »

wbl wrote: post #19
doubleunplussed wrote: post #12

I've heard the following called "Aaronson's trilemma": Either the extended Church-Turing thesis is false, or quantum computers are impossible, or...there exists a classical polynomial factoring algorithm that runs in polynomial time. One of these things must be true, and debates around quantum computing usually focus on the first two. But as argued, we don't have great reasons to believe factoring in polynomial time…

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.

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

#32

Post by nabla9 »

wbl wrote: post #19
doubleunplussed wrote: post #12

I've heard the following called "Aaronson's trilemma": Either the extended Church-Turing thesis is false, or quantum computers are impossible, or...there exists a classical polynomial factoring algorithm that runs in polynomial time. One of these things must be true, and debates around quantum computing usually focus on the first two. But as argued, we don't have great reasons to believe factoring in polynomial time…

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

The original Church-Turing thesis says nothing about computational complexity. Extended Church-Turing thesis says that all Turing machine equivalent computers can compute the same problems withing polynomial time.

Quantum computers are not known to be capable of solving NP-Complete problems in polynomial time.

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

#33

Post by Jabbles »

garmaine wrote: post #18
pas wrote: post #11

Earlier quoted context omitted.

I think that number (100) is a bit too low. There are students, graduates, post-grad fellows, and otherwise thousands of people living and breathing number theory. Sure, they might not directly stare at a blackboard with The Problem of Factoring staring back at them, but they are very much doing that indirectly. Just like the AKS primality testing algorithm depends on clever number theory, any progress, any new trick…

I think the core point of the OP you are missing is that he doesn't consider people indirectly, tangentially working on related things as doing "serious" work on factoring. I tend to agree. Look at Fermat's last theorem: 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. Factoring (and discrete log?) is…

in reality all it took was one guy dedicating a couple of months of exclusive work to it

This is wrong. Many professional mathematicians attacked the problem, and many useful discoveries were made before it was proved. For a brief summary, see https://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem#Early_...

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

#34

Post by komali2 »

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?

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

Very relevant, probably the Allie's breaking the Axis enigma code in WWII.

https://en.m.wikipedia.org/wiki/Ultra

If the NSA broke RSA, they'd have a similar program set up to ensure nobody notices.

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

#35

Post by mokus »

wbl wrote: post #19
doubleunplussed wrote: post #12

I've heard the following called "Aaronson's trilemma": Either the extended Church-Turing thesis is false, or quantum computers are impossible, or...there exists a classical polynomial factoring algorithm that runs in polynomial time. One of these things must be true, and debates around quantum computing usually focus on the first two. But as argued, we don't have great reasons to believe factoring in polynomial time…

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?

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

#36

Post by 0815test »

DanBC wrote: post #25
garmaine wrote: post #18

Earlier quoted context omitted.

I think the core point of the OP you are missing is that he doesn't consider people indirectly, tangentially working on related things as doing "serious" work on factoring. I tend to agree. Look at Fermat's last theorem: 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. Factoring (and discrete log?) is…

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

> There were plenty of people who tackled this problem and who failed to make any headway.

There was also plenty of meaningful progress throughout the 20th century at least, showing that the FLT was implied by other statements which would be easier to prove. Wiles's work was a follow-on to this progress; it's quite misleading to say that it "took" a single guy working over six years to prove FLT.

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

#37

Post by zvrba »

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 think there are only two safe options if your intention is to avoid being assassinated: 1) don't tell anyone, 2) publish it anonymously. If you want to be able to prove to somebody that you're the author, sign the paper and keep the private key offline on a piece of paper.

It'd be interesting if it could be used to manipulate voting results, but e-voting is still in its infancy.

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

#38

Post by cococonspirator »

seppel wrote: post #27
aykevl wrote: post #14

Earlier quoted context omitted.

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…

> Discuss the result with a few cryptographers he trusts, to check whether he didn't make a mistake Well, what kinds of mistakes can you make? Either it works or it doesnt. You (and everyone else) can verify that easily. (It might not work some numbers with special properties or so. But this does not matter if you can already break 99% of RSA keys)

You won’t necessarily be able to verify it works empirically, even if you can prove so analytically, because it would be a complexity bound that was broken. If I could crack RSA keys for a mere one million times the computational resources used to create them, that would be a groundbreaking result and I would have “broken RSA”, but _I_ still wouldn’t be able to crack any RSA keys at all.

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

#39

Post by MS-DDOS »

pmoriarty wrote: post #28
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…

This is the main reason that I don't store any of my sensitive data encrypted on cloud storage. If the encryption eventually gets cracked somehow, my data will be available not only to whoever owns, hacks, or otherwise compromises the cloud storage provider itself, but anyone who happened to have captured the traffic on any of the hops it went through on the way to the provider.

What if you encrypted using a symmetric key approach instead?

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

#40

Post by williamstein »

DanBC wrote: post #25
garmaine wrote: post #18

Earlier quoted context omitted.

I think the core point of the OP you are missing is that he doesn't consider people indirectly, tangentially working on related things as doing "serious" work on factoring. I tend to agree. Look at Fermat's last theorem: 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. Factoring (and discrete log?) is…

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

Also Andrew Wiles' six years of focused worked fundamentally depended on very deep work that Ken Ribet had just completed, which in turn relied on decades of highly nontrivial work by Mazur, Katz, and others on modular curves and modular forms, which made surprising connections with other areas of mathematics. Finally, Wiles' first announced proof of FLT was wrong, and Richard Taylor collaborated with him to find a correct and quite different proof. (Disclaimer: I published a book on modular forms, and cowrote papers with some of the people mentioned above.)
Post reply on HN