Est-il difficile de compter le nombre de facteurs d'un entier?

Étant donné un entier de longueur bits, est-il difficile de produire le nombre de facteurs premiers (ou alternativement le nombre de facteurs) de ? $N$ $n$ $N$

Si nous connaissions la factorisation première de , ce serait facile. Cependant, si nous connaissions le nombre de facteurs premiers ou le nombre de facteurs généraux, il n'est pas clair comment nous trouverions la factorisation réelle. $N$

Ce problème est-il étudié? Existe-t-il des algorithmes connus qui résolvent cette question sans trouver la factorisation première?

Cette question est motivée par la curiosité et en partie par une question math.SE .

cc.complexity-theory counting-complexity nt.number-theory factoring Artem Kaznatcheev
la source

Si le nombre de facteurs premiers est grand, cela impliquerait que N a un petit facteur qui peut être trouvé facilement. D'un autre côté, si le nombre de facteurs premiers de N est petit, disons 2, alors c'est similaire au problème de factoriser un produit de deux nombres premiers, et savoir que le nombre de facteurs est 2 ne semble pas aider. Voir cette question d'Omid sur leur dureté moyenne.

Kaveh

Une dernière chose, puisque la division est uniforme

, le problème de compter tous les facteurs (pas seulement les facteurs premiers) est dans

et est donc également dans

(et est probablement aussi complet pour

sous

Réductions

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 vous pouviez développer votre commentaire ci-dessus en une réponse, ce serait bien. Je ne vois pas exactement comment la division dans

vous amène à compter les facteurs dans

sans impliquer également que l'affacturage est dans

. Ce malentendu est probablement dû à mes propres échecs, mais une réponse plus détaillée serait utile.

{TC}^{0}

$\text{TC}^0$

# {TC}^{0}

$\#\text{TC}^0$

{TC}^{0}

$\text{TC}^0$

Derrick Stolee

AFAIK connu! et c'est trop facile. Mais je ne vois pas où l'argument se brise. ps: je suppose que je sais voir, ma définition de

n'est pas bonne (c'est la même chose que

) et c'est le problème.

# T C^{0}

$\mathsf{\#TC^0}$

# P

$\mathsf{\#P}$

Kaveh

@Artem,

est défini comme le nombre de chemins d'acceptation d'une machine

, et une machine

ne peut utiliser qu'un espace logarithmique (en

) pour deviner

. Nous supposons trop de bits si nous utilisons la définition que j'ai écrite, un calcul

avec de nombreuses suppositions polynomiales capturerait

, en comptant de manière similaire le nombre de

s de taille polynomiale qu'une machine

accepte sur eux donnerait

# 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}$ (devinez également le calcul et vérifiez qu'il s'agit bien d'un calcul acceptant).

Kaveh

Réponses:

Ce n'est pas ma réponse, mais Terrence Tao a donné une belle réponse à cette question sur MathOverflow.

Voici les premières lignes de sa réponse. Pour lire la réponse complète, suivez le lien.

Il existe une observation du folklore selon laquelle si l'on était capable de compter rapidement le nombre de facteurs premiers d'un entier n, alors on serait probablement capable de factoriser rapidement n complètement. On pense donc que le problème des facteurs premiers de comptage a des difficultés comparables à l'affacturage lui-même.

(Je ne savais pas si cela devait être une réponse ou un commentaire. Mais c'est vraiment une réponse, bien qu'elle ne soit pas écrite par moi. J'ai fait la réponse Wiki de la communauté afin qu'elle puisse être votée ou acceptée sans inutilement me donnant la réputation.)

Robin Kothari
la source

À mon avis, un pointeur vers une réponse comme celle-ci mérite des points de réputation (il ne devrait donc pas être un wiki communautaire), mais je comprends que différentes personnes ont des opinions différentes.

Tsuyoshi Ito

Mais ce n'est pas une réduction officielle ....

arnab

@arnab: Non, ce n'est pas le cas. C'est pourquoi il a écrit «alors on serait probablement capable de factoriser rapidement n complètement».

Tsuyoshi Ito

$N$ $n$ $N$ $N$ $\log_3(N)$ $N^{1/p}$ $N$ $p$

Foo Barrigno
la source