Cuántas cpu necesario para comprobar de 100 millones de dígitos de los números primos de una manera eficiente?

Question

Si yo tuviera acceso a la número potencialmente grande de Cpu y quería comprobar rápidamente los 100 millones de números de dos dígitos durante primalidad a través de un mapa-reducir la arquitectura, cuántas Cpu sería necesario? Cada una de las asignadas a las instancias informáticas que iba a realizar eficiente comprueba el número en cuestión se ha asignado un rango de divisores (por ejemplo, Ejemplo 1: comprueba que los divisores de 2-1000, Ejemplo 2: comprueba que los divisores de 1001-2000, etc...).

Definiciones:

rápidamente los medios de comprobación de un único divisor en contra de los 100 millones de dígitos del número en cuestión de horas.

división eficiente significa sólo la comprobación de los números impares hasta la raíz cuadrada. Inferior divisores sería sólo la conocen los números primos para acelerar la velocidad de cálculo.

1 de la CPU es el equivalente de la capacidad de CPU de 1.0-1.2 GHz 2007 Opteron o 2007 Xeon.

Sí, sé que hay mejores algoritmos como las queratosis actínicas, pero tengo que ser capaz de dividir el trabajo entre el mapeado de los casos. Si hay una mejor manera de dividir y conquistar soy todo oídos.

La mejor pregunta probablemente sería: ¿cuál es la relación matemática entre el número de CPUs y la cantidad de tiempo que toma para verificar un número de una magnitud dada de dígitos?

Yo estoy pidiendo esto porque estoy tratando de averiguar el número de Mapa de Reducir los casos necesitaría para comprar en Amazon AWS para hacer el cálculo factible (un par de meses/menos de un año).

Answer 1

Supongamos por un momento que se fijan en este juicio-división formulario de pruebas de primalidad. Si usted dio a cada equipo de 1000 números de prueba (lo que se sugiere), entonces usted necesitará alrededor de $\large10^{5*10^7 - 3}$ equipos. (¿Por qué? - la raíz cuadrada de $10^{10^8}$$10^{5 * 10^7}$). También probable que necesite un nuevo tipo de datos, como una de las cien millones de dígitos de la misma tome más de un gigabyte de memoria (y no hablemos acerca de la viabilidad de las operaciones).

Afortunadamente, simplemente encontrar un primer parcialmente a compensar el costo, ya que este sería el más grande primer conocidos hasta la fecha. Cuánto más grande? Cerca de 90 millones de dígitos más grande que el actual, el más grande conocido prime.

En definitiva, este no es factible de acuerdo a los métodos actuales. Y el más grande de los números primos son los números Primos de Mersenne, que son mucho más fáciles de la prueba. E incluso entonces, los programas que probado eran muy ingenioso.

Su último bit: ¿cuál es la relación entre el número de CPUs y el tiempo que toma la prueba, en realidad no es tan trivial. Uno podría imaginar que en el principio, hay una cierta cantidad de trabajo de cálculo de W a hacer, y dividiendo entre x equipos significaría que cada equipo lleva $\frac{1}{x}$ cantidad de tiempo. Pero eso no es cómo iba a funcionar - como se supone que sabemos exactamente cómo dividir el trabajo. Es más difícil hacer operaciones entre números grandes, por ejemplo, por lo que el equipo trato con los números más grandes en realidad se las arregla 1000 de ellos, que va a terminar almacenar más de un terabyte de información sobre las cifras de ser probado, sin contar las mismas operaciones (por suerte, no en un tiempo - tal vez sólo varios conciertos a la vez). El número más pequeño equipo nunca golpea a un megabyte. De modo que es difícil, demasiado. Pero uno puede enlazado el esfuerzo por asumir que los equipos no funcionan de forma sinérgica, y hacerlo no es mejor que el $\frac{1}{x}$ del tiempo.

Answer 2

Hay alrededor de $\sqrt{x}/2\log x$ prepara para la prueba, con $x\approx10^{10^8}$. El tamaño promedio de los números primos será de más de 20 MB, pero supongamos que usted tiene algunos super-GPU que puede manejar los números de ese tamaño. Además, es tan rápido como un procesador de 3 GHz, y que puede hacer un multiprecision división en un ciclo. (Esto es absurdamente generoso; en realidad podría tomar miles de millones de ciclos.) Con mil núcleos, usted puede hacer casi de $10^{20}$ divisiones por año, por lo que necesita $$ \frac{\sqrt{10^{10^8}}}{2\registro de\a la izquierda(10^{10^8}\right)}\cdot\frac{1}{10^{20}}= \frac{10^{5\cdot10^7}}{2\cdot10^{28}\log10}\approx2.17\cdot10^{49999971} $$ de estas GPU equipos para terminar en un año. Si pesan un gramo cada uno, esto es aproximadamente el $3.62\cdot10^{49999915}$ de veces la masa del universo.

---

Por otro lado, si usted utiliza una técnica moderna como fastECPP, se necesitarían sólo $8.8\cdot10^{20}$ procesador días, extrapolando a partir de la hora de la toma para el registro de 2011 a prueba. Así que para conseguir esto se hace en un mes tendría sólo acerca de 3,500,000,000,000,000,000 8-core instancias. Estoy seguro de que Amazon iba a dar un descuento para este tipo de compra a granel...

Dividir el trabajo no sería trivial; esto supone el mejor de los casos, donde puede escribirse de manera eficiente.

Answer 3

Como otros han señalado, la división de juicios no es, simplemente, la manera de ir sobre ella. Básicamente la aplicación de métodos que daría el primer factorización (en lugar de simplemente la prueba de primalidad).

Como una indicación de lo que los números son challanging incluso sofisticados métodos de factorización en costosas de hardware, podemos mirar el RSA números. RSA-768 fue factorizada por un equipo de expertos utilizando el campo de número de tamiz método:

1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

Esto ha 232 dígitos decimales. Estamos hablando de 100000000 dígitos, usando mucho menos eficiente.

---

De manera más realista, si usted quiere encontrar de 100 millones de dígitos, el primer por golpear el problema con una serie de equipos (presumiblemente con el fin de reclamar el premio de 150.000 dólares aquí), que me sugieren los siguientes pasos:

• Encontrar una clase de números (como Proth números) en la que primalidad puede ser demostrado de manera eficiente.

• Generar una larga lista de candidatos de los números de esta forma, y realizar la prueba de la división (es decir, tamizado) en esta lista con el fin de deshacerse de los no primos.

• Ejecutar el eficiente primalidad de prueba para cada uno de los candidatos en equipos independientes.

Esto es como lo demostró la primalidad de el (en el tiempo) 629-ésimo más grande que se conoce prime (ref.). Hay ya muy eficiente software que puede hacer esto para usted (NewPGen para el cribado, y el PRESTAMISTA en última instancia para las pruebas de primalidad).

Usted puede esperar que esto requiere de varios años, ser costoso y causa innecesarias CO$_2$ de las emisiones. También se puede esperar a ser aplastado por una de las miles de personas que están haciendo la misma cosa.

Answer 4

No me refiero al hilo en cualquiera de los dedos de los pies, así que por favor me perdone si lo hago.

Yo no soy un Matemático, pero estoy ejecutando cuatro instancias de Cudalucas en la GTX 690 Gpu para un par de días y ahora su Eta está diciendo 190 días para la prueba de cuatro 100 millones de dígitos de los números primos de mersenne. aceptar su largo tiempo de espera ( y, probablemente, otra de 190 días para comprobarla) se le dijo que no que no es un número primo, pero mucho más corto que los cálculos anteriores.

Saludos

Rob.