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.
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?
<p><pre><code> 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.
</code></pre>
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.