Quão difícil é contar o número de fatores de um número inteiro?

Dado um número inteiro de comprimento bits, quão difícil é produzir o número de fatores primos (ou o número alternativo de fatores) de ? $N$ $n$ $N$

Se soubéssemos a fatoração primária de , isso seria fácil. No entanto, se soubéssemos o número de fatores primos ou o número de fatores gerais, não está claro como encontraríamos a fatoração primordial real. $N$

Este problema é estudado? Existem algoritmos conhecidos que resolvem essa questão sem encontrar a fatoração primária?

Esta questão é motivado por curiosidade e parcialmente por uma questão math.SE .

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

Se o número de fatores primos for grande, isso implicaria que N possui um fator pequeno que pode ser encontrado facilmente. Por outro lado, se o número de fatores primos de N for pequeno, digamos 2, é semelhante ao problema de fatorar um produto de dois primos e saber que o número de fatores é 2 não parece ajudar. Veja esta pergunta de Omid sobre sua dureza média.

Kaveh

Mais uma coisa, como a divisão é uniforme

, o problema de contar todos os fatores (não apenas os fatores primos) está em

e, portanto, também está em

(e provavelmente também está completo em

Reduções 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}$

19411 Kaveh

Kaveh, se você pudesse expandir seu comentário acima em uma resposta, isso seria ótimo. Não vejo exatamente como a divisão no

leva você a contar fatores no

sem também implicar que o fatoramento está no

. Esse mal-entendido provavelmente se deve às minhas próprias falhas, mas uma resposta mais detalhada ajudaria.

{TC}^{0}

$\text{TC}^0$

# {TC}^{0}

$\#\text{TC}^0$

{TC}^{0}

$\text{TC}^0$

Derrick Stolee

conhecido AFAIK! e isso é muito fácil. Mas não vejo onde o argumento termina. ps: Eu acho que sei ver, minha definição de

não é boa (é a mesma que

) e esse é o problema.

# T C^{0}

$\mathsf{\#TC^0}$

# P

$\mathsf{\#P}$

Kaveh

@Artem,

é definido como o número de percursos de aceitação de uma

máquina, e um

máquina pode utilizar apenas logarítmica (em

) quantidade de espaço para adivinhar

. Estamos adivinhando muitos bits se usarmos a definição que escrevi; um cálculo de

com muitas suposições polinomialmente capturaria

, contando da mesma forma o número de

s de tamanho polinomial que uma máquina

aceita

dará

# 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}$ (adivinhe também o cálculo e verifique se é realmente um cálculo aceitável).

precisa saber é o seguinte

Respostas:

Esta não é a minha resposta, mas Terrence Tao deu uma bela resposta a esta pergunta no MathOverflow.

Aqui estão as primeiras linhas de sua resposta. Para ler a resposta completa, siga o link.

Há uma observação do folclore de que, se alguém fosse capaz de contar rapidamente o número de fatores primos de um número inteiro n, provavelmente seria capaz de fatorar rapidamente n completamente. Portanto, acredita-se que o problema dos fatores primos da contagem tenha dificuldade comparável à fatoração em si.

(Eu não tinha certeza se isso deveria ser uma resposta ou um comentário. Mas é realmente uma resposta, embora não tenha sido escrita por mim. Fiz a resposta Wiki da comunidade para que possa ser votado ou aceito sem necessidade desnecessária me dando reputação.)

Robin Kothari
fonte

Na minha opinião, um ponteiro para uma resposta como essa merece pontos de reputação (portanto, não deve ser um wiki da comunidade), mas entendo que pessoas diferentes têm opiniões diferentes.

Tsuyoshi Ito

Mas esta não é uma redução formais ....

arnab

@arnab: Não, não é. É por isso que ele escreveu "então seria possível fatorar rapidamente n completamente". #

Tsuyoshi Ito

Como outros já declararam, contar os fatores provavelmente exigiria o fatoramento n. No entanto, a divisão de teste pode limitar o número de fatores. Você sabe, por exemplo, que possui no máximo fatores, uma vez que nenhum fator pode ser menor que 2. Testando se é divisível por 2, você também sabe que possui no máximo fatores, etc. A desvantagem é que cada redução no tamanho é progressivamente mais difícil - você precisa testar até para excluir contendo mais do que fatores . $N$ $n$ $N$ $N$ $\log_3(N)$ $N^{1/p}$ $N$ $p$

Foo Barrigno
fonte