29 ms·

Factoring may be easier than we think (2016)

dooglius 7y ago
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.
- whatshisface 7y ago
  If Bitcoin was broken it would instantly become worthless.
  - dumbfoundded 7y ago
    Not if you did it in a smart way. Let's say you could arbitrarily make transactions. Probably the best way to do it would be to steal all the coins from a particular exchange, like Coinbase. Then everyone would think Coinbase pwnd but bitcoin is fine. Rinse and repeat with other exchanges once a year and you can make a hefty profit.
- hackcasual 7y ago
  Bitcoin signatures rely on the difficulty of elliptic logarithms, not factoring, and only publish hashes of the public keys until they spend an address, meaning the vulnerable window is quite short as long as they never reuse private keys. The papers claim, that np but very likely not np-hard problems are likely to be in p is applicable though to breaking ECC
Jabbles 7y ago
Let's say a serious attempt consists of several months of work by an expert, someone who knows enough number theory to read the literature on this problem. Then the number of people who have seriously tried must be on the order of magnitude of 100. In academia, maybe. But I would not be surprised if millenia of experts' time has been spent on this problem in intelligence agencies.
- alexandercrohde 7y ago
  But if intelligence agencies broke factoring, would we know? Maybe they have.
  - goerz 7y ago
    Unlikely, as they wouldn’t keep using methods that they’ve broken themselves
    - cgriswald 7y ago
      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.
      - macintux 7y ago
        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.
        alfiedotwtf 7y ago
        Nice
    - OscarCunningham 7y ago
      They could switch algorithms and claim that they were just doing it to be resistant against quantum computers.
    - all2 7y ago
      That's not the case. With compartmentalization as a core organizational design, the people with the crack won't be saying anything to the operations and infrastructure folks. A key portion of an advantage like this would be who to share 1) derived intel and 2) capability with.
mabbo 7y ago
In a sense, this is terrifying. I mean, the math nerd in me is delighted at the idea, but in all practical senses if someone were to stumble upon and share a usably fast factoring algorithm tomorrow, the sky would fall. Sure, lots of crypto exists that isn't prime factoring based and we could move to that in a hurry- but it would be a lot like if we'd realized the Y2K problem on December 31st, 1999. Everything would need to be updated right now, immediately, today. And yet part of me is kind of excited it could happen.
- Mirioron 7y ago
  It wouldn't even be as tame as you mentioned. Any encrypted information that has been caught and stored would also become available.
waynecochran 7y ago
I have always wondered if the NSA has figured out how to factor effeciently.
- phicoh 7y ago
  One thing to remember here is that RSA can be used in 2 ways: to encrypt and to sign. If RSA is used to encrypt (for example if you send an encrypted message using PGP) then factoring directly breaks the encryption. In practice, a lot of encryption on the Internet uses RSA to sign the hash of a key obtained using Diffie-Hellman. In this case breaking RSA would allow the NSA to impersonate but not directly break existing communications. The problem with impersonation is that it is very noticeable. What I find odd about the linked article is that it only talks about factoring. In practice, the discrete log. problem is just as important and is very much related to factoring.
adamnemecek 7y ago
Fast factorization is going to be one of the killer apps of photonic computers.
- goerz 7y ago
  You mean quantum computing (for which photonics are not a leading candidate), or regular photonic computing? Because the latter doesn’t scale any better than normal computers.
waynecochran 7y ago
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 algorithm)? Would you use it for personal gain or power? Who would you tell first? Who do you trust?
- aykevl 7y ago
  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 with a hash of the paper. * Wait ~3 years until everyone has moved to a better algorithm. The normal responsible disclosure period is 3-6 months but this is so big it has to take a bit longer. * Publish the paper. I certainly think this is pretty dangerous. It may in fact be better to do the initial publication anonymously... and make sure you avoid all possible traces (the NSA will do everything in their power to get a hold of you).
  - seppel 7y ago
    > 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)
    - cococonspirator 7y ago
      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.
