Насколько сложно посчитать количество факторов целого числа?

Учитывая целое число длиной битов, насколько сложно вывести число простых факторов (или, альтернативно, число факторов) из ? $N$ $n$ $N$

Если бы мы знали первичную факторизацию , то это было бы легко. Однако, если бы мы знали количество основных факторов или число общих факторов, неясно, как мы могли бы найти фактическую основную факторизацию. $N$

Эта проблема изучена? Существуют ли известные алгоритмы, которые решают этот вопрос, не находя основной факторизации?

Этот вопрос мотивирован любопытством и частично вопросом математики .

cc.complexity-theory counting-complexity nt.number-theory factoring Артем Казнатчеев
источник

Если число простых факторов велико, это будет означать, что N имеет небольшой фактор, который можно легко найти. С другой стороны, если число простых факторов N мало, скажем, 2, то это похоже на проблему факторизации произведения двух простых чисел, и знание того, что число факторов равно 2, похоже, не помогает. Посмотрите на этот вопрос Омида об их средней твердости.

Каве

Еще одна вещь, так как деление происходит в равномерном , проблема подсчета всех факторов (не только простых факторов) находится в и, следовательно, также в (и, вероятно, также завершено для разделе сокращений).

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}$

Каве

Каве, если бы ты мог расширить свой комментарий выше в ответ, это было бы здорово. Я не совсем понимаю, как деление в

приводит вас к подсчету факторов в но также не подразумевает, что факторинг находится в . Это недоразумение, вероятно, связано с моими собственными неудачами, но более подробный ответ поможет.

{TC}^{0}

$\text{TC}^0$

# {TC}^{0}

$\#\text{TC}^0$

{TC}^{0}

$\text{TC}^0$

Деррик Столи

известный AFAIK! и это слишком просто. Но я не вижу, где аргумент нарушается. PS: я думаю, я знаю, видите, мое определение не годится (это то же самое, что

), и это проблема.

# T C^{0}

$\mathsf{\#TC^0}$

# P

$\mathsf{\#P}$

Каве

@Artem,

определяется как число принимающих путей машины

, а машина

может использовать только логарифмическое (в

) количество пространства для угадывания

. Мы предполагаем, что слишком много битов, если мы используем определение, которое я написал, вычисление

с полиномиально большим количеством догадок будет захватывать

, аналогично подсчет числа

s полиномиального размера, которое машина

принимает для них, даст

# 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}$ (угадайте вычисление также и убедитесь, что это действительно приемлемое вычисление).

Каве

Это не мой ответ, но Терренс Тао дал прекрасный ответ на этот вопрос в MathOverflow.

Вот первые несколько строк его ответа. Чтобы прочитать полный ответ, перейдите по ссылке.

Существует фольклорное наблюдение, что если бы можно было быстро сосчитать число простых факторов целого числа n, то, вероятно, можно было бы быстро полностью вычислить n. Таким образом, считается, что проблема подсчета простых факторов сопряжена с трудностями факторинга.

(Я не был уверен, должен ли это быть ответ или комментарий. Но это действительно ответ, хотя он не написан мной. Я сделал ответ на вики-сайте сообщества, чтобы его можно было проголосовать или принять без необходимости. давая мне репутацию.)

Робин Котари
источник

По моему мнению, указатель на такой ответ заслуживает репутации (так что это не должно быть вики сообщества), но я понимаю, что разные люди имеют разные взгляды.

Цуёси Ито

Но это не формальное сокращение ....

Арнаб

@arnab: нет, это не так. Вот почему он написал « то можно было бы , вероятно , будет в состоянии быстро фактора п полностью.»

Цуоши Ито

Насколько сложно посчитать количество факторов целого числа?

Ответы: