¿Qué tan difícil es contar el número de factores de un número entero?

Dado un entero de longitud bits, ¿qué tan difícil es generar el número de factores primos (o alternativamente el número de factores) de ? $N$ $n$ $N$

Si supiéramos la factorización principal de , entonces esto sería fácil. Sin embargo, si supiéramos el número de factores primos, o el número de factores generales, no está claro cómo encontraríamos la factorización prima real. $N$

¿Se estudia este problema? ¿Existen algoritmos conocidos que resuelvan esta pregunta sin encontrar la factorización prima?

Esta pregunta está motivada por la curiosidad y parcialmente por una pregunta de matemáticas .

cc.complexity-theory counting-complexity nt.number-theory factoring Artem Kaznatcheev
fuente

Si el número de factores primos es grande, eso implicaría que N tiene un factor pequeño que se puede encontrar fácilmente. Por otro lado, si el número de factores primos de N es pequeño, digamos 2, entonces es similar al problema de factorizar un producto de dos números primos, y saber que el número de factores es 2 no parece ayudar. Vea esta pregunta de Omid sobre su dureza promedio.

Kaveh

Una cosa más, dado que la división está en uniforme , el problema de contar todos los factores (no solo los factores primos) está en y, por lo tanto, también está en (y probablemente también esté completo para bajo las reducciones de ).

T C^{0}

$\mathsf{TC^0}$

# T C^{0}

$\mathsf{\#TC^0}$

P

$\mathsf{P}$

# T C^{0}

$\mathsf{\#TC^0}$

A C^{0}

$\mathsf{AC^0}$

Kaveh

Kaveh, si pudieras ampliar tu comentario anterior en una respuesta, sería genial. No veo exactamente cómo la división en lleva a contar factores en sin implicar también que la factorización está en . Es probable que este malentendido se deba a mis propios fracasos, pero una respuesta más detallada ayudaría.

{TC}^{0}

$\text{TC}^0$

# {TC}^{0}

$\#\text{TC}^0$

{TC}^{0}

$\text{TC}^0$

Derrick Stolee

conocido AFAIK! Y esto es demasiado fácil. Pero no veo dónde se rompe el argumento. ps: supongo que sé, mi definición de no es buena (es lo mismo que ) y ese es el problema.

# T C^{0}

$\mathsf{\#TC^0}$

# P

$\mathsf{\#P}$

Kaveh

@Artem, se define como el número de rutas de aceptación de una máquina , y una máquina solo puede usar una cantidad logarítmica (en ) de espacio para adivinar . Adivinamos demasiados bits si utilizamos la definición que escribí, un cálculo de con polinomios muchas conjeturas capturarían , contando de manera similar el número de s de tamaño polinómico que un máquina acepta en ellos dará (adivine el cálculo también y verifique que realmente sea un cálculo de aceptación).

# L

$\mathsf{\#L}$

N L

$\mathsf{NL}$

N L

$\mathsf{NL}$

| y |

$|y|$

x

$x$

A C^{0}

$\mathsf{AC^0}$

N P

$\mathsf{NP}$

x

$x$

A C^{0}

$\mathsf{AC^0}$

# P

$\mathsf{\#P}$

Kaveh

Respuestas:

Esta no es mi respuesta, pero Terrence Tao dio una hermosa respuesta a esta pregunta en MathOverflow.

Aquí están las primeras líneas de su respuesta. Para leer la respuesta completa, siga el enlace.

Hay una observación del folklore de que si uno fuera capaz de contar rápidamente el número de factores primos de un número entero n, probablemente sería capaz de factorizar rápidamente n por completo. Por lo tanto, se cree que el problema de los factores primos de contar tiene una dificultad comparable a la factorización.

(No estaba seguro de si esto debería ser una respuesta o un comentario. Pero en realidad es una respuesta, aunque no está escrito por mí. He hecho la respuesta Community Wiki para que pueda ser votada o aceptada sin innecesariamente dándome reputación)

Robin Kothari
fuente

En mi opinión, un puntero a una respuesta como esta merece puntos de reputación (por lo que no debería ser wiki de la comunidad), pero entiendo que diferentes personas tienen diferentes puntos de vista.

Tsuyoshi Ito

Pero esto no es una reducción formal ...

arnab

@arnab: No, no lo es. Es por eso que escribió “entonces uno podría probablemente ser capaz de factor de forma rápida n completamente.”

Tsuyoshi Ito

Como han dicho otros, contar los factores probablemente requeriría factorizar n. Sin embargo, la división de prueba puede limitar el número de factores. Usted sabe, por ejemplo, que tiene como máximo factores, ya que ningún factor puede ser menor que 2. Al probar si es divisible por 2, también sabe que tiene como máximo factores, etc. La desventaja es que cada reducción de tamaño es progresivamente más difícil: debe probar hasta para descartar que contenga más de factores $N$ $n$ $N$ $N$ $\log_3(N)$ $N^{1/p}$ $N$ $p$

Foo Barrigno
fuente