est31 7y ago
The US federal government once expended 10 percent of the US's electric energy supply in the Manhattan project for getting weapons grade nuclear material. This gives a rough ballpark for the amount of energy they are willing to invest into major strategic advancements. However, if you apply Landauer's principle, current factoring algorithms would require enough energy to boil all oceans on the earth, that's a lot even compared to the US's energy supply. So algorithmic improvements are the real danger basically. Even if we discovered a decryption method now, and immediately everyone stopped using RSA, there would still be an immense impact because all the past encrypted traffic that someone might have stored somewhere suddenly becomes decryptable. And usually, traffic from 20 years ago is still relevant today.
- 0xb100db1ade 7y ago
  > current factoring algorithms would require enough energy to boil all oceans on the earth, that's a lot even compared to the US's energy supply. Interesting. For what algorithm & key size? I'd love to quote this. I've heard it before but I don't remember the source.
  - est31 7y ago
    https://eprint.iacr.org/2013/635.pdf https://eprint.iacr.org/2013/635.pdf > Boiling all water on the planet (including all starfish) amounts to about 2^24 lakes of Geneva and leads to global security: 114-bit symmetric cryptosystems, 228-bit cryptographic hashes, 2380-bit RSA. This needs to be done 16 thousand times to break AES-128, SHA-256, or 3064-bit RSA. I think this paper isn't using Landauer's bounds though, but conventional computers. So maybe my claim was wrong, because we aren't 16 thousand times away from Landauer's bounds but millions [1]. [1]: https://web.archive.org/web/20141219043239/http://www.bloomfieldknoble.com/nanomagnet-memories-approach-low-power-limit/ https://web.archive.org/web/20141219043239/http://www.bloomf...
    - johndough 7y ago
      But why the starfish.
JPLeRouzic 7y ago
I am not a scientist, but in my team 15 years ago, many people much more talented than me were in love with public cryptography. For them encryption with a 1024 key was perfect, impossible to break. They did not even considered that several RSA challenges had already been found. Even if I had no education in mathematics I tried to show that in fact it was feasible to factor some enough large numbers with "bc" (using square root and a few other simple tricks) so the risk of having encryption broken by professionals was quite serious. My boss asked to another guy for its advice, which was essentially that for a start he would not try to break any encryption scheme anyway. And that was the end of the story. The unstated lesson was probably that there were no reason to expect a career boost by working on such topics.
- delinka 7y ago
  I'm not following your story. At the time when 1024-bit numbers used in RSA were 'perfect', it was infeasible to factor the number in a reasonable amount of time. The most straightforward approach is just to iterate over integers from 2 to your target number (call it n), and see if anything divides evenly. Now, you start looking for shortcuts. First, you can test only half the numbers, because the second half will give identical results (e.g. n=20, n/2 = 10; later, n/10 = 2; no need to even test the second half of the range.) Next, it becomes obvious that we only care about odd numbers (if it's divisible by an even number, it's divisible by two); but really, when it comes down do it, we only care about prime factors (for one thing, all non-primes can be decomposed into prime factors; for another, we used prime numbers to get n.) And lastly, for the simple shortcuts, you really only have to get to int(sqrt(n)) + 1 or so. So we've cut down the number of integers we have to divide with. Did we find the two prime factors of our n in a "reasonable" time? If so, just double the bit length to get a problem twice as hard. Every publicly-known shortcut to factoring large numbers just means you need to make your n larger to increase the workload on an attacker. The question then becomes: has anyone found a shortcut that will factor any number within a "reasonable" time? We don't know. As to your career-related comments, I read cluelessness from your boss, and carelessness from the 'other guy' - if OG "would not try to break any encryption scheme," then he's not the person whose advice you want about the strength of cryptosystems. Your boss just lacked critical thinking skills.
karmakaze 7y ago
With a grain of salt > Of course, I have no real evidence for my views: [...]
- garmaine 7y ago
  Whoosh. The point is that NOBODY has any real evidence either way, so one shouldn't have a strong default prior of the problem being truly "hard."
- 6gvONxR4sf7o 7y ago
  Might want to include context there: >Of course, I have no real evidence for my views; ... On the other hand, the people who talk about the great difficulty of factoring have equally little evidence.
  - karmakaze 7y ago
    When we talk about the 'difficulty of factoring' there's an implication. The direct meaning is that there may well be a simple algorithm for factoring that has yet to be discovered. No one disputes this. The implied idea is that this discovery could happen at any time and all things depending on it are at risk. This is also true but it's unreasonable to think that it is likely given that much effort has been put into this. Yes we don't know, but two unknowns are not 50:50. Of course regardless of how you estimate its truth consider the cost of being wrong when using anything depending on it.
doubleunplussed 7y ago
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 is impossible. We certainly don't have a proof that no such algorithm exists.
- wbl 7y ago
  What is the extended Church-Turing thesis? We already know quantum computers give speedups beyond classical lower bounds.
  - daveFNbuck 7y ago
    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.
    - wbl 7y ago
      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.
      - nabla9 7y ago
        Grover's algorithm still takes exponentially many operations to solve a search problem that can be brute-forced in exponentially many steps. Much faster, but still in EXPTIME. No jump from exponential to polynomial complexity class.
    - scottlocklin 7y ago
      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 bullshit. How does that make you feel?
