¿Cuál es la complejidad del peor caso del tamiz de campo numérico?

Dada compuesto $N\in\Bbb N$ tamiz campo de número general es mejor algoritmo de factorización conocida para la factorización de enteros de $N$ . Es un algoritmo aleatorio y obtenemos una complejidad esperada de $O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)$ con el factor $N$ .

Busqué información sobre la complejidad del peor de los casos en este algoritmo aleatorio. Sin embargo, no puedo localizar la información.

(1) ¿Cuál es la complejidad del peor caso del tamiz de campo numérico?

(2) ¿ También se puede eliminar la aleatoriedad aquí para dar un algoritmo subexponencial determinista?

reference-request derandomization factoring average-case-complexity worst-case
fuente

Respuestas:

$e^{O(2\sqrt{2}\sqrt{\log n\log\log n})}$

$x$ $x^2 \pmod{n}$ $n$ $n$

La complejidad nominal para el peor de los casos de todos estos algoritmos es infinita: en el caso del tamiz cuadrático y el tamiz de campo numérico, siempre puede generar la misma , mientras que en el método de curva elíptica siempre puede generar la misma curva elíptica. . Hay muchas formas de evitar esto, por ejemplo, ejecutar un algoritmo de tiempo exponencial en paralelo. $x$

Yuval Filmus
fuente

Dado que también tocaste el ECM: conocemos un algoritmo aleatorio subexp para calcular en tiempo usando ECM donde es desconocido y aleatorio. ¿Tiene una estimación de cuántas pruebas de este algoritmo son suficientes para obtener y donde ?

n! r

$n!r$

O (e x p (\sqrt{\log n}))

$O(exp(\sqrt{\log n}))$

r

$r$

n! r

$n!r$

n! s

$n!s$

(r, s) = 1

$(r,s)=1$

No tengo idea de qué es , pero en términos generales, al elegir parámetros en ECM, estamos equilibrando entre la probabilidad que la curva sea lo suficientemente suave y el tiempo de ejecución requerido para probar cada curva. Por lo general, el punto de equilibrio es cuando .Por lo tanto, el número esperado de pruebas debería ser .

n! r

$n!r$

p

$p$

T

$T$

1 / p \approx T

$1/p \approx T$

O (\exp \sqrt{\log n})

$O(\exp\sqrt{\log n})$

Yuval Filmus

n!

$n!$ es factorial de . Es un problema abierto obtener la complejidad lineal de factorial. Sabemos cómo calcular donde es desconocido en tiempo subexp. Si conocemos dos y , podemos obteneren tiempo subexp si .

n

$n$

n! r

$n!r$

r

$r$

n! r

$n!r$

n! s

$n!s$

(n! r, n! s) = n!

$(n!r,n!s)=n!$

(r, s) = 1

$(r,s)=1$

Recuerdo calcular hace un tiempo. No creo que pueda obtener una mejora ya que hubo una captura y no recuerdo los detalles.

El último párrafo parece extraño y podría aclararse más. ¿Estás hablando de un escenario en el que el RNG está "roto" en el sentido de que no muestra el espacio de distribución general? ¿Pero entonces el paralelismo no ayudaría allí? porque sería el mismo RNG "roto" en paralelo? ¿O es la idea de que sería un RNG diferente ejecutado en paralelo? complejidad realidad paralela de algoritmos de factorización es realmente un conjunto el otro tema complejo, por ejemplo, algunos se pueden parallelized mejor que otros, de orden O puede que no sea exactamente aplicable, etc

VZN

En los últimos meses, se ha analizado rigurosamente una versión del tamiz de campo numérico: http://www.fields.utoronto.ca/talks/rigorous-analysis-randomized-number-field-sieve-factoring

Básicamente, el peor tiempo de ejecución es incondicionalmente y bajo GRH. Esto no es para el tamiz de campo numérico "clásico", sino una versión ligeramente modificada que aleatoriza más pasos para facilitar el análisis de complejidad. $L_n(1/3, 2.77)$ $L_n(1/3, (64/9)^{1/3})$

Creo que el documento correspondiente todavía está bajo revisión.

Actualización: El periódico ya salió. Jonathan D. Lee y Ramarathnam Venkatesan, "Análisis riguroso de un tamiz de campo numérico aleatorizado", Journal of Number Theory 187 (2018), pp. 92-159, doi: 10.1016 / j.jnt.2017.10.019

djao
fuente

¿Puede dar una referencia más completa sobre dónde podemos aprender más, con título, autor y dónde se publica, para que la respuesta siga siendo útil incluso si el enlace deja de funcionar?

Dado que el resultado se anunció recientemente, creo que actualmente está bajo revisión como se indica en mi respuesta y, por lo tanto, aún no se ha publicado. Actualizaré mi respuesta en el futuro cuando la información de publicación esté disponible.

djao

FWIW no parece estar en arxiv.org. Sin embargo, el autor es Ramarathnam Venkatesan, que puede ayudar en futuras búsquedas si fuera necesario.

Peter Taylor

En realidad es una obra de dos autores (JD Lee y R. Venkatesan): cmi.ac.in/activities/…

Sary