There is a folklore observation that if one was able to quickly count the number of prime factors of an integer n, then one would likely be able to quickly factor n completely. So the counting-prime-factors problem is believed to have comparable difficulty to factoring itself.
The reason for this is that we expect any factoring-type algorithm that works over the integers, to also work over other number fields (ignoring for now the issue of unique factorisation, which in principle can be understood using class field theory). Thus, for instance, we should also be able to count the number of prime factors over the Gaussian integers, which would eventually reveal how many of the (rational) prime factors of the original number n were equal to 1 mod 4 or to 3 mod 4.
Using more and more number fields (but one should only need polylog(n) such fields) and using various reciprocity relations, one would get more and more congruence relations on the various prime factors, and pretty soon one should be able to use the Chinese remainder theorem to pin down the prime factors completely.
More generally, the moment one has a way of extracting even one non-trivial useful bit of information about the factors of a number, it is likely that one can vary this procedure over various number fields (or by changing other parameters, e.g. twisting everything by a Dirichlet character) and soon extract out enough bits of information to pin down the factors completely. The hard part is to first get that one useful bit...
[EDIT: The above principle seems to have one exception, namely the parity bit of various number-theoretic functions. For instance, in the (now stalled) Polymath4 project to find primes, we found a quick way to compute the parity of the prime counting function $pi(x)$, but it has proven stubbornly difficult to perturb this parity bit computation to find other useful pieces of information about this prime counting function.]
No comments:
Post a Comment