?

Czytając blog Dicka Liptona, natknąłem się na następujący fakt pod koniec jego posta Bourne Factor :

Jeśli dla każdego istnieje relacja formy , gdzie , a każdy z , i są na długości bitowej, a następnie faktoring ma obwody wielomianowe. $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)$

Innymi słowy, $(2^n)!$ , który ma wykładniczą liczbę bitów , może być potencjalnie reprezentowany efektywnie.

Mam parę pytań:

Czy ktoś może dostarczyć dowód powyższej relacji, podać mi imię i / lub podać jakieś referencje?
Gdybym miał dać ci , i każdy z , i , czy mógłbyś podać mi algorytm wielomianowy do sprawdzenia poprawności relacji (tj. Czy jest to w )? $n$ $m$ $a_k$ $b_k$ $c_k$ $NP$

— użytkownik834
źródło

Czy ten post na blogu tak naprawdę nie jest sprzeczny? To znaczy, jeśli równania powyższej postaci

mają rozwiązania w ogóle , następnie faktoring ma obwody wielomianowe.

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

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

— mikero

Myślę, że faktycznie napisałeś odwrotność tego, co napisał Dick Lipton. Mówi, że jeśli takie równanie istnieje dla każdego

, to faktoring ma wielomianowe obwody wielkości. Zatem implikacja jest taka, że jeśli faktoring jest niejednorodnie trudny (dla nieskończenie wielu

), wówczas równania powyższej postaci nie istnieją (dla nieskończenie wielu

n

$n$

n

$n$

n

$n$

— Sasho Nikolov

@mero, SashoNikolov, oboje macie rację, przepraszam. Zredagowałem swoje pytanie.

— user834

zauważ, że „algorytm wielomianowy” zwykle oznacza jednolity algorytm. Post Liptona potwierdza jedynie istnienie rodziny obwodów wielogatunkowych do faktoringu.

— Sasho Nikolov

Należy zauważyć, że, aby ta własność być prawdziwe,

powinno

w rozmiarze bitowym / jak podano na Lipton strony / i

w postaci liczb całkowitych . Twoja definicja nie jest jasna.

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

Skomentuję, dlaczego relacja jak w pytaniu (dla każdego

(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$ ) pomaga w faktorowaniu. Nie jestem w stanie dokończyć dyskusji, ale może ktoś może.

Pierwszą obserwacją jest to, że relacja jak wyżej (i bardziej ogólnie, istnienie wielowymiarowych obwodów arytmetycznych dla ) Daje obwód wielowymiarowy do obliczeń dla podany binarnie: po prostu oceń sumę modulo $(2^n)!$ $(2^n)!\bmod x$ $x$ $x$ , używając potęgowania przez powtarzanie kwadratu.

$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$ is coprime to $(2^n)!$ , and divides $(2^{n+1})!$ . This is equivalent to saying that $x$ is square-free, and all its prime factors have the same bit-length. I don’t know what to do in this (rather important, cf. Blum integers) case.

— Emil Jeřábek supports Monica
źródło

If the relation holds (for all

n

$n$ ), then perhaps it also holds (with a different choice of

a_{k}

$a_k$ ,

b_{k}

$b_k$ and

c_{k}

$c_k$ ) when one replaces

2

$2$ with another (small) prime,

p

$p$ . One could presumably search until a

p

$p$ is found such that

x

$x$ is coprime to

(p^{n})!

$(p^n)!$ and not

(p^{n + 1})!

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

— user834