miccah 7y ago
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/master/README.md#performance https://github.com/mcastorina/wheel-factorization/blob/maste...
debatem1 7y ago
I think it's interesting how many people worry about factorization. A second preimage attack on SHA2 would be at least as dangerous, and nowhere near as many people know or care about its assumptions.
- hackcasual 7y ago
  Breaking hashes aren't a decision problem, so they're not directly comparable, but sha2 isn't on the same shaky mathematical ground that RSA is.
  - phicoh 7y ago
    SHA-2 was on related shaky ground. Remember that in relatively short significant advances were made in breaking MD-5 and SHA-1. SHA-2 is based on similar constructs as MD-5/SHA-1. For this reason the SHA-3 competition was started to find a new hash function based on different principles. In the end it was found that creating practical attacks for SHA-2 is too hard. But we don't know what the future will bring. The difference between RSA and SHA-2 is that RSA is a very nice mathematical structure and we are still learning a lot about (prime) numbers. In contrast, SHA-2 is weird structure that has to solve a hard problem. It is hard to attack.
naveen99 7y ago
The reason factoring is hard is because finding very large probably prime numbers is easier making number sieve based methods useless for the purpose of breaking large numbers used in cryptography.
webdva 7y ago
> The first thing to realize is that until the advent of public key cryptography in the 1970's, few people cared about factoring. Some people were interested in it for its intrinsic beauty, but nobody thought it was good for anything, and it certainly wasn't the notorious unsolved problem it is today. If anything, it was mildly obscure. "There is no branch of mathematics, however abstract, which may not some day be applied to phenomena of the real world." - Nikolai Ivanovich Lobachevsky Applied mathematics is a problem looking for a solution and pure or abstract mathematics is a solution looking for a problem. An instance of this is the extension of the set of complex numbers called the quaternions discovered long ago which eventually found their application in affairs that require the representation of orientations in three dimensions, such as in computer graphics. It seems here then that a motivated entrepreneur can establish a remunerative business should he or she find a solution to this prime factoring problem.
carapace 7y ago
Purely tangential, speculative questions: If you did prove that P = NP would you tell anyone? If so, how? Why?
- nneonneo 7y ago
  Yes, I’d check the proof with some trusted colleagues, because odds are I’m wrong and I’d want to know why. P=NP is a very hard problem and there have been a lot of failed solutions (including some that are flawed for very subtle reasons that can be easy to overlook). Even many famous, well known people have fallen into the trap of thinking they have a viable solution.
carapace 7y ago
You can build a machine with a laser and a big mirror.
kmill 7y ago
This is the Henry Cohn that recently received recognition for his work on optimal sphere packings in 8 and 24 dimensions: http://www.ams.org/journals/notices/201804/rnoti-p463.pdf http://www.ams.org/journals/notices/201804/rnoti-p463.pdf
dang 7y ago
Discussed at the time: https://news.ycombinator.com/item?id=12355431 https://news.ycombinator.com/item?id=12355431
go_ruby 7y ago
I would become a vigilante hacker, blackmailing the worlds most nefarius characters into servitude of myself forcing them to do good. Slowly moving their wealth into my control, then after a decade, cut their heads off.
JacksonGariety 7y ago
> Of course, I have no real evidence for my views... > On the other hand, the people who talk about the great difficulty of factoring have equally little evidence... This is a classic antinomy (paradox): one can argue indefinitely in either direction, because the question lies along the bounds of human reason (or so says Immanuel Kant). The two sentences above, in themselves, provide a bit of evidence of the impossibility of solving the problem, and at the same time provide evidence for the possibility of handling this problem as a significant phenomenon of pure mathematics. :) EDIT: I mean only that the insolubility of the problem may itself be of mathematical use: it may (insofar as it is unsolvable, and insofar as it appears to be soluble) amount to a kind of 'anchor' for mathematics, a marker that indicates the boundary of the mathematical sciences, and that such a boundary would be of tremendous import to mathematicians and philosophers. Why is _this_ problem, _this_ problem specifically, unsolvable? (Rather than some other problem that has been solved?) tl;dr The question of "why have we have trying to solve this problem for millennia?" is perhaps more significant for mathematics than the solution to the problem.
PhantomGremlin 7y ago
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) https://en.wikipedia.org/wiki/Sneakers_(1992_film)

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.

