A New Provable Factoring Algorithm
rjlipton.wordpress.com
A New Provable Factoring Algorithm
1–10 of 22 posts
Re: A New Provable Factoring Algorithm
#2I'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
#3I'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 polyn…
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, ...
... yet are observed to be the fastest in practice
for numbers of substantial size.
The provable algorithms are usually deterministic,
but their key feature is that their correctness is
unconditional.
Re: A New Provable Factoring Algorithm
#4I'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 polyn…
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
#5I'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 polyn…
[deleted]
Re: A New Provable Factoring Algorithm
#6 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.
Re: A New Provable Factoring Algorithm
#7I'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 polyn…
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 fast…
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
#8Earlier quoted context omitted.
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 fast…
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 i…
Perfect - thank you.
Re: A New Provable Factoring Algorithm
#9I 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?
Re: A New Provable Factoring Algorithm
#10I 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?
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...