?

Читая блог Дика Липтона, я наткнулся на следующий факт в конце его поста о факторе Борна :

Если для каждого существует отношение вида где , и каждый из , и является по длине в битах, тогда факторинг имеет полином размерные схемы. $n$
$(2^{n})! = \sum_{k = 0}^{m - 1} a_{k} b_{k}^{c_{k}}$ $(2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k}$ $m = poly(n)$ $a_k$ $b_k$ $c_k$ $poly(n)$

Другими словами,, который имеет экспоненциальное количество битов , потенциально может быть представлен эффективно. $(2^n)!$

У меня есть несколько вопросов:

Может ли кто-нибудь предоставить доказательство вышеуказанного отношения, назвать мне имя и / или предоставить какие-либо ссылки?
Если бы я дал вам , и каждый из , и , не могли бы вы предоставить мне алгоритм полиномиального времени для проверки правильности отношения (т. Е. Находится ли он в )? $n$ $m$ $a_k$ $b_k$ $c_k$ $NP$

ds.algorithms reference-request factoring comp-number-theory user834
источник

Разве этот пост в блоге не претендует на обратное? То есть, если уравнения вышеприведенного вида имеют решения в общем , тогда факторинг имеет схемы полиномиального размера.

(2^{n})! = \sum \dots

$(2^n)! = \sum \cdots$

Микро

Я думаю, что вы на самом деле написали обратное тому, что написал Дик Липтон. Он говорит, что если такое уравнение существует для каждого , то факторинг имеет схемы полиномиального размера. Таким образом, подразумевается, что если факторинг является неравномерно сложным (для бесконечного числа ), то уравнения указанной выше формы не существуют (для бесконечного числа ).

n

$n$

n

$n$

n

$n$

Сашо Николов

@mikero, SashoNikolov, вы оба правы, мои извинения. Я отредактировал свой вопрос.

user834

Обратите внимание, что «алгоритм полиномиального времени» обычно означает единый алгоритм. Пост Липтона только утверждает существование семейства полисайтовых схем для факторинга.

Сашо Николов

Обратите внимание, что для того, чтобы это свойство было истинным,

должны быть

в битовом размере /, как указано в блоге Липтона /, и

как целые числа , Ваше определение не ясно.

a_{k}

$a_k$

b_{k}

$b_k$

c_{k}

$c_k$

p o l y (n)

$poly(n)$

p o l y (2^{n})

$poly(2^n)$

Гопи

Ответы:

Я прокомментирую почему отношение как в вопросе (для каждого ) помогает факторинг. Я не могу закончить спор, но, возможно, кто-то может.

(2^{n})! = \sum_{k = 0}^{m - 1} a_{k} b_{k}^{c_{k}}

$(2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k}$

n

$n$

Первое наблюдение заключается в том, что приведенное выше соотношение (и в более общем смысле, наличие многоразмерных арифметических схем для ) Дает многоразмерную схему для вычисления для заданный в двоичном виде: просто вычислите сумму по модулю , используя возведение в степень путем повторного возведения в квадрат. $(2^n)!$ $(2^n)!\bmod x$ $x$ $x$

Теперь, если бы мы могли вычислить для произвольного , мы могли бы множить : используя бинарный поиск, найти наименьший такой, что (который мы можем вычислить, используя ). Тогда должен быть наименьшим простым делителем . $y!\bmod x$ $y$ $x$ $y$ $\gcd(x,y!)\ne1$ $\gcd(x,(y!\bmod x))$ $y$ $x$

Если мы можем сделать только степени для , мы все равно можем попытаться вычислить Для каждого . Одним из них будет нетривиальный делитель , за исключением неудачного случая, когда существует такое , что взаимно прост с и делит , Это эквивалентно тому, чтобы сказать, что $2$ $y$ $\gcd(x,(2^n)!)$ $n\le\log x$ $x$ $n$ $x$ $(2^n)!$ $(2^{n+1})!$ $x$ не содержит квадратов, и все его главные факторы имеют одинаковую длину в битах. Я не знаю, что делать в этом (довольно важном случае).

Эмиль Йержабек поддерживает Монику
источник

Если отношение выполнено (для всех

), то, возможно, оно также выполняется (с другим выбором

), когда один заменяет

другим (малым) простым числом,

. Можно предположить поиск до тех пор, пока не будет найдено

, так что

взаимно прост с

а не

n

$n$

a_{k}

$a_k$

b_{k}

$b_k$

c_{k}

$c_k$

2

$2$

p

$p$

p

$p$

x

$x$

(p^{n})!

$(p^n)!$

(p^{n + 1})!

$(p^{n+1})!$

user834