?

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$

ds.algorithms reference-request factoring comp-number-theory 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

?

Odpowiedzi: