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

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

#41

Post by [deleted] » Sun, Jun 30, 2019, 3:52 PM UTC

0815test wrote: post #36

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

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

[deleted]

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

#42

Post by wbl » Sun, Jun 30, 2019, 3:56 PM UTC

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.

That's true but Grover search shows that quantum computers can give big speedups so I don't know why I would believe BPP=BQP.

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

#43

Post by OscarCunningham » Sun, Jun 30, 2019, 3:58 PM UTC

goerz wrote: post #13

alexandercrohde wrote: post #6

Earlier quoted context omitted.

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

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

They could switch algorithms and claim that they were just doing it to be resistant against quantum computers.

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

#44

Post by AlexCoventry » Sun, Jun 30, 2019, 4:00 PM UTC

williamstein wrote: post #40

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

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

I'm going to read your book, because your book with Mazur on the Riemann Hypothesis was incredible.

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

#45

Post by aewens » Sun, Jun 30, 2019, 4:01 PM UTC

zvrba wrote: post #37

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.

Interestingly, the consequence of releasing that algorithm would make having that private key insignificant since most schemas rely on factoring primes to secure the key pair.

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

#46

Post by miccah » Sun, Jun 30, 2019, 4:03 PM UTC

I did a toy project on wheel factorization if anyone is interested. Through it I learned some interesting math and ancient algorithms. It is by no means the cutting edge of factorization, but it was a fun little project.

https://github.com/mcastorina/wheel-factorization/blob/maste...

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

#47

Post by seppel » Sun, Jun 30, 2019, 4:15 PM UTC

cococonspirator wrote: post #38

seppel wrote: post #27

Earlier quoted context omitted.

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

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: https://en.wikipedia.org/wiki/RSA_numbers

You can factor, e.g, RSA-100 on a normal PC with state of the art algorithms in reasonable time.

That said, I had some new insight into factoring, and I was only a mere factor of one million away from factoring industrial crytography, I'd maybe try to optimize it a bit more.

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

#48

Post by emilfihlman » Sun, Jun 30, 2019, 4:18 PM UTC

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…

>to check whether he didn't make a mistake

No discussion needed. Simply MITM yourself or others in network to find out.

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

#49

Post by emilfihlman » Sun, Jun 30, 2019, 4:22 PM UTC

cococonspirator wrote: post #38

seppel wrote: post #27

Earlier quoted context omitted.

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

>If I could crack RSA keys for a mere one million times

You are off by many magnitudes. 1M is very little and equivalent computing power can be bought for a few tens of euros.

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

#50

Post by dooglius » Sun, Jun 30, 2019, 4:31 PM UTC

EDIT: this comment was mistaken, bitcoin uses elliptic curve based key pairs, as hackcasual points out below.

One thing to keep in mind:

Bitcoin wallets are implemented with public/private key pairs. If you believed that you had a method to crack that, well you probably couldn't just take all the bitcoin (people would notice and the market value would evaporate), but you could probably figure out a way to make at least 1% (a couple billion). So if it can be broken with a group of smart people thinking hard, that sounds like a startup opportunity.