¿Es difícil calcular el número de factores primos de un número entero dado?

Question

Hice una pregunta relacionada en este hilo de mathoverflow . Esa pregunta fue rápidamente contestada. Esta es una pregunta de seguimiento natural de esa, que decidí volver a publicar ya que esa pregunta está respondida.

Así que citándome a mí mismo en ese hilo:

¿Es difícil calcular el número de factores primos de un número entero dado? Esto no puede ser tan difícil como la factorización, puesto que ya se conoce este valor para los semiprimas, y esta información no parece ayudar en absoluto. Además, determinar si el número de factores primos es 1 o mayor que 1 se puede hacer de manera eficiente utilizando la prueba de primalidad.

Answer 1

Hay una observación popular que dice que si uno fuera capaz de contar rápidamente el número de factores primos de un número entero n, entonces probablemente sería capaz de factorizar rápidamente n por completo. Así que se cree que el problema de contar los factores primos tiene una dificultad comparable a la de la factorización en sí.

La razón es que esperamos que cualquier algoritmo de factorización que funcione sobre los enteros, también funcione sobre otros campos numéricos (ignorando por ahora la cuestión de la factorización única, que en principio puede entenderse utilizando la teoría de campos de clases). Así, por ejemplo, también deberíamos ser capaces de contar el número de factores primos sobre los enteros de Gauss, lo que eventualmente revelaría cuántos de los factores primos (racionales) del número original n eran iguales a 1 mod 4 o a 3 mod 4.

Utilizando más y más campos numéricos (pero sólo se deberían necesitar polilog(n) campos de este tipo) y utilizando varias relaciones de reciprocidad, se obtendrían más y más relaciones de congruencia sobre los distintos factores primos, y muy pronto se podría utilizar el teorema del resto chino para precisar los factores primos por completo.

En términos más generales, en el momento en que uno tiene una forma de extraer aunque sea un bit de información útil no trivial sobre los factores de un número, es probable que uno pueda variar este procedimiento sobre varios campos numéricos (o cambiando otros parámetros, por ejemplo, torciendo todo por un carácter Dirichlet) y pronto extraer suficientes bits de información para precisar los factores completamente. Lo difícil es conseguir primero ese bit útil...

[EDIT: El principio anterior parece tener una excepción, a saber, el bit de paridad de varias funciones de la teoría de los números. Por ejemplo, en el proyecto (ahora estancado) Polymath4 para encontrar primos, encontramos una forma rápida de calcular la paridad de la función de conteo de primos $\pi(x)$ pero se ha demostrado que es obstinadamente difícil perturbar este cálculo de bits de paridad para encontrar otras piezas útiles de información sobre esta función de recuento de primos].

Answer 2

No tengo nada riguroso ni respaldado, pero calcular el número de factores primos (mod 2) parece ser en sí mismo muy difícil. El hecho de que la tecnología teórica actual, en particular, no pueda distinguir entre números enteros con un número par de factores primos y números enteros con un número impar de factores primos es una la mayor pesadilla de la teoría de los números . La discusión en el post enlazado me hace dudar fuertemente de que haya un algoritmo eficiente conocido para esto, ya que tendría que utilizar métodos que son muy diferentes de casi cualquier otro algoritmo de teoría numérica que hay.

Answer 3

Sólo unas simples observaciones que aún no han sido señaladas. En primer lugar, se puede plantear la pregunta como un problema de decisión: ¿Tiene el número entero N más de k factores primos (distintos o no)? Entonces se puede utilizar la búsqueda binaria para encontrar de forma eficiente el número exacto de factores primos mediante preguntas repetidas. Como usted señala, esto es más fácil que la factorización. En cuanto a las clases de complejidad particulares, este problema está en BQP (tiempo polinómico cuántico de error limitado), ya que podemos utilizar simplemente El algoritmo de Shor para factorizar eficientemente el número primero. También está en la intersección de co-NP y NP ya que cualquiera que sea la respuesta que obtengamos (si tiene al menos k factores primos, o menos de k) puede verificarse eficientemente en un ordenador clásico. Puede que haya clases de complejidad más especializadas en las que uno podría intentar encajar este problema... el primer lugar donde buscar es el Zoológico de la Complejidad .

Answer 4

Este documento Sobre algunas estimaciones relativas al número de divisores primos de un número entero puede tener algo que te ayude.