[damarquis]

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.

[phkahler]

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.