whatshisface 7y ago
If Bitcoin was broken it would instantly become worthless.
- dumbfoundded 7y ago
  Not if you did it in a smart way. Let's say you could arbitrarily make transactions. Probably the best way to do it would be to steal all the coins from a particular exchange, like Coinbase. Then everyone would think Coinbase pwnd but bitcoin is fine. Rinse and repeat with other exchanges once a year and you can make a hefty profit.
hackcasual 7y ago
Bitcoin signatures rely on the difficulty of elliptic logarithms, not factoring, and only publish hashes of the public keys until they spend an address, meaning the vulnerable window is quite short as long as they never reuse private keys. The papers claim, that np but very likely not np-hard problems are likely to be in p is applicable though to breaking ECC

Jabbles 7y ago

Let's say a serious attempt consists of several months of work by an expert, someone who knows enough number theory to read the literature on this problem. Then the number of people who have seriously tried must be on the order of magnitude of 100. In academia, maybe. But I would not be surprised if millenia of experts' time has been spent on this problem in intelligence agencies.

alexandercrohde 7y ago
But if intelligence agencies broke factoring, would we know? Maybe they have.
- goerz 7y ago
  Unlikely, as they wouldn’t keep using methods that they’ve broken themselves
  - cgriswald 7y ago
    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.
    - macintux 7y ago
      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.
      - alfiedotwtf 7y ago
        Nice
  - OscarCunningham 7y ago
    They could switch algorithms and claim that they were just doing it to be resistant against quantum computers.
  - all2 7y ago
    That's not the case. With compartmentalization as a core organizational design, the people with the crack won't be saying anything to the operations and infrastructure folks. A key portion of an advantage like this would be who to share 1) derived intel and 2) capability with.

mabbo 7y ago

In a sense, this is terrifying. I mean, the math nerd in me is delighted at the idea, but in all practical senses if someone were to stumble upon and share a usably fast factoring algorithm tomorrow, the sky would fall. Sure, lots of crypto exists that isn't prime factoring based and we could move to that in a hurry- but it would be a lot like if we'd realized the Y2K problem on December 31st, 1999. Everything would need to be updated right now, immediately, today. And yet part of me is kind of excited it could happen.

Mirioron 7y ago
It wouldn't even be as tame as you mentioned. Any encrypted information that has been caught and stored would also become available.

waynecochran 7y ago

I have always wondered if the NSA has figured out how to factor effeciently.

phicoh 7y ago
One thing to remember here is that RSA can be used in 2 ways: to encrypt and to sign. If RSA is used to encrypt (for example if you send an encrypted message using PGP) then factoring directly breaks the encryption. In practice, a lot of encryption on the Internet uses RSA to sign the hash of a key obtained using Diffie-Hellman. In this case breaking RSA would allow the NSA to impersonate but not directly break existing communications. The problem with impersonation is that it is very noticeable. What I find odd about the linked article is that it only talks about factoring. In practice, the discrete log. problem is just as important and is very much related to factoring.

adamnemecek 7y ago

Fast factorization is going to be one of the killer apps of photonic computers.

goerz 7y ago
You mean quantum computing (for which photonics are not a leading candidate), or regular photonic computing? Because the latter doesn’t scale any better than normal computers.

waynecochran 7y ago

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 algorithm)? Would you use it for personal gain or power? Who would you tell first? Who do you trust?

aykevl 7y ago
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 with a hash of the paper. * Wait ~3 years until everyone has moved to a better algorithm. The normal responsible disclosure period is 3-6 months but this is so big it has to take a bit longer. * Publish the paper. I certainly think this is pretty dangerous. It may in fact be better to do the initial publication anonymously... and make sure you avoid all possible traces (the NSA will do everything in their power to get a hold of you).
- seppel 7y ago
  > 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)
  - cococonspirator 7y ago
    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.

est31 7y ago

The US federal government once expended 10 percent of the US's electric energy supply in the Manhattan project for getting weapons grade nuclear material. This gives a rough ballpark for the amount of energy they are willing to invest into major strategic advancements. However, if you apply Landauer's principle, current factoring algorithms would require enough energy to boil all oceans on the earth, that's a lot even compared to the US's energy supply. So algorithmic improvements are the real danger basically. Even if we discovered a decryption method now, and immediately everyone stopped using RSA, there would still be an immense impact because all the past encrypted traffic that someone might have stored somewhere suddenly becomes decryptable. And usually, traffic from 20 years ago is still relevant today.

