Jak trudno policzyć liczbę czynników całkowitych?

Biorąc pod uwagę liczbę całkowitą długości bitów, jak trudne jest wyprowadzenie liczby czynników pierwszych (lub alternatywnie liczby czynników) ? $N$ $n$ $N$

Gdybyśmy znali podstawową faktoryzację , byłoby to łatwe. Gdybyśmy jednak znali liczbę czynników pierwszych lub liczbę czynników ogólnych, nie jest jasne, w jaki sposób ustalilibyśmy faktyczne czynniki pierwsze. $N$

Czy ten problem jest badany? Czy znane są algorytmy, które rozwiązują to pytanie bez znalezienia faktoryzacji pierwotnej?

To pytanie jest motywowane ciekawością, a częściowo pytaniem matematycznym .

cc.complexity-theory counting-complexity nt.number-theory factoring Artem Kaznatcheev
źródło

Jeśli liczba czynników pierwszych jest duża, oznaczałoby to, że N ma mały czynnik, który można łatwo znaleźć. Z drugiej strony, jeśli liczba czynników pierwszych N jest niewielka, powiedzmy 2, to jest to podobne do problemu faktorowania iloczynu dwóch liczb pierwszych, a świadomość, że liczba czynników wynosi 2, nie wydaje się pomóc. Zobacz to pytanie Omida dotyczące ich średniej twardości.

Kaveh

Jeszcze jedna rzecz, ponieważ podział jest w jednolitej

, problem zliczania wszystkich czynników (nie tylko liczb pierwszych) występuje w

a zatem występuje również w

(i prawdopodobnie jest również kompletny dla

pod

Redukcje

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, gdybyś mógł rozwinąć swój powyższy komentarz w odpowiedź, byłoby świetnie. Nie do końca rozumiem, jak podział w

prowadzi do liczenia czynników w

nie sugerując również, że faktoring jest w

. To nieporozumienie jest prawdopodobnie spowodowane moimi własnymi niepowodzeniami, ale pomocna byłaby bardziej szczegółowa odpowiedź.

{TC}^{0}

$\text{TC}^0$

# {TC}^{0}

$\#\text{TC}^0$

{TC}^{0}

$\text{TC}^0$

Derrick Stolee,

znany AFAIK! i to jest zbyt łatwe. Ale nie widzę, gdzie argument się załamuje. ps: Chyba wiem, że moja definicja

nie jest dobra (jest taka sama jak

) i na tym polega problem.

# T C^{0}

$\mathsf{\#TC^0}$

# P

$\mathsf{\#P}$

Kaveh

# 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}$ (zgadnij również obliczenia i sprawdź, czy naprawdę jest to obliczenie akceptujące).

Kaveh

Odpowiedzi:

To nie jest moja odpowiedź, ale Terrence Tao udzielił pięknej odpowiedzi na to pytanie na MathOverflow.

Oto kilka pierwszych linii jego odpowiedzi. Aby przeczytać pełną odpowiedź, kliknij link.

Istnieje obserwacja folklorystyczna, że jeśli ktoś byłby w stanie szybko policzyć liczbę liczb pierwszych liczby całkowitej n, to prawdopodobnie byłby w stanie szybko obliczyć liczbę całkowitą n. Uważa się zatem, że problem czynników liczących pierwsze ma podobną trudność jak samo faktoring.

(Nie byłem pewien, czy to powinna być odpowiedź, czy komentarz. Ale to naprawdę odpowiedź, chociaż nie jest napisana przeze mnie. Udzieliłem odpowiedzi Community Wiki, aby można było ją głosować lub zaakceptować bez niepotrzebnego dając mi reputację).

Robin Kothari
źródło

Moim zdaniem wskaźnik do takiej odpowiedzi zasługuje na punkty reputacji (więc nie powinno to być wiki społeczności), ale rozumiem, że różni ludzie mają różne poglądy.

Tsuyoshi Ito,

Ale to nie jest formalna redukcja ....

arnab

@arnab: Nie, nie jest. Dlatego napisał „wtedy prawdopodobnie można by było szybko całkowicie uwzględnić czynnik n”.

Tsuyoshi Ito,

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

Foo Barrigno
źródło