News for hackers. Stuff that matters.
Re:A New Provable Factoring Algorithm by Sniffnoy on Thursday October 23, 2014 @05:43AM (#8497362)
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.
Re:A New Provable Factoring Algorithm by ColinWright on Thursday October 23, 2014 @06:08AM (#8497414)
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.
Re:A New Provable Factoring Algorithm by pbsd on Thursday October 23, 2014 @08:46AM (#8497826)
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...

[2] https://math.dartmouth.edu/~carlp/hyperI.pdf

[3] https://math.dartmouth.edu/~carlp/PDF/paper129.pdf

[4] https://openaccess.leidenuniv.nl/bitstream/handle/1887/3826/...

Re:A New Provable Factoring Algorithm by Sniffnoy on Thursday October 23, 2014 @05:25PM (#8500846)
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.
Re:A New Provable Factoring Algorithm by ColinWright on Thursday October 23, 2014 @08:53AM (#8497843)
Perfect - thank you.
Re:A New Provable Factoring Algorithm by algorias on Thursday October 23, 2014 @07:46AM (#8497650)
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.

Re:A New Provable Factoring Algorithm by thaumasiotes on Thursday October 23, 2014 @11:17AM (#8498560)
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".
Re:A New Provable Factoring Algorithm by JadeNB on Thursday October 23, 2014 @01:17PM (#8499372)
"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.

Re:A New Provable Factoring Algorithm by thaumasiotes on Thursday October 23, 2014 @10:08PM (#8501800)
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.
Re:A New Provable Factoring Algorithm by JadeNB on Friday October 24, 2014 @10:08PM (#8506936)
> 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.

Oh, I see. I read "A is consistent with B" as "A+B is consistent", but I can see the validity of the reading "A+B is 'as consistent as' A".

Re:A New Provable Factoring Algorithm by dvt on Thursday October 23, 2014 @02:32PM (#8499866)
What he means when he says "unprovable" is "not provably guaranteed to run in O(x)" since the entire discussion is about complexity. A "provable" algorithm, then, is one where the running time can be calculated.

In a deterministic algorithm, this bound will always exist. In a non-deterministic algorithm (e.g. one that uses a random walk), this bound will not. The funny thing is that in the real world (and for big data) the latter algorithms generally run faster than the former.

If you're wondering why a non-deterministic algorithm can't have bounds, it's simple! Because it would range from a trivial best case of I get really lucky and randomly hit every "good" factor in constant time O(1) to the trivial worst cast of I get really unlucky and keep guessing the wrong numbers ad infinitum.