?

Ao ler o blog de Dick Lipton, deparei-me com o seguinte fato no final de seu post no Bourne Factor :

Se, para cada , existe uma relação da forma onde , e cada um dos , e são no comprimento de bits, então fatoração possui circuitos polinomiais. $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)$

Em outras palavras, o , que possui um número exponencial de bits , pode potencialmente ser representado com eficiência. $(2^n)!$

Eu tenho algumas perguntas:

Alguém poderia fornecer uma prova da relação acima, me dizer o nome e / ou fornecer alguma referência?
Se fosse para dar-lhe , e cada uma a , e , pode me proporcionar um algoritmo de tempo polinomial para verificar a validade da relação (ou seja, são em )? $n$ $m$ $a_k$ $b_k$ $c_k$ $NP$

ds.algorithms reference-request factoring comp-number-theory user834
fonte

Na verdade, essa publicação do blog não reivindica o contrário? Ou seja, se equações da forma acima

ter soluções em geral , depois de factoring tem circuitos polinomiais de tamanho.

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

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

Mikero

Eu acho que você realmente escreveu o inverso do que Dick Lipton escreveu. Ele diz que, se existe uma equação para cada

, o fatoração tem circuitos polinomiais de tamanho. Portanto, a implicação é que, se o fatoração não é uniformemente difícil (para infinitamente muitos

), então não existem equações da forma acima (para infinitamente muitos

n

$n$

n

$n$

n

$n$

Sasho Nikolov

@mikero, SashoNikolov, vocês dois estão corretos, minhas desculpas. Eu editei minha pergunta.

User834

observe que "algoritmo de tempo polinomial" geralmente significa um algoritmo uniforme. O post de Lipton apenas afirma a existência de uma família de circuitos polisizados para fatoração.

Sasho Nikolov

Note-se que para que essa propriedade para ser verdade,

deve ser

em tamanho bit / como indicado no Lipton do blog / e

como inteiros . Sua definição não é clara.

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

Gopi

Respostas:

Vou comentar por que uma relação como na pergunta (para cada ) ajuda a fatorar. Não consigo terminar a discussão, mas talvez alguém possa.

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

A primeira observação é que uma relação como acima (e mais geralmente, a existência de circuitos aritméticos de tamanho polivalente para ) Fornece um circuito de tamanho polivalente para a computação para dado em binário: simplesmente avalie a soma módulo , usando exponenciação por quadrado repetido. $(2^n)!$ $(2^n)!\bmod x$ $x$ $x$

Agora, se pudéssemos calcular $y!\bmod x$ para arbitrário , podemos fatorar : usando a pesquisa binária, encontre o menor tal que (que podemos calcular usando ). Então deve ser o menor divisor principal de . $y$ $x$ $y$ $\gcd(x,y!)\ne1$ $\gcd(x,(y!\bmod x))$ $y$ $x$

Se conseguirmos apenas potências de para , ainda podemos tentar calcular Para cada . Um deles será um divisor não trivial de , exceto no caso lamentável em que existe um tal que é coprime para e divide . Isso é equivalente a dizer que $2$ $y$ $\gcd(x,(2^n)!)$ $n\le\log x$ $x$ $n$ $x$ $(2^n)!$ $(2^{n+1})!$ $x$ é livre de quadrados e todos os seus principais fatores têm o mesmo comprimento de bit. Não sei o que fazer nesse caso (bastante importante, cf. números inteiros de Blum).

Emil Jeřábek apoia Monica
fonte

Se a relação se mantém (para todos

), então talvez ele também detém (com uma escolha diferente de

) quando um substitui

com outro (pequeno) prime,

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