Wie schwer ist es, die Anzahl der Faktoren einer ganzen Zahl zu zählen?

Wie schwer ist es bei einer ganzen Zahl einer Länge von Bits, die Anzahl der Primfaktoren (oder alternativ die Anzahl der Faktoren) von auszugeben ? $N$ $n$ $N$

Wenn wir die Primfaktorisierung von , wäre dies einfach. Wenn wir jedoch die Anzahl der Primfaktoren oder die Anzahl der allgemeinen Faktoren wüssten, ist nicht klar, wie wir die tatsächliche Primfaktorisierung finden würden. $N$

Ist dieses Problem untersucht? Gibt es bekannte Algorithmen, die diese Frage lösen, ohne die Primfaktorisierung zu finden?

Diese Frage wird durch Neugier und teilweise durch eine mathematische Frage motiviert .

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

Wenn die Anzahl der Primfaktoren groß ist, würde dies bedeuten, dass N einen kleinen Faktor hat, der leicht gefunden werden kann. Wenn andererseits die Anzahl der Primfaktoren von N klein ist, sagen wir 2, dann ähnelt dies dem Problem, ein Produkt aus zwei Primzahlen zu faktorisieren, und es scheint nicht hilfreich zu sein, zu wissen, dass die Anzahl der Faktoren 2 ist. Siehe diese Frage von Omid über ihre durchschnittliche Härte.

Kaveh

Eine weitere Sache ist , dass das Problem des Zählens aller Faktoren (nicht nur der Primfaktoren) in

und daher auch in

(und wahrscheinlich auch für

unter

vollständig ist), da die Division in einheitlicher

vorliegt

-Reduktionen).

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, wenn Sie Ihren obigen Kommentar zu einer Antwort erweitern könnten, wäre das großartig. Ich verstehe nicht genau, wie die Division in

Sie dazu bringt, die Faktoren in

ohne auch zu implizieren, dass Factoring in

. Dieses Missverständnis ist wahrscheinlich auf meine eigenen Fehler zurückzuführen, aber eine detailliertere Antwort würde helfen.

{TC}^{0}

$\text{TC}^0$

# {TC}^{0}

$\#\text{TC}^0$

{TC}^{0}

$\text{TC}^0$

Derrick Stolee

bekannte AFAIK! und das ist zu einfach. Aber ich sehe nicht, wo die Auseinandersetzung aufhört. ps: Ich glaube, ich weiß, dass meine Definition von

nicht gut ist (es ist dasselbe wie

) und das ist das Problem.

# T C^{0}

$\mathsf{\#TC^0}$

# P

$\mathsf{\#P}$

Kaveh

@Artem,

wird als die Anzahl der Annahme von Pfaden einer definierten

- Maschine, und eine

Maschine nur logarithmisch verwenden kann (in

) Menge an Speicherplatz für Erraten

. Wir raten zu viele Bits , wenn wir die Definition verwenden ich schrieb, eine

Berechnung mit polynomial vielen Vermutungen würden erfassen

, in ähnlicher Weise die Anzahl der Zählung

s von Polynom Größe , dass eine

Maschine akzeptiert sie geben

# 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}$ (Errate die Berechnung auch und überprüfe, ob sie wirklich akzeptabel ist).

Kaveh

Antworten:

Dies ist nicht meine Antwort, aber Terrence Tao hat diese Frage auf MathOverflow wunderschön beantwortet .

Hier sind die ersten Zeilen seiner Antwort. Um die vollständige Antwort zu lesen, folgen Sie dem Link.

Es gibt eine Folklorebeobachtung, dass man n wahrscheinlich schnell vollständig faktorisieren könnte, wenn man in der Lage wäre, die Anzahl der Primfaktoren einer ganzen Zahl n schnell zu zählen. Es wird angenommen, dass das Problem der Zählprimfaktoren vergleichbare Schwierigkeiten hat, sich selbst zu faktorisieren.

(Ich war mir nicht sicher, ob dies eine Antwort oder ein Kommentar sein sollte. Aber es ist wirklich eine Antwort, obwohl sie nicht von mir geschrieben wurde. Ich habe die Antwort im Community-Wiki so erstellt, dass sie ohne unnötigen Grund hochgestuft oder akzeptiert werden kann gib mir einen guten ruf.)

Robin Kothari
quelle

Meiner Meinung nach verdient ein Zeiger auf eine Antwort wie diese Reputationspunkte (es sollte also kein Community-Wiki sein), aber ich verstehe, dass verschiedene Menschen unterschiedliche Ansichten haben.

Tsuyoshi Ito

Aber dies ist keine formale Reduktion ....

Arnab

@arnab: Nein, das ist es nicht. Deshalb schrieb er: "Dann könnte man wahrscheinlich schnell n vollständig

Tsuyoshi Ito

Wie andere angegeben haben, würde das Zählen der Faktoren höchstwahrscheinlich das Faktorisieren von n erfordern. Die Aufteilung in Studien kann jedoch die Anzahl der Faktoren begrenzen. Sie wissen zum Beispiel, dass höchstens Faktoren hat, da kein Faktor kleiner als 2 sein kann. Wenn Sie testen, ob durch 2 teilbar ist, wissen Sie auch, dass höchstens Faktoren usw. hat Der Nachteil ist, dass jede Größenverringerung zunehmend schwieriger wird - Sie müssen bis zu testen, um auszuschließen, dass mehr als Faktoren enthält. $N$ $n$ $N$ $N$ $\log_3(N)$ $N^{1/p}$ $N$ $p$

Foo Barrigno
quelle