0xb100db1ade 7y ago
> current factoring algorithms would require enough energy to boil all oceans on the earth, that's a lot even compared to the US's energy supply. Interesting. For what algorithm & key size? I'd love to quote this. I've heard it before but I don't remember the source.
- est31 7y ago
  https://eprint.iacr.org/2013/635.pdf https://eprint.iacr.org/2013/635.pdf > Boiling all water on the planet (including all starfish) amounts to about 2^24 lakes of Geneva and leads to global security: 114-bit symmetric cryptosystems, 228-bit cryptographic hashes, 2380-bit RSA. This needs to be done 16 thousand times to break AES-128, SHA-256, or 3064-bit RSA. I think this paper isn't using Landauer's bounds though, but conventional computers. So maybe my claim was wrong, because we aren't 16 thousand times away from Landauer's bounds but millions [1]. [1]: https://web.archive.org/web/20141219043239/http://www.bloomfieldknoble.com/nanomagnet-memories-approach-low-power-limit/ https://web.archive.org/web/20141219043239/http://www.bloomf...
  - johndough 7y ago
    But why the starfish.

JPLeRouzic 7y ago

I am not a scientist, but in my team 15 years ago, many people much more talented than me were in love with public cryptography. For them encryption with a 1024 key was perfect, impossible to break. They did not even considered that several RSA challenges had already been found. Even if I had no education in mathematics I tried to show that in fact it was feasible to factor some enough large numbers with "bc" (using square root and a few other simple tricks) so the risk of having encryption broken by professionals was quite serious. My boss asked to another guy for its advice, which was essentially that for a start he would not try to break any encryption scheme anyway. And that was the end of the story. The unstated lesson was probably that there were no reason to expect a career boost by working on such topics.

delinka 7y ago
I'm not following your story. At the time when 1024-bit numbers used in RSA were 'perfect', it was infeasible to factor the number in a reasonable amount of time. The most straightforward approach is just to iterate over integers from 2 to your target number (call it n), and see if anything divides evenly. Now, you start looking for shortcuts. First, you can test only half the numbers, because the second half will give identical results (e.g. n=20, n/2 = 10; later, n/10 = 2; no need to even test the second half of the range.) Next, it becomes obvious that we only care about odd numbers (if it's divisible by an even number, it's divisible by two); but really, when it comes down do it, we only care about prime factors (for one thing, all non-primes can be decomposed into prime factors; for another, we used prime numbers to get n.) And lastly, for the simple shortcuts, you really only have to get to int(sqrt(n)) + 1 or so. So we've cut down the number of integers we have to divide with. Did we find the two prime factors of our n in a "reasonable" time? If so, just double the bit length to get a problem twice as hard. Every publicly-known shortcut to factoring large numbers just means you need to make your n larger to increase the workload on an attacker. The question then becomes: has anyone found a shortcut that will factor any number within a "reasonable" time? We don't know. As to your career-related comments, I read cluelessness from your boss, and carelessness from the 'other guy' - if OG "would not try to break any encryption scheme," then he's not the person whose advice you want about the strength of cryptosystems. Your boss just lacked critical thinking skills.

karmakaze 7y ago

With a grain of salt > Of course, I have no real evidence for my views: [...]

garmaine 7y ago
Whoosh. The point is that NOBODY has any real evidence either way, so one shouldn't have a strong default prior of the problem being truly "hard."
6gvONxR4sf7o 7y ago
Might want to include context there: >Of course, I have no real evidence for my views; ... On the other hand, the people who talk about the great difficulty of factoring have equally little evidence.
- karmakaze 7y ago
  When we talk about the 'difficulty of factoring' there's an implication. The direct meaning is that there may well be a simple algorithm for factoring that has yet to be discovered. No one disputes this. The implied idea is that this discovery could happen at any time and all things depending on it are at risk. This is also true but it's unreasonable to think that it is likely given that much effort has been put into this. Yes we don't know, but two unknowns are not 50:50. Of course regardless of how you estimate its truth consider the cost of being wrong when using anything depending on it.

doubleunplussed 7y ago

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 is impossible. We certainly don't have a proof that no such algorithm exists.

wbl 7y ago
What is the extended Church-Turing thesis? We already know quantum computers give speedups beyond classical lower bounds.
- daveFNbuck 7y ago
  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.
  - wbl 7y ago
    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.
    - nabla9 7y ago
      Grover's algorithm still takes exponentially many operations to solve a search problem that can be brute-forced in exponentially many steps. Much faster, but still in EXPTIME. No jump from exponential to polynomial complexity class.
  - scottlocklin 7y ago
    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 bullshit. How does that make you feel?

