PDF de programación - Algoritmo Genético vs. Algoritmos Clásicos para Factorización de Números Enteros Grandes

Algoritmo Genético vs. Algoritmos Clásicos para

Factorización de Números Enteros Grandes

Departamento de Ingeniería Eléctrica – Sección de Computación

Daniel Cortés Rivera

CINVESTAV



Resumen.
En éste trabajo se propone la utilización de un algoritmo genético (AG), para encontrar la
factorización de un número entero grande. La solución que se tiene para número menores a
128 bits, es no muy buena comparado con los algoritmos actuales para la factorización,
pero están puestos los ojos en que para números de mayor tamaño pueda comportarse
mejor, refinando la técnica, desde luego modificando los parámetros del algoritmo genético
en cuestión. El algoritmo genético utilizado para la factorización es el clásico, que utiliza
representación binaria, selección de ruleta, cruza uniforme, mutación uniforme, y remoción
de duplicados. Al final se presentan los resultados obtenidos, pero eso no significa que sea
todo lo que haya que hacer.

1>n
y n–

se dice que es un número primo (o solamente un primo) si los divisores de
. Hay un número infinito de primos, los cuatro primeros son 2, 3, 5 y 7.

y n no es primo, entonces se dice que n es compuesto. El entero 1 no es primo ni

1>n

Introducción.
Un entero
n son 1–
Si
compuesto.
La teoría fundamental de la aritmética dice que cada entero positivo puede ser expresado
como un producto finito de números primos, y esta factorización es única excepto por el
orden de los factores. La tabla 1 tiene algunos ejemplos de factorizaciones.

1990 = 2 · 5 · 199
1991 = 11 · 181
1992 = 23 · 3 · 83
1993 = 1993
1994 = 2 · 997
Tabla 1: Ejemplos de Factorización
La existencia de esta factorización es una fácil consecuencia de la definición de un número
primo y del principio del orden. La prueba es ligeramente difícil. Sin embargo la existencia
de esta prueba da una clave sobre la eficiencia en la búsqueda de los factores de un entero
grande. La factorización ha sido la fascinación de los matemáticos por siglos. Gauss
escribió [1, p.398]:
“El problema de distinguir números primos de los compuestos, y descomponer números
compuestos en sus factores primos, es algo de lo más importante y útil de la aritmética. El
honor de la ciencia parece demandar que todos ayuden a la solución que celosamente los ha
cautivado.”


2000 = 24 · 53
2001 = 3 · 23 · 29
2002 = 2 · 7 · 11 · 13 2007 = 32 · 223
2008 = 23 · 251
2003 = 2003
2009 = 72 · 41
2004 = 22 · 3 · 167

1995 = 3 · 5 · 7 · 19
1996 = 22 · 499
1997 = 1997
1998 = 2 · 33 · 37
1999 = 1999

2005 = 5 · 401
2006 = 2 · 17 · 59

n

£b

12

99
a –
n b

y n pequeñas. Brent et al [3] extendió las tablas hasta

Algunos libros son fieles a clasificar los factores de un número de una forma especial. La
1–nb
más referenciada es la tabla de Cunningham [2], que lista los factores conocidos de

£b
. Algunas de
para bases
estas factorizaciones aparecen en [4], que además tienen algunos factores
. Brillhart
et al [5] dan la factorización de los números de Fibonacci y los relacionados con los
números de Lucas. El reto de RSA [6] es construir una tabla de factores de la partición de
un número.

La factorización fue originalmente de interés académico. Esta ha ganado en la práctica una
gran importancia después de la introducción del sistema criptográfico de llave pública
RSA. La fortaleza de RSA está basada en la dificultad de factorizar números enteros
grandes.

Sea N un entero grande compuesto. Hasta los 1960s, el mejor algoritmo para factorizar N
tomaba un tiempo
. Tal algoritmo es la división trivial, que trata de
dividir N por todos los primos inferiores a N . Esto cambio cuando Morrison y Brillhart
[7] introducen el método de la fracción continua, cuyo tiempo es [8]:
(

0>e

para

eNO

(

)(

)

1

)

2

log

N

log

log

N

log

log

N

=

NO

(
2

+

( )
)
1

o

+

o

2

( )
1

e

.

log

N

1–P

Modernos algoritmos para factorizar N caen en dos categorías. Los algoritmos en la
primera categoría encuentran pequeños factores primos rápidamente. Esto incluye la
división trivial, Pollard Rho,
, y el método de curvas elípticas. Los algoritmos en la
segunda categoría factorizan al número sin tener en cuenta el tamaño de los factores
primos, pero el costo aumenta considerablemente con enteros grandes. Dentro de estos
algoritmos se incluyen: fracciones continuas (continued fractions), cuadrados sin retención
(quadratic sieve) y campos de números sin retención (number field sieve).

En la práctica, los algoritmos de ambas categorías son importantes. Dado un entero grande
sin alguna pista sobre el tamaño de los factores, típicamente se prueba con la primera
categoría hasta que se encuentra algún cofactor del número original que sea suficientemente
pequeño. Hasta ese momento se comienza a probar con la segunda categoría.

La interpretación de suficientemente pequeño ha cambiado considerablemente con el
avance de la tecnología. En los 1960s, John Brillhart y John Selfridge [7, p. 87] que
factorizar un número con más de 25 dígitos era un problema grande. En los 1970s, Richard
Guy [8, p. 82] decía que pocos números sobre 80 dígitos podrían ser factorizados. En 1994
se ha llegado hasta 100 – 120 dígitos.


Factorizando enteros.

Uno de los más prominentes problemas de la teoría computación numérica es la
factorización de enteros, que es sumamente simple de describir a cualquiera sin necesidad
de tener un gran conocimiento en matemáticas. Mientras no se conoce un algoritmo
eficiente para la factorización, los niños saben hacer la multiplicación eficientemente, que


ł


Ł

es la operación inversa de la factorización. Otra razón importante sobre el problema de la
factorización, es su crucial importancia en la criptografía. La seguridad de algunos
protocolos y sistemas criptográficos esta basado en asumir que es difícil la factorización de
los enteros grandes, típicamente el producto de dos números primos grandes. El
descubrimiento de un algoritmo eficiente para factorizar tendría un dramático impacto en la
criptografía y en particular en miles de sistemas de seguridad implementados alrededor del
mundo.

Por simplicidad, y sin perdida de generalidad se considera el problema de la factorización
de un entero como la tarea de encontrar los factores de un número dado.

Mientras no se encuentre el tan aclamado algoritmo eficiente para la factorización, se
intentan muchos métodos para tratar de factorizar un número entero compuesto grande, y es
el caso que se presenta en este reporte, donde se propone para la factorización de un
número entero grande un algoritmo genético.


Algoritmos Genéticos.
Los algoritmos genéticos (denominados originalmente “planes reproductivos genéticos”)
fueron desarrollados por John H. Holland a principios de 1960s, motivado por resolver
problemas de aprendizaje de máquina.


Algoritmo.
El algoritmo genético enfatiza la importancia de la cruza sexual (operador principal) sobre
el de la mutación (operador secundario), y usa selección probabilística.
El algoritmo básico es el siguiente:

§ Generar (aleatoriamente) una población inicial.
§ Calcular aptitud de cada individuo.
§ Seleccionar (probabilísticamente) con base a su aptitud.
§ Aplicar operadores genéticos (cruza y mutación) para generar la siguiente

población.

§ Ciclar hasta que cierta condición se satisfaga.


La representación tradicional es la binaria, tal y como se ejemplifica en la figura 1.
A la cadena binaria se le llama “cromosoma”. A cada posición de la cadena se le denomina
“gene” y al valor dentro de esta posición se le denomina “alelo”.

Para poder aplicar el algoritmo genético se requiere de los 5 componentes básicos
siguientes:

§ Una representación de las soluciones potenciales del problema.
§ Una forma de crear una población inicial de posibles soluciones (normalmente un

proceso aleatorio).

§ Una función de evaluación que juegue el papel del ambiente, clasificando las

soluciones en términos de su “aptitud”.

§ Operadores genéticos que alteren la composición de los hijos que se producirán para

las siguientes generaciones.

§ Valores para los diferentes parámetros que utiliza el algoritmo genético (tamaño de
población, probabilidad de cruza, probabilidad de mutación, número máximo de
generaciones, etc.)



¿Cuándo debe usarse un algoritmo genético?
Es adecuado si el espacio de búsqueda es grande, accidentado, poco comprendido, o si la
función de aptitud tiene mucho ruido, y si la tarea no requiere que se encuentre el óptimo
global (encontrar una solución bastante buena con cierta rapidez resulta suficiente).

Sí el espacio de búsqueda es muy pequeño, entonces el problema se puede resolver por
medio de búsqueda exhaustiva, y el AG no tiene mucha razón de ser.

Sí el espacio de búsqueda no está accidentado y es unimodal, entonces una técnica de
gradiente como “escalando la colina con ascenso pronunciado”, será mucho más eficiente
que un algoritmo genético.

Sí el espacio de búsqueda se conoce bien, es posible diseñan métodos de búsqueda que usen
conocimiento específico sobre el dominio para superar fácilmente una
técnica
independiente del dominio como el AG. Si la función de aptitud tiene ruido, un método de
búsqueda que solo candidato a la vez será arrastrada inevitablemente por las rutas erróneas
debido al ruido, mientras que el algoritmo genético tendrá un desempeño razonable porque
trabaja mediante la acumulación de estadísticas de aptitud a través de las generaciones.

Los consejos anteriores