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...
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.