miccah 7y ago

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/master/README.md#performance https://github.com/mcastorina/wheel-factorization/blob/maste...

debatem1 7y ago

I think it's interesting how many people worry about factorization. A second preimage attack on SHA2 would be at least as dangerous, and nowhere near as many people know or care about its assumptions.

hackcasual 7y ago
Breaking hashes aren't a decision problem, so they're not directly comparable, but sha2 isn't on the same shaky mathematical ground that RSA is.
- phicoh 7y ago
  SHA-2 was on related shaky ground. Remember that in relatively short significant advances were made in breaking MD-5 and SHA-1. SHA-2 is based on similar constructs as MD-5/SHA-1. For this reason the SHA-3 competition was started to find a new hash function based on different principles. In the end it was found that creating practical attacks for SHA-2 is too hard. But we don't know what the future will bring. The difference between RSA and SHA-2 is that RSA is a very nice mathematical structure and we are still learning a lot about (prime) numbers. In contrast, SHA-2 is weird structure that has to solve a hard problem. It is hard to attack.

naveen99 7y ago

The reason factoring is hard is because finding very large probably prime numbers is easier making number sieve based methods useless for the purpose of breaking large numbers used in cryptography.

webdva 7y ago

> The first thing to realize is that until the advent of public key cryptography in the 1970's, few people cared about factoring. Some people were interested in it for its intrinsic beauty, but nobody thought it was good for anything, and it certainly wasn't the notorious unsolved problem it is today. If anything, it was mildly obscure. "There is no branch of mathematics, however abstract, which may not some day be applied to phenomena of the real world." - Nikolai Ivanovich Lobachevsky Applied mathematics is a problem looking for a solution and pure or abstract mathematics is a solution looking for a problem. An instance of this is the extension of the set of complex numbers called the quaternions discovered long ago which eventually found their application in affairs that require the representation of orientations in three dimensions, such as in computer graphics. It seems here then that a motivated entrepreneur can establish a remunerative business should he or she find a solution to this prime factoring problem.

carapace 7y ago

Purely tangential, speculative questions: If you did prove that P = NP would you tell anyone? If so, how? Why?

nneonneo 7y ago
Yes, I’d check the proof with some trusted colleagues, because odds are I’m wrong and I’d want to know why. P=NP is a very hard problem and there have been a lot of failed solutions (including some that are flawed for very subtle reasons that can be easy to overlook). Even many famous, well known people have fallen into the trap of thinking they have a viable solution.

carapace 7y ago

You can build a machine with a laser and a big mirror.

kmill 7y ago

This is the Henry Cohn that recently received recognition for his work on optimal sphere packings in 8 and 24 dimensions: http://www.ams.org/journals/notices/201804/rnoti-p463.pdf http://www.ams.org/journals/notices/201804/rnoti-p463.pdf

dang 7y ago

Discussed at the time: https://news.ycombinator.com/item?id=12355431 https://news.ycombinator.com/item?id=12355431

go_ruby 7y ago

I would become a vigilante hacker, blackmailing the worlds most nefarius characters into servitude of myself forcing them to do good. Slowly moving their wealth into my control, then after a decade, cut their heads off.

JacksonGariety 7y ago

> Of course, I have no real evidence for my views... > On the other hand, the people who talk about the great difficulty of factoring have equally little evidence... This is a classic antinomy (paradox): one can argue indefinitely in either direction, because the question lies along the bounds of human reason (or so says Immanuel Kant). The two sentences above, in themselves, provide a bit of evidence of the impossibility of solving the problem, and at the same time provide evidence for the possibility of handling this problem as a significant phenomenon of pure mathematics. :) EDIT: I mean only that the insolubility of the problem may itself be of mathematical use: it may (insofar as it is unsolvable, and insofar as it appears to be soluble) amount to a kind of 'anchor' for mathematics, a marker that indicates the boundary of the mathematical sciences, and that such a boundary would be of tremendous import to mathematicians and philosophers. Why is _this_ problem, _this_ problem specifically, unsolvable? (Rather than some other problem that has been solved?) tl;dr The question of "why have we have trying to solve this problem for millennia?" is perhaps more significant for mathematics than the solution to the problem.

PhantomGremlin 7y ago

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) https://en.wikipedia.org/wiki/Sneakers_(1992_film)