2
$\begingroup$

We know that computing number of prime factors implies efficient factoring algorithm (How hard is it to compute the number of prime factors of a given integer?).

Let $\omega(n)$ be number of distinct prime factors of $n$. Knowledge of below three do not seem to give a factoring algorithm.

  1. Square-freeness (already have efficient square-freeness tests for univariate polynomials).

  2. Number of bits (MSB) and parity (LSB) of $\omega(n)$. MSB gives number of bits and LSB gives parity (eg: if number of prime factors is $124$ then since $124=(1111100)_2$ number of bits is $7$ and parity of $124$ is $0$). These cannot be $\#P$ complete or $\oplus P$ complete unless polynomial hierarchy has randomized subexponential algorithms and in $\mathsf{BQP}$.

These problems may be computable in randomized polynomial time since MSB and LSB on $0/1$ permanent is in $BPP$ and in $P$ respectively and $0/1$ permanent is $\#P$ complete.

  1. Number of bits in each factor if the number is a semiprime (there is no good algorithm to find degree of factors even for univariate polynomials).

Can there be efficient algorithms for these?

From 1. and 2. we can at best say if the number is a semiprime ($pq$) form or a triprime ($pqr$) form.

If a semiprime then 3. tells whether it is balanced (equal bits in $p$ and $q$).

$\endgroup$
  • $\begingroup$ The answer probably is "we don't know" to all four... $\endgroup$ – Wojowu Sep 26 '17 at 16:44
  • $\begingroup$ @Wojowu yes I agree but by saying 'Can there be..?' I look for obstructions as well. $\endgroup$ – T.... Sep 26 '17 at 16:45
  • $\begingroup$ @wojowu Number of bits in $\omega(n)$ may be in $BPP$. $\endgroup$ – T.... Sep 27 '17 at 0:01
  • $\begingroup$ We know that computing number of prime factors implies efficient factoring algorithm: The answers on the linked page make it clear that nothing like that is actually known. $\endgroup$ – Emil Jeřábek Sep 27 '17 at 13:37
  • $\begingroup$ "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". $\endgroup$ – T.... Sep 28 '17 at 2:58
3
$\begingroup$

We know that computing number of prime factors implies efficient factoring algorithm (How hard is it to compute the number of prime factors of a given integer?).

We don't know that. Terrence Tao's answer is a plausibility argument. Since you are interested in complexity classes it isn't relevant.

I have comments about two of your questions:

  1. Square-freeness (already have efficient square-freeness tests for univariate polynomials).

No algorithm exists faster than factoring $n$.

If $n$ has a special form then there might be a better way to factor it than applying GNFS. For example there is the following paper for $n = pq^r$ for large $r$: https://crypto.stanford.edu/~dabo/abstracts/prq.html

  1. parity of $\omega(n)$

If $n$ is an odd squarefree number that's a product of primes congruent to $3 \pmod{4}$ this can be done. Let $\omega_3(n)$ be the number of distinct prime factors congruent to $3 \pmod{4}$.

$\omega_3(n)$ can be computed from $n \pmod 4.$

$\endgroup$
  • $\begingroup$ Here's a simple method to determine if a number N is square free. It does not require factoring N. math.stackexchange.com/questions/3064068/… $\endgroup$ – user25406 Jan 11 at 21:48
  • $\begingroup$ The method requires finding all representations of N as a sum of two squares. The relevant question is not "Does finding all representations of N as a sum of two squares require factoring N" it is "Can all representations of N as a sum of two squares be computed using fewer operations than factoring N." $\endgroup$ – David Marquis Jan 11 at 22:29
  • 1
    $\begingroup$ I think the number of solutions is a function of the number of divisors of n. Of course this quantity can be used to tell if the number is square free. It seems like the number of divisors of a number often comes up when counting solutions to diophantine equations. Another example is that the number of solutions to $lcm(A,B) = N$ is $d(N^2)$ (from Problems in Analytic Number Theory by Murty). $\endgroup$ – David Marquis Jan 12 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.