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

Improve this question
$\endgroup$
7
  • $\begingroup$ The answer probably is "we don't know" to all four... $\endgroup$
    – Wojowu
    Sep 26, 2017 at 16:44
  • $\begingroup$ @Wojowu yes I agree but by saying 'Can there be..?' I look for obstructions as well. $\endgroup$
    – Turbo
    Sep 26, 2017 at 16:45
  • $\begingroup$ @wojowu Number of bits in $\omega(n)$ may be in $BPP$. $\endgroup$
    – Turbo
    Sep 27, 2017 at 0:01
  • 1
    $\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, 2017 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$
    – Turbo
    Sep 28, 2017 at 2:58

1 Answer 1

Reset to default
5
$\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.$

Improve this answer
$\endgroup$
3
  • $\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, 2019 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$
    – duckstar
    Jan 11, 2019 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$
    – duckstar
    Jan 12, 2019 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.