5 ms·

A New Provable Factoring Algorithm

59 points by mr_tyzic 12y ago

Sniffnoy 12y ago
I'm a little confused as to what distinction is being made here between "provable" and "unprovable" factoring algorithms. Is it just that "provable" ones may output the correct result all the time, while "unprovable" ones are probabilistic and output the correct result with high probability? (E.g., roughly the distinction between P or ZPP on the one hand and BPP on the other hand, if these hypothetically ran in polynomial time and we were talking about decision problems.) Or is something even weaker meant by "unprovable", like retuning possibly incorrect results based not on a random input but on the number to be factored? I assume it's the former -- if it were the latter I'd say such things are not really factoring algorithms, practically useful as they might be -- but the way it's worded isn't exactly clear.
- ColinWright 12y ago
  The following is general, and may be wrong in some details. I look forward to someone more knowledgeable than I coming along to fix it to be totally correct, but here are some of the ideas. The unprovable algorithm usually use randomness and/or rely for their correctness on unproved hypotheses, ... As an example, some algorithms rely on the Riemann Hypothesis for their correctness. ... yet are observed to be the fastest in practice for numbers of substantial size. The Pollard Rho algorithm is not a fast one, running in expected time proportional to the square root of the factor found, which is usually (but not always) the smallest factor. however, this effectively relies on the birthday problem, and is only a heuristic, not proven. It's also not guaranteed to factor the number at all. The provable algorithms are usually deterministic, but their key feature is that their correctness is unconditional. And their run time is proven without using unproven hypotheses.
  - pbsd 12y ago
    Nitpick: Pollard's rho is unproven not because it relies on the birthday paradox, but because there's no way to prove that f(x) = x^2 + a behaves like a random walk. It may not because, e.g, the length of the cycle may be the same for every prime divisor of the number being factored. Similarly, the complexity of the quadratic sieve is heuristic because there is no known way to prove that (sqrt(n) + i)^2 - n results in the same distribution of smooth integers than that of a random sequence of the same size. Dixon's algorithm [1] turns the quadratic sieve provable (but much slower in practice) by sampling randomly instead of sequentially. Sieving is thus no longer possible, but we get a subexponential running time of L_n[1/2, 2 sqrt(2)]. The hyperelliptic curve factorization algorithm [2, 3] is another probabilistic but provable algorithm with a more efficient but not provable counterpart, the elliptic curve method [4]. The blog post only seems to care about deterministic factoring algorithms, though. There are indeed no known deterministic factorization algorithms with better than exponential complexity. [1] http://www.ams.org/journals/mcom/1981-36-153/S0025-5718-1981-0595059-1/home.html http://www.ams.org/journals/mcom/1981-36-153/S0025-5718-1981... [2] https://math.dartmouth.edu/~carlp/hyperI.pdf https://math.dartmouth.edu/~carlp/hyperI.pdf [3] https://math.dartmouth.edu/~carlp/PDF/paper129.pdf https://math.dartmouth.edu/~carlp/PDF/paper129.pdf [4] https://openaccess.leidenuniv.nl/bitstream/handle/1887/3826/346_086.pdf?sequence=1 https://openaccess.leidenuniv.nl/bitstream/handle/1887/3826/...
    - ColinWright 12y ago
      Perfect - thank you.
    - Sniffnoy 12y ago
      Huh -- I had always assumed when people talked about e.g. GNFS being the fastest known, they meant proven. I had no idea about this, thank you.
- algorias 12y ago
  Well, in math some things are true but not provable unless our formal system is inconsistent. This is one of Gödel's incompleteness theorems. It's therefore not far fetched that some algorithms might in fact always work correctly, but at the same time a proof for their correctness doesn't exist. You can never be sure (literally!) that you're not just confusing it with an algorithm that's wrong but happens to work on all problem instances you've thrown at it so far. IIUC, when the article says unprovable, what it actually means is unproven. To correctly describe an algorithm as unprovable, you would have to have a proof of its unprovability, which would be quite something.
  - thaumasiotes 12y ago
    There's no obstacle in principle to proving that something can't be proved. As far as I understand things, the continuum hypothesis has been shown to be unprovable within ZFC (since ZFC is consistent with both the truth and the falsity of the continuum hypothesis, obviously it is unable to prove the hypothesis true or false), and theoretical computer science produces results of the form "to prove X, the following kinds of approaches cannot work".
    - JadeNB 12y ago
      "ZFC is consistent with …" must, of course, be replaced by "If ZFC is consistent, then so are …". In fact, singling out ZFC gives you another example of this kind of result: if ZF is consistent, then so are ZF+C and ZF-C.
      - thaumasiotes 12y ago
        That all depends whether you're comfortable saying a contradiction is "consistent" with an unrelated proposition; I don't see much of a problem with it. Contradictions, being impossible, are logically consistent with everything else. I guess unprovable propositions would switch over to being provable, though.
        JadeNB 12y ago
- deleted 12y ago
  [deleted]
h3xe 12y ago
I want to replace systems like AES with ones that uses the hardness of factoring for their security. Systems like AES rely on intuition and experimental testing for their security—there is not even a conditional proof that they are secure. 1) You can prove symmetric crypto is secure 2) In the light of (upcoming fast) factoring algorithms, using crypto that relies on factoring everywhere sounds very stupid.
- nhaehnle 12y ago
  Please point to a proof of the security of symmetric crypto if you can. Last I checked, such a proof would have still been considered an incredible breakthrough. All that people are doing is to show that k rounds of cypher C can be broken, where actual implementations use K > k rounds, and then arguing that nobody has been able to break more despite a lot of effort, cypher C is probably secure in practice. That is good evidence, but not a proof.
  - Groxx 12y ago
    One-time-use random data XOR your data = provably secure symmetric crypto, afaik. I could try to hunt down a proof of that one. Impractical, sure, but provable. Also afaik, others haven't been proven / can only be proven to have certain qualities, and leave gaps which have massive real-world implication. So yeah, I'm curious for other proofs too.
    - duaneb 12y ago
      One time pads are currently the only provable "unbreakable" encryption. The proof is trivial.
phkahler 12y ago
I found an algorithm to determine the parity (even or odd) of the number of factors in N. Never wrote about it because IDK if it's unique, and also because it's time complexity seems poor and I never tried to prove any upper bound or make it faster. Anyone know of something similar? Would this be interesting?
- pbsd 12y ago
  That is called the Liouville function; you might get luckier searching for that name. I don't know much about the state-of-the-art on computing it, but I found a description of such a method here, which may be a starting point to compare with: http://www.ams.org/journals/mcom/1960-14-072/S0025-5718-1960-0120198-5/ http://www.ams.org/journals/mcom/1960-14-072/S0025-5718-1960...
- damarquis 12y ago
  A fast algorithm for parity would be interesting. There is currently no better way to compute parity than factoring N. There is a well known hand wavy-argument that computing any function on the prime factors of arbitrary integers should be difficult. Very roughly the idea is that if you can compute such a function over the integers you can probably also compute it over other rings. Applying it over certain number fields would let you get information about the low bits of the prime factors which is thought to be hard. There is a bit more information given in Terrence Tao's answer here http://mathoverflow.net/questions/3820/how-hard-is-it-to-compute-the-number-of-prime-factors-of-a-given-integer http://mathoverflow.net/questions/3820/how-hard-is-it-to-com... His answer is about counting the number of distinct prime factors but I think that it can extended to the parity of this value as well.
  - phkahler 12y ago
    Thanks, the mathoverflow link was very informative. It's funny because I started out computing a number that I thought would be useful for factoring N, but it turned out that it would take one of 2 values depending if N was prime or had 2 factors (this is easily proven). Subsequent testing via software seemed to indicate it was actually determining the parity of the number of primes. I believe that's what it does in general but never bothered to go any further.

