¿Por qué no los algoritmos genéticos trabajan en problemas como el de la factorización de RSA?

Question

Hace algún tiempo yo estaba bastante interesado en GAs y estudié acerca de ellos un poco.He usado C++ GAlib a escribir algunos programas y me quedé bastante sorprendido por su capacidad para resolver de otra manera difícil de calcular problemas, en cuestión de segundos.Que les parece un gran bruteforcing técnica que funciona muy, muy inteligente y se adapta.

Estaba leyendo un libro por Michalewitz, si recuerdo correctamente el nombre y todo parecía estar basado en el Esquema Teorema, demostrado por el MIT.

También he oído que no puede ser utilizado para el planteamiento de problemas como el factoring RSA con claves privadas.

Podría alguien explicar por qué este es el caso ?

Answer 1

El algoritmo genético no es inteligente en absoluto , son algoritmos muy codiciosos optimizantes. Todos trabajan alrededor de la misma idea. Usted tiene un grupo de puntos ('una población de individuos'), y usted transforma a ese grupo en otro con operador estocástico, con un sesgo en la dirección de la mejor mejora ('mutación + cruce + selección'). Repita hasta que convergue o esté cansado de ello, nada inteligente allí.

Para un algoritmo genético para trabajar, una nueva población de puntos debe desempeñarse cerca de la población de puntos anteriores. Poca perturbación debe crea poco cambio. Si, después de una pequeña perturbación de un punto, obtiene un punto que representa una solución con un rendimiento completamente diferente, entonces, el algoritmo no es nada mejor que la búsqueda aleatoria, generalmente no es un buen algoritmo de optimización. En el caso RSA, si sus puntos son directamente los números, es sí o no, solo al voltear un poco ... Por lo tanto, usar un algoritmo genético no es mejor que la búsqueda aleatoria, si representa el problema de RSA sin mucho pensamiento "Vamos a pensar Puntos de búsqueda de código como los bits de los números "

Answer 2

Yo diría porque la factorización de las claves no es un problema de optimización, sino un problema exacto.Esta distinción no es muy precisa, así que aquí hay detalles. Los algoritmos genéticos son excelentes para resolver problemas donde son los mínimos (locales / globales), pero no hay ninguno en el problema factible.Algoritmo genético como DCA o recocido simulado necesita una medida de "lo cerca que soy de la solución", pero no puede decir esto por nuestro problema.

Para un ejemplo de la genética problemática es bueno, está el problema de la escalada en la colina.

Answer 3

El gas se basa en la evaluación de la aptitud de las soluciones candidatas.

Básicamente, tiene una función de acondicionamiento físico que lleva a una solución candidata como entrada y le devuelve un escalar que le dice lo bueno que es el candidato.Luego continúe y permite a las mejores personas de una generación dada para aparearse con mayor probabilidad que el resto, de modo que la descendencia será (con suerte) más 'FIT' en general, y así sucesivamente en .

No hay manera de evaluar la forma física (qué tan bueno es una solución candidata en comparación con el resto) en el escenario de factorización RSA, por eso no puede usarlos.

Answer 4

GAs no son fuerza bruta, es sólo un algoritmo de búsqueda.Cada GA esencialmente se parece a esto:

candidates = seed_value;
while (!good_enough(best_of(candidates))) {
    candidates = compute_next_generation(candidates);
}

Donde good_enough y best_of se define en términos de una función de aptitud.Una función de aptitud dice cómo así que un candidato se soluciona el problema.Ese parece ser el problema principal aquí:¿cómo se escribe una función de aptitud para la factorización?Por ejemplo, 20 = 2*10 o 4*5.Las tuplas (2,10) y (4,5) son claramente los ganadores, pero ¿y los demás?Cómo "ajuste" es (1,9) o (3,4)?

Answer 5

Indirectamente, lo que puede el uso de un algoritmo genético para el factor de un número entero N.Dixon de la factorización de enteros método utiliza las ecuaciones de participación de los poderes de la primera k los números primos, modulo N.Estos productos de potencias de primos pequeños son llamados "suave".Si estamos usando la primera k=4 los números primos - {2,3,5,7} - 42=2x3x7 es suave y 11 no es por falta de un mejor término, 11 es "bruto").Dixon método requiere una invertible k x k la matriz consta de los exponentes que definen estos liso números.Para más información sobre Dixon del método ver https://en.wikipedia.org/wiki/Dixon%27s_factorization_method.

