?

Mientras leía el blog de Dick Lipton, me topé con el siguiente hecho cerca del final de su publicación de Bourne Factor :

Si, por cada $n$ , existe una relación de la forma
$(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}$ donde $m = poly(n)$ , y cada una de las $a_k$ , $b_k$ y $c_k$ son $poly(n)$ en longitud de bits, entonces la factorización tiene circuitos de tamaño polinómico.

En otras palabras, el $(2^n)!$ , que tiene un número exponencial de bits , potencialmente se puede representar de manera eficiente.

Tengo algunas preguntas:

¿Podría alguien proporcionar una prueba de la relación anterior, decirme el nombre y / o proporcionar alguna referencia?
Si tuviera que darle $n$ , $m$ cada una de las $a_k$ , $b_k$ y $c_k$ , ¿podría proporcionarme un algoritmo de tiempo polinómico para verificar la validez de la relación (es decir, está en $NP$ )?

ds.algorithms reference-request factoring comp-number-theory usuario834
fuente

¿Esa publicación de blog no afirma lo contrario? Es decir, si las ecuaciones de la forma anterior

tiene soluciones en general , entonces la factorización tiene circuitos de tamaño polinómico.

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

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

mikero

Creo que en realidad escribiste lo contrario de lo que escribió Dick Lipton. Él dice que si tal ecuación existe para cada

, entonces la factorización tiene circuitos de tamaño polinómico. Entonces, la implicación es que si la factorización es no uniformemente difícil (para infinitas

), entonces las ecuaciones de la forma anterior no existen (para infinitas

n

$n$

n

$n$

n

$n$

Sasho Nikolov

@mikero, SashoNikolov, ambos tienen razón, disculpen. He editado mi pregunta.

user834

tenga en cuenta que "algoritmo de tiempo polinómico" generalmente significa un algoritmo uniforme. La publicación de Lipton solo afirma la existencia de una familia de circuitos polisize para factoraje.

Sasho Nikolov

Tenga en cuenta que para que esta propiedad sea verdadera,

deben ser

en tamaño de bit / como se indica en el blog de Lipton /, y

como enteros . Tu definición no está 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

Respuestas:

¡Comentaré por qué una relación como en la pregunta (por cada ) ayuda a factorizar. No puedo terminar la discusión, pero tal vez alguien pueda.

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

La primera observación es que una relación como la anterior (¡y más generalmente, la existencia de circuitos aritméticos de tamaño polivinílico para ) Da un circuito de tamaño polivinílico para calcular $(2^n)!$ para dado en binario: simplemente evalúe la suma del módulo , usando exponenciación mediante cuadratura repetida. $(2^n)!\bmod x$ $x$ $x$

Ahora, si pudiéramos calcular para arbitraria , podríamos factorizar : usando la búsqueda binaria, encontrar la más pequeña de manera que (que podemos calcular usando ). Entonces debe ser el divisor primo más pequeño de . $y!\bmod x$ $y$ $x$ $y$ $\gcd(x,y!)\ne1$ $\gcd(x,(y!\bmod x))$ $y$ $x$

Si solo podemos hacer potencias de para , todavía podemos intentar calcular Por cada . ¡Uno de estos será un divisor no trivial de , excepto en el caso desafortunado cuando hay un tal que es coprimo a , y divide . Esto es equivalente a decir que $2$ $y$ $\gcd(x,(2^n)!)$ $n\le\log x$ $x$ $n$ $x$ $(2^n)!$ $(2^{n+1})!$ $x$ no tiene cuadrados, y todos sus factores primos tienen la misma longitud de bits. No sé qué hacer en este caso (más bien importante, ver números enteros de Blum).

Emil Jeřábek apoya a Monica
fuente

Si la relación se cumple (para todo

), entonces quizás también se cumple (con una elección diferente de

) cuando uno reemplaza

por otro (pequeño) primo,

. ¡Presumiblemente se podría buscar hasta que se encuentre una

tal que

sea coprimo a

y no

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