News for hackers. Stuff that matters.
Re:A New Provable Factoring Algorithm by phkahler on Thursday October 23, 2014 @09:51AM (#8498084)
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?
Re:A New Provable Factoring Algorithm by pbsd on Thursday October 23, 2014 @10:07AM (#8498164)
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...

Re:A New Provable Factoring Algorithm by damarquis on Thursday October 23, 2014 @11:44AM (#8498758)
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-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.

Re:A New Provable Factoring Algorithm by phkahler on Thursday October 23, 2014 @03:34PM (#8500243)
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.
Re:A New Provable Factoring Algorithm by JadeNB on Thursday October 23, 2014 @01:19PM (#8499384)
Do you really mean the number of factors, or just the number of prime factors? If the former, that's always even except for squares, so one reasonably fast approach would seem to be (square-root computation) + (test for integrality).