Ahora, volviendo a la pregunta original:Hay un algoritmo genético para encontrar las ecuaciones de Dixon del método.

1. Vamos r ser la inversa de un buen número de mod N - tan r es un número aproximado
2. Vamos s ser suave
3. Generar soluciones aleatorias de rx = sy mod N.Estas soluciones [x,y] son la población para el algoritmo genético.Cada x, y tiene un suave componente y áspero de un componente.Por ejemplo, supongamos que x = 369 = 9 x 41.Entonces (suponiendo que 41 no es lo suficientemente pequeño como para contar como suave), la pieza en bruto de x es de 41 y la parte lisa es 9.
4. Elegir los pares de soluciones - "los padres" - combinar en combinaciones lineales con cada vez menos áspero partes.
5. El algoritmo termina cuando un par de [x,y] se encuentra con áspero partes [1,1], [1,-1],[-1,1] o [-1,-1].Esto da lugar a una ecuación de Dixon del método, debido a que rx=sy mod N y r es el único número aproximado a la izquierda: x y y son suaves, y s empezó suave.Pero incluso en 1/r mod N es suave, así que es todo lo suave!

Cada vez que se combinan dos pares - dicen [v,w] y [x,y] - el buen partes de los cuatro números que se ocultan, excepto para los factores de las piezas lisas de la v y x compartir, y los factores que las piezas lisas de w y y compartir.Así que elegimos a los padres que comparten las piezas lisas en la mayor medida posible.Para hacer este preciso, escribir

g = mcd(parte lisa de v, parte lisa de x)

h = gcd(parte lisa de la w, la parte lisa de y)

[v,w], [x,y] = [g v/g, h l/h], [x g/g, h s/h].

El duro-ganado suave factores g y h se conserva en la próxima generación, pero las piezas lisas de v/g, w/h, x/g y s/h va a ser sacrificados con el fin de combinar [v,w] y [x,y].Así que elegimos a los padres para que v/g, w/h, x/g y s/h tienen la más pequeña de las piezas lisas.De esta manera podemos realmente hacer en coche por la áspera partes de nuestras soluciones para rx = sy mod N de una generación a la siguiente.

Answer 6

En el pensamiento adicional, la mejor manera de enfrentar los coeficientes lisos X, Y en el Axe de celosía= por MOD N está con regresión, no con un algoritmo genético.

Se realizan dos regresiones, una con respuestas vector R0 que consiste en valores X de las soluciones elegidas al azar de AX= por MOD N; y el otro con respuesta vector R1 que consiste en valores Y de las mismas soluciones. Ambas regañas usan la misma matriz explicativa X. en X son columnas que consisten en las columnas que consisten en los restos de los divisores suaves de módulo de valores X, y otras columnas que consisten en los restos del módulo de valores Y otros divisores suaves.

La mejor opción de divisores suaves es el que minimiza los errores de cada regresión:

e0= R0 - X (Inverso de (X-Transpose) (X)) (X-Transpose) (R0)

e1= r1 - x (inverso de (x-transposición) (x)) (X-Transpose) (R1)

Lo que sigue es las operaciones de la fila a Annihilate X. Luego, aplique un resultado Z de estas operaciones de fila a los valores X- y Y de las soluciones originales desde las cuales se formó X.

z R0 = z R0 - 0
     = z R0 - zX (inverse of (X-transpose)(X)) (X-transpose) (R0)
     = z E0 

de manera similar, z r1= z e1

Tres propiedades ahora se combinan en Z R0 y Z R1:

• son múltiplos de grandes números suaves, porque Z aniquilates los números suaves de Modulo.
• son relativamente pequeños, ya que E0 y E1 son pequeños.
• Como cualquier combinación lineal de soluciones a AX= por MOD N, Z R0 y Z R1 son soluciones en sí mismas a esa ecuación.

  Un múltiplo relativamente pequeño de un número liso grande puede ser el número suave en sí. Tener una solución suave de AX= por MOD N produce una entrada a Método de Dixon.

  Dos optimizaciones hacen de esto particularmente rápido:

  • No hay necesidad de adivinar todos los números y columnas suaves de x a la vez. Puede ejecutar regresiones continuamente, agregando una columna a X a la vez, la elección de columnas que más reducen E0 y E1. En ningún momento se seleccionarán dos números suaves con un factor común.
  • También puede comenzar con muchas soluciones aleatorias de zx= por mod n, y eliminar los más grandes errores entre las selecciones de las nuevas columnas para x.