La factorización de la rueda es una mejora del método de división de prueba para la factorización de enteros .
El método de división de prueba consiste en dividir el número a factorizar sucesivamente por los primeros enteros (2, 3, 4, 5, ...) hasta encontrar un divisor. Para la factorización de la rueda, se parte de una pequeña lista de números, denominada base , generalmente los primeros números primos ; luego se genera la lista, llamada rueda , de los enteros que son coprimos con todos los números de la base. Luego, para encontrar el divisor más pequeño del número a factorizar, se divide sucesivamente por los números en la base y en la rueda.
Con la base {2, 3}, este método reduce el número de divisiones a 1/3 <34% del número necesario para la división de prueba. Las bases más grandes reducen aún más esta proporción; por ejemplo, con base {2, 3, 5} a 8/30 <27% ; y con base {2, 3, 5, 7} a 48/210 <23% .
Un ejemplo típico
Con una base dada de los primeros números primos {2, 3, 5}, el "primer giro" de la rueda consiste en:
- 7, 11, 13, 17, 19, 23, 29, 31 .
El segundo turno se obtiene sumando 30, el producto de la base, a los números del primer turno. El tercer turno se obtiene sumando 30 al segundo turno, y así sucesivamente.
Para implementar el método, se puede observar que los incrementos entre dos elementos consecutivos de la rueda, es decir
- inc = [4, 2, 4, 2, 4, 6, 2, 6],
siguen siendo los mismos después de cada turno.
La implementación sugerida que sigue usa una función auxiliar div ( n , k ), que prueba si n es divisible por k , y devuelve verdadero en este caso, falso en caso contrario. En esta implementación, el número a factorizar es n , y el programa devuelve el divisor más pequeño de n , devolviendo n si es primo.
si div ( n , 2) = verdadero entonces devuelve 2 si div ( n , 3) = verdadero luego devuelve 3 si div ( n , 5) = verdadero luego devuelve 5 k : = 7; i : = 1 while k * k ≤ n do si div ( n , k ) = true, entonces devuelve k k : = k + inc [ i ] si i <8 entonces i : = i + 1 si no i : = 1 return norte
Para obtener la factorización completa de un número entero, el cálculo puede continuar sin reiniciar la rueda al principio. Esto conduce al siguiente programa para una factorización completa, donde la función "agregar" agrega su primer argumento al final del segundo argumento, que debe ser una lista.
factores: = [] mientras que div ( n , 2) = verdadero hacer factores: = sumar (2, factores) n : = n / 2 mientras div ( n , 3) = verdadero hacer factores: = sumar (3, factores) n : = n / 3 mientras div ( n , 5) = verdadero hacer factores: = sumar (5, factores) n : = n / 5 k : = 7; i : = 1 mientras k * k ≤ n hacer si div ( n , k ) = verdadero entonces sumar ( k , factores) n : = n / k si no k : = k + inc [ i ] si i <8 entonces i : = i + 1 más i : = 1 return add ( n , factores)
Otra presentacion
La factorización de rueda se utiliza para generar listas de números primos en su mayoría a partir de una fórmula matemática simple y una lista mucho más pequeña de los primeros números primos. Estas listas pueden usarse luego en divisiones de prueba o tamices . Debido a que no todos los números en estas listas son primos, hacerlo introduce operaciones redundantes ineficientes. Sin embargo, los propios generadores requieren muy poca memoria en comparación con mantener una lista pura de números primos. La pequeña lista de números primos iniciales constituye parámetros completos para que el algoritmo genere el resto de la lista. Estos generadores se denominan ruedas . Si bien cada rueda puede generar una lista infinita de números, después de cierto punto, los números dejan de ser primos en su mayoría.
El método se puede aplicar además de forma recursiva como un tamiz de rueda de números primos para generar ruedas más precisas. Paul Pritchard [1] [2] [3] [4] realizó gran parte del trabajo definitivo sobre factorización de ruedas, tamices que utilizan factorización de ruedas y tamiz de ruedas, al formular una serie de algoritmos diferentes. Para visualizar el uso de una rueda de factorización, se puede comenzar escribiendo los números naturales alrededor de círculos como se muestra en el diagrama adyacente. El número de radios se elige de manera que los números primos tengan una tendencia a acumularse en una minoría de los radios.
Ejemplo de procedimiento gráfico
- Encuentra los primeros números primos para formar la base de la rueda de factorización. Se conocen o tal vez se determinan a partir de aplicaciones anteriores de ruedas de factorización más pequeñas o al encontrarlas rápidamente usando el Tamiz de Eratóstenes .
- Multiplica los números primos básicos para obtener el resultado n, que es la circunferencia de la rueda de factorización.
- Escribe los números del 1 al n en un círculo. Este será el círculo más interno que representa una rotación de la rueda.
- Desde los números 1 an en el círculo más interno, tache todos los múltiplos de los números primos base del paso uno como se aplicó en el paso 2. Esta eliminación de números compuestos se puede lograr mediante el uso de un tamiz como el Tamiz de Eratóstenes o como el resultado de aplicaciones de ruedas de factorización más pequeñas.
- Tomando x como el número de círculos escritos hasta ahora, continúe escribiendo xn + 1 en xn + n en círculos concéntricos alrededor del círculo más interno, de modo que xn + 1 esté en la misma posición que ( x - 1) n + 1.
- Repita el paso 5 hasta que el círculo de rotación más grande abarque el número más grande para probar la primalidad.
- Tacha el número 1.
- Tacha los radios de los números primos como se encuentra en el paso 1 y aplica en el paso 2 en todos los círculos externos sin tachar los números primos en el círculo más interno (en el círculo 1).
- Tacha los radios de todos los múltiplos de números primos tachados del círculo interior 1 en el paso 4 de la misma manera que tacha los rayos de los números primos base en el paso 8.
- Los números restantes en la rueda son en su mayoría números primos (colectivamente se denominan primos "relativamente"). Use otros métodos como el Tamiz de Eratóstenes o la aplicación adicional de ruedas de factorización más grandes para eliminar los no primos restantes.
Ejemplo
1. Encuentra los primeros 2 números primos: 2 y 3.
2. n = 2 × 3 = 6
3.
1 2 3 4 5 6
4. tacha los factores 2 y 3 que son 4 y 6 como factores 2; 6 ya que el único factor de 3 ya está anulado:
1 2 3456
5. x = 1.
xn + 1 = 1 · 6 + 1 = 7.
( x + 1) n = (1 + 1) · 6 = 12.
Escriba 7 a 12 con 7 alineado con 1.
1 2 34567 8 9 10 11 12
6. x = 2.
xn + 1 = 2 · 6 + 1 = 13.
( x + 1) n = (2 + 1) · 6 = 18.
Escriba 13 a 18.
Repita para las siguientes líneas.
1 2 34567 8 9 10 11 1213 14 15 16 17 1819 20 21 22 23 2425 26 27 28 29 30
7 y 8. Tamizado
12 345678910 11 1213141516 17 1819202122 23 2425262728 29 30
9. Tamizado
12 3456789101112131415161718192021222324252627282930
10. La lista resultante contiene un número no primo de 25 que es 5 2 . Utilice otros métodos como un tamiz para eliminarlo y llegar a
2 3 5 7 11 13 17 19 23 29
Tenga en cuenta que al usar exactamente el siguiente número primo de 5 ciclos de rueda y eliminar el múltiplo (s) de ese primo (y solo ese primo) de la lista resultante, hemos obtenido la rueda base según el paso 4 para una rueda de factorización con base primos de 2, 3 y 5; esta es una rueda por delante de la rueda de factorización 2/3 anterior. Luego, se podrían seguir los pasos hasta el paso 10 usando el siguiente primo sucesivo de 7 ciclos y solo eliminando los múltiplos de 7 de la lista resultante en el paso 10 (dejando algunos primos "relativos" en este caso y todos los casos sucesivos, es decir, algunos no son verdaderos primos totalmente calificados), para obtener la siguiente rueda más avanzada, repitiendo de forma recursiva los pasos según sea necesario para obtener ruedas sucesivamente más grandes.
Análisis e implementación informática
Formalmente, el método hace uso de las siguientes ideas: Primero, que el conjunto de primos base unidos con su conjunto (infinito) de coprimos es un superconjunto de primos. En segundo lugar, que el conjunto infinito de coprimos se puede enumerar fácilmente desde los coprimos hasta el conjunto base entre 2 y el producto del conjunto base. (Tenga en cuenta que 1 requiere un manejo especial).
Como se ve en el ejemplo anterior, el resultado de aplicaciones repetidas del procedimiento recursivo anterior de los pasos 4 a 10 puede ser una lista de rueda que abarca cualquier rango de tamizado deseado (al cual se puede truncar) y la lista resultante incluye solo los múltiplos de primos superiores a uno después de los últimos primos base utilizados.
Tenga en cuenta que una vez que una rueda alcanza el límite superior deseado del rango de tamizado, uno puede dejar de generar más ruedas y usar la información en esa rueda para seleccionar los números compuestos restantes de esa última lista de ruedas usando una técnica de tipo Tamiz de Eratóstenes pero usando el espacio. patrón inherente a la rueda para evitar descartes redundantes; Es posible que se puedan realizar algunas optimizaciones basándose en el hecho de que (se probará en la siguiente sección) que no habrá selección repetida de ningún número compuesto: cada compuesto restante se eliminará exactamente una vez. Alternativamente, se puede continuar generando listas de ruedas truncadas usando números primos hasta la raíz cuadrada del rango de tamiz deseado, en cuyo caso todas las representaciones de números restantes en la rueda serán primos; sin embargo, aunque este método es tan eficiente como para no descartar números compuestos más de una vez, pierde mucho tiempo fuera de las operaciones de descarte normalmente consideradas en el procesamiento de los sucesivos barridos de rueda, de modo que toma mucho más tiempo. La eliminación de números compuestos mediante una rueda de factorización se basa en lo siguiente: Dado un número k> n, sabemos que k no es primo si k mod n y n no son primos relativos. A partir de eso, se puede determinar la fracción de números que elimina el tamiz de la rueda (aunque no todos necesitan ser eliminados físicamente; muchos pueden eliminarse automáticamente en las operaciones de copia de ruedas menores a ruedas mayores) como 1 - phi (n) / n, que también es la eficiencia del tamiz.
Se sabe que
donde γ es la constante de Euler . [5] Por lo tanto, phi (n) / n llega a cero lentamente a medida que n aumenta hasta el infinito y se puede ver que esta eficiencia aumenta muy lentamente al 100% para n infinitamente grande. A partir de las propiedades de phi, se puede ver fácilmente que el tamiz más eficiente menor que x es aquel en el que y (es decir, la generación de la rueda puede detenerse cuando la última rueda pasa o tiene una circunferencia suficiente para incluir el número más alto en el rango de tamizado).
Para ser de máximo uso en una computadora, queremos los números que son menores que ny relativamente primos como un conjunto. Usando algunas observaciones, el conjunto se puede generar fácilmente:
- Empezar con , que es el set para con 2 como primer primo. Este conjunto inicial significa que todos los números que comienzan en dos se incluyen como primos "relativos" ya que la circunferencia de la rueda es 1.
- Los siguientes conjuntos son lo que significa que comienza en 3 para todos los números impares con los factores de 2 eliminados (circunferencia de 2), tiene los factores de 2 y 3 eliminados (circunferencia de 6) como para la rueda base inicial en el ejemplo anterior y así sucesivamente.
- Dejar ser el conjunto donde k se ha agregado a cada elemento de .
- Luego dónde representa la operación de eliminar todos los múltiplos de x.
- 1 y serán los dos más pequeños de Cuándo eliminando la necesidad de calcular los números primos por separado, aunque el algoritmo necesita mantener un registro de todos los números primos básicos eliminados que ya no se incluyen en los conjuntos siguientes.
- Todos los conjuntos donde la circunferencia n> 2 son simétricos alrededor , reduciendo los requisitos de almacenamiento. El siguiente algoritmo no utiliza este hecho, pero se basa en el hecho de que los espacios entre números sucesivos en cada conjunto son simétricos alrededor del punto medio.
Ver también
Referencias
- ^ Pritchard, Paul, "Tamices lineales de números primos: un árbol genealógico", Sci. Computación. Programming 9 : 1 (1987), págs. 17–35.
- ^ Paul Pritchard, Un tamiz aditivo sublineal para encontrar números primos, Comunicaciones del ACM 24 (1981), 18-23. Señor 600730
- ^ Paul Pritchard, Explicación del tamiz de rueda, Acta Informatica 17 (1982), 477–485. SEÑOR685983
- ^ Paul Pritchard, Tamices de números primos compactos rápidos (entre otros), Journal of Algorithms 4 (1983), 332-344. SEÑOR729229
- ^ Hardy y Wright 1979 , thm. 328
enlaces externos
- Factorización de ruedas
- Tamices de números primos incrementales mejorados por Paul Pritchard