59 points by mr_tyzic 12y ago

I'm a little confused as to what distinction is being made here between "provable" and "unprovable" factoring algorithms. Is it just that "provable" ones may output the correct result all the time, while "unprovable" ones are probabilistic and output the correct result with high probability? (E.g., roughly the distinction between P or ZPP on the one hand and BPP on the other hand, if these hypothetically ran in polynomial time and we were talking about decision problems.) Or is something even weaker meant by "unprovable", like retuning possibly incorrect results based not on a random input but on the number to be factored? I assume it's the former -- if it were the latter I'd say such things are not really factoring algorithms, practically useful as they might be -- but the way it's worded isn't exactly clear.

ColinWright 12y ago
The following is general, and may be wrong in some details. I look forward to someone more knowledgeable than I coming along to fix it to be totally correct, but here are some of the ideas. The unprovable algorithm usually use randomness and/or rely for their correctness on unproved hypotheses, ... As an example, some algorithms rely on the Riemann Hypothesis for their correctness. ... yet are observed to be the fastest in practice for numbers of substantial size. The Pollard Rho algorithm is not a fast one, running in expected time proportional to the square root of the factor found, which is usually (but not always) the smallest factor. however, this effectively relies on the birthday problem, and is only a heuristic, not proven. It's also not guaranteed to factor the number at all. The provable algorithms are usually deterministic, but their key feature is that their correctness is unconditional. And their run time is proven without using unproven hypotheses.
- pbsd 12y ago
  Nitpick: Pollard's rho is unproven not because it relies on the birthday paradox, but because there's no way to prove that f(x) = x^2 + a behaves like a random walk. It may not because, e.g, the length of the cycle may be the same for every prime divisor of the number being factored. Similarly, the complexity of the quadratic sieve is heuristic because there is no known way to prove that (sqrt(n) + i)^2 - n results in the same distribution of smooth integers than that of a random sequence of the same size. Dixon's algorithm [1] turns the quadratic sieve provable (but much slower in practice) by sampling randomly instead of sequentially. Sieving is thus no longer possible, but we get a subexponential running time of L_n[1/2, 2 sqrt(2)]. The hyperelliptic curve factorization algorithm [2, 3] is another probabilistic but provable algorithm with a more efficient but not provable counterpart, the elliptic curve method [4]. The blog post only seems to care about deterministic factoring algorithms, though. There are indeed no known deterministic factorization algorithms with better than exponential complexity. [1] http://www.ams.org/journals/mcom/1981-36-153/S0025-5718-1981-0595059-1/home.html http://www.ams.org/journals/mcom/1981-36-153/S0025-5718-1981... [2] https://math.dartmouth.edu/~carlp/hyperI.pdf https://math.dartmouth.edu/~carlp/hyperI.pdf [3] https://math.dartmouth.edu/~carlp/PDF/paper129.pdf https://math.dartmouth.edu/~carlp/PDF/paper129.pdf [4] https://openaccess.leidenuniv.nl/bitstream/handle/1887/3826/346_086.pdf?sequence=1 https://openaccess.leidenuniv.nl/bitstream/handle/1887/3826/...
  - ColinWright 12y ago
    Perfect - thank you.
  - Sniffnoy 12y ago
    Huh -- I had always assumed when people talked about e.g. GNFS being the fastest known, they meant proven. I had no idea about this, thank you.
algorias 12y ago
Well, in math some things are true but not provable unless our formal system is inconsistent. This is one of Gödel's incompleteness theorems. It's therefore not far fetched that some algorithms might in fact always work correctly, but at the same time a proof for their correctness doesn't exist. You can never be sure (literally!) that you're not just confusing it with an algorithm that's wrong but happens to work on all problem instances you've thrown at it so far. IIUC, when the article says unprovable, what it actually means is unproven. To correctly describe an algorithm as unprovable, you would have to have a proof of its unprovability, which would be quite something.
- thaumasiotes 12y ago
  There's no obstacle in principle to proving that something can't be proved. As far as I understand things, the continuum hypothesis has been shown to be unprovable within ZFC (since ZFC is consistent with both the truth and the falsity of the continuum hypothesis, obviously it is unable to prove the hypothesis true or false), and theoretical computer science produces results of the form "to prove X, the following kinds of approaches cannot work".
  - JadeNB 12y ago
    "ZFC is consistent with …" must, of course, be replaced by "If ZFC is consistent, then so are …". In fact, singling out ZFC gives you another example of this kind of result: if ZF is consistent, then so are ZF+C and ZF-C.
    - thaumasiotes 12y ago
      That all depends whether you're comfortable saying a contradiction is "consistent" with an unrelated proposition; I don't see much of a problem with it. Contradictions, being impossible, are logically consistent with everything else. I guess unprovable propositions would switch over to being provable, though.
      - JadeNB 12y ago
deleted 12y ago
[deleted]

h3xe 12y ago

I want to replace systems like AES with ones that uses the hardness of factoring for their security. Systems like AES rely on intuition and experimental testing for their security—there is not even a conditional proof that they are secure. 1) You can prove symmetric crypto is secure 2) In the light of (upcoming fast) factoring algorithms, using crypto that relies on factoring everywhere sounds very stupid.

nhaehnle 12y ago
Please point to a proof of the security of symmetric crypto if you can. Last I checked, such a proof would have still been considered an incredible breakthrough. All that people are doing is to show that k rounds of cypher C can be broken, where actual implementations use K > k rounds, and then arguing that nobody has been able to break more despite a lot of effort, cypher C is probably secure in practice. That is good evidence, but not a proof.
- Groxx 12y ago
  One-time-use random data XOR your data = provably secure symmetric crypto, afaik. I could try to hunt down a proof of that one. Impractical, sure, but provable. Also afaik, others haven't been proven / can only be proven to have certain qualities, and leave gaps which have massive real-world implication. So yeah, I'm curious for other proofs too.
  - duaneb 12y ago
    One time pads are currently the only provable "unbreakable" encryption. The proof is trivial.

phkahler 12y ago

I found an algorithm to determine the parity (even or odd) of the number of factors in N. Never wrote about it because IDK if it's unique, and also because it's time complexity seems poor and I never tried to prove any upper bound or make it faster. Anyone know of something similar? Would this be interesting?

pbsd 12y ago
That is called the Liouville function; you might get luckier searching for that name. I don't know much about the state-of-the-art on computing it, but I found a description of such a method here, which may be a starting point to compare with: http://www.ams.org/journals/mcom/1960-14-072/S0025-5718-1960-0120198-5/ http://www.ams.org/journals/mcom/1960-14-072/S0025-5718-1960...
damarquis 12y ago
A fast algorithm for parity would be interesting. There is currently no better way to compute parity than factoring N. There is a well known hand wavy-argument that computing any function on the prime factors of arbitrary integers should be difficult. Very roughly the idea is that if you can compute such a function over the integers you can probably also compute it over other rings. Applying it over certain number fields would let you get information about the low bits of the prime factors which is thought to be hard. There is a bit more information given in Terrence Tao's answer here http://mathoverflow.net/questions/3820/how-hard-is-it-to-compute-the-number-of-prime-factors-of-a-given-integer http://mathoverflow.net/questions/3820/how-hard-is-it-to-com... His answer is about counting the number of distinct prime factors but I think that it can extended to the parity of this value as well.
- phkahler 12y ago
  Thanks, the mathoverflow link was very informative. It's funny because I started out computing a number that I thought would be useful for factoring N, but it turned out that it would take one of 2 values depending if N was prime or had 2 factors (this is easily proven). Subsequent testing via software seemed to indicate it was actually determining the parity of the number of primes. I believe that's what it does in general but never bothered to go any further.