¿Cómo factorizó Cole$2^{67}-1$ en 1903?

Question

Acabo de escuchar una this American Life episodio que relató la famosa anécdota sobre Frank Nelson Cole factoring $N:=2^{67}-1$ como $193{,}707{,}721\times 761{,}838{,}257{,}287$. No parece ser un registro histórico de cómo Cole logrado esto; todos tenemos que podía encontrar en su declaración que le tomó "a tres años de los domingos". Ira Glass invitado, Pablo Hoffman, sugiere que esto se hizo mediante la prueba de la división.

Pero esto es una locura, a menos que me falta algo. Tres años de los domingos es $156$ días. Si trabaja $10$ horas del día, que es $93{,}600$ minutos. Hay $10{,}749{,}692$ números primos hasta $193{,}707{,}721$. Así que es más que $100$ ensayo de las divisiones de un minuto. Peor que eso, existente primer tablas no ir lo suficientemente alta: de Acuerdo con el Capítulo XIII de Dickson de la Historia de la Teoría de los Números, las tablas existentes de los números primos sólo corrió a algo como $10{,}000{,}000$ ($664{,}579$ de los números primos), por lo que para la gran mayoría de las divisiones de juicios, él tendría que encontrar los números primos en primer lugar. (Lehmer, en 1914, fue a $10{,}006{,}721$.)

Pero estoy perplejo pensando qué otra cosa Cole podría haber hecho. Yo desnatada en el Capítulo XIV, en Dickson. Los métodos que parecen haber existido en el tiempo son:

• Varias maneras para acelerar la prueba de la división para la primera $1000$'s de los números primos. Que sólo ayuda en el inicio.

• Escrito $N$ como $x^2-y^2$. Pero $y$ serían $380{,}822{,}274{,}783$, lo que es aún más la búsqueda.

• Desde $2$ es un cuadrado modulo $N$ (es decir, $(2^{34})^2 \equiv 2 \mod N$), sabemos que todos los factores primos deben ser $\pm 1 \bmod 8$, lo que reduce el tiempo a la mitad. Pero esto es sólo un factor de $2$.

• Desde $N \equiv 3 \mod 4$, debe haber un primer factor que es $3 \bmod 4$, por lo que podríamos tratar sólo la comprobación de los números primos. Pero esto resulta para empeorar las cosas, desde el PEQUEÑO factor es el que es $1 \bmod 4$.

• Si podía escribir $N$ como una suma de los cuadrados de dos maneras, nos gustaría hacer. Pero $N$ no es una suma de cuadrados, ya que es $3 \bmod 4$. Las generalizaciones a otros positiva definida cuadráticas formas eran conocidos en el momento, pero, ¿cómo iba a Cole saber que una forma cuadrática a probar?

• Una variante de la anterior, sería el uso de la forma cuadrática $2x^2-y^2$, puesto que ya tienen una solución. Dickson no mencionar el trabajo con una mezcla de formas de firma, pero que funcionaría. Y desde $\mathbb{Z}[\sqrt{2}]$ es un PID, debe haber una segunda forma de escribir $N$ como $2x^2-y^2$, no relacionado con el anterior por las unidades de $\mathbb{Z}[\sqrt{2}]$. No estoy seguro de cómo es de grande esta segunda solución.

Entonces, mi pregunta es:

¿Cómo podría alguien encontrar los factores primos de $N$ en $100{,}000$ minutos de la mano de cálculo?

Answer 1

Resumiendo lo que, dice Cole para mi propio entendimiento: Por los métodos que él no hace claro para mí, Cole encontrado soluciones a $x^2 \equiv a \bmod N$ para muchos pequeños valores de $a$ y convenció a sí mismo (pero no rigurosa) que muchos otros $a$ no eran alcanzables. Esto dio muchos congruencia condiciones posibles divisores de $N$. De esta manera, fue rápidamente capaz de filtrar los números enteros de hasta el $16$ millones a solo un par de juicio divisores, ninguno de los cuales trabajó. (Nota que está bien si termina tratando de no-primos divisores en el proceso).

En este punto, hizo uso de sus datos de una manera diferente. Supongamos que $N=pq$ y la mirada en uno de sus pequeños valores de $a$, por ejemplo,$a=-7$. Porque él conocía a $-7$ era cuadrada modulo $N$, podemos deducir que $p$ e $q$ son cada $ 1$ , $2$ o $4 \bmod 7$ y, desde $2^{67}-1 \equiv 1 \bmod 7$, obtenemos que $(p,q)$ es $(1,1)$, $(2,4)$ o $(4,2) \bmod 7$. Esto significa que $(p+q)/2 \equiv 1$ o $3 \bmod 7$. De esta manera, ha conseguido modular condiciones en $(p+q)/2$, dando un par de posibilidades. Para cada posibilidad de $x$, se comprueba si $x^2-N$ era cuadrada. Cuando se trató de la opción de la derecha, había $x^2-N = ((p+q)/2)^2 - N = ((p-q)/2)^2$ y ganó.

Answer 2

Se supone que él hizo sus cálculos a mano, pero que no es una necesidad. En el momento, calculadoras mecánicas (arithmometers) fueron ampliamente disponibles. No es en absoluto inusual que el tipo de persona a la que dedica los domingos a la factorización es el dueño de uno.

Estas máquinas son órdenes de magnitud más rápido y preciso que haciendo los cálculos a mano. Este modelo de 1875 podía manejar números de 20 dígitos, por ejemplo. ($2^{67}$ 21 dígitos).

La multiplicación de dos números en uno de ellos se lleva un par de segundos. Para multiplicar 761838257287 por 193707721, por ejemplo (suponiendo que se ajuste en la máquina, que no es el caso de la máquina en la imagen --- se pueden multiplicar dos de diez números de dos dígitos en la mayoría, de forma nativa), tendrías que:

• reinicia la máquina girando una pequeña restablecer la manivela o interruptor.
• deslice hacia arriba y hacia abajo de los 10 lineal de los interruptores en la parte inferior derecha, uno por uno, a las posiciones correspondientes a los dígitos de 761838257287.
• gire la manivela de una vez, a continuación, deslice la parte superior de la losa a la derecha por una muesca, a continuación, gire la manivela de nuevo 2 veces, luego mover la losa, a continuación, enciéndalo de 7 veces, y así sucesivamente para cada dígito del segundo número, para un total de 1+9+3+7+0+7+7+2+1 = 37 los giros. El número de vueltas en cada posición se muestra en un indicador, para reducir los errores. (los diez pequeños agujeros circulares en la parte superior de la lineal interruptores, creo).
• a continuación puedes leer los dígitos del resultado en la fila superior, de 20 de rotación de los indicadores.

Del mismo modo, para dividir (con resto) un cierto número de $A<10^{20}$ por $B<10^{10}$, puede hacer lo siguiente, que imita directamente grado de división de la escuela:

• configurar el equipo de manera que la parte superior de mover fila muestra el número de $A$
• deslice la parte superior de la losa a la derecha de un cierto número de $k$ de las víctimas, por lo que el dígito más significativo de $A$ está alineado con el dígito más significativo de $B$.
• gire la manivela en la dirección inversa entre 0 y 10 veces; cada vez resta $10^k B$ de $A$. Parar cuando iba a llegar por debajo de cero. En la práctica, estas máquinas de trabajo modulo $10^{20}$, y muchos de los modelos que hacen un sonido de campana cuando se mueve por debajo de cero; por lo que en la práctica se había gire la manivela hasta que escuche el timbre, a continuación, hacer una vuelta atrás.
• deslice la parte superior de la losa una muesca a la izquierda, y continuar restando múltiplos de $10^{k-1}B$ a partir del número de la fila superior. Continuar hasta que la parte superior de la losa está de vuelta a la posición original (lo que significa que usted está restando múltiplos de $10^{0}B$ y no puede deslizarse a la izquierda nada más. A continuación, puedes leer el resto de la fila superior, y el cociente en una pequeña (apenas visible aquí) de la fila de los números por debajo de ella, que siguió la pista de cuántas vueltas se hicieron en cada posición.

Yo no tengo mucha habilidad manual con estas máquinas, pero parece que el método podría ser realizado en un completamente inconscientes de manera --- gire la manivela hasta que escuche el timbre, a su vez de nuevo una vez, deslice a la izquierda, repita.

Answer 3

Mientras que la cuestión de cómo Cole factorizada $N := 2^{67}−1$ ya ha sido contestada por el cilindro, David Speyer más general, la pregunta es cómo alguien podría encontrar los factores de los que número de $100000$ minutos de la mano de la computación.

Suponiendo que se trataría de rho de Pollard algoritmo de cálculo y la secuencia de $x_1 := 1$, $x_{k+1} := (x_k^2+1) \!\! \mod n$, a continuación, se encontrará que $\gcd(x_{8064} - x_{2536},n) = 193707721$. Esto requiere de $2 \cdot 8063 = 16126$ multiplicaciones mod $n$ (en la práctica un poco más, ya que uno no toma Mcd del después de cada paso), y tomar un par de Mcd con $n$. Ahora, haciendo una multiplicación modulo un $21$-número de dígitos en $6$ minutos por lado es tal vez difícil, pero verosímil posible.

Otra opción sería probar la criba cuadrática. En este caso, tratamos de ver si lo que FactInt's MPQS hace rutina podría ser hecho a mano así. --

FactInt elige un factor de base de tamaño de $92$, y la toma de $4096$ a medida que la longitud de la tamizado intervalo. Con esto, se tarda $8$ polinomios hasta que encuentra lo suficientemente factorizations sobre el factor de base (incluidas las relaciones con un gran factor) para obtener una factorización de $N$. Hacer el tamizado con la mano en el estándar de A4 $5$mm cuadrado de papel, marcando plazas requeriría $2$ hojas de papel para cada intervalo de cribado de $4096$ números, como hay $41 \cdot 58 = 2378$ plazas en cada hoja, de ahí el tamizado tomaría total $8 \cdot 2 = 16$ hojas de papel.

Finalmente, será necesario encontrar la nullspace de un dispersas $\mathbb{F}_2$ matriz con $114$ columnas y un par más filas, de los cuales uno podría escribir en $6$ de dicho hojas de papel cuadriculado pegan si uno usa una plaza para cada entrada. Haciendo eliminación Gaussiana ahora probablemente será un poco tedioso a mano y es probable que tomar el resto de la escritura de notas, pero es evidente que no será factible con una oferta de tiempo tan generoso como el asumido $100000$ minutos.

Answer 4

Me imagino que tomó Cole ya que él dijo. Si yo fuera a emprender el proyecto, aquí es cómo iba a proceder:

Me gustaría empezar tamizando el conjunto de números {134 k + 1} de números primos. Uno puede modificar la Criba de Eratóstenes para producir algunos de los números primos de forma rápida y, a continuación, sólo hacer algunos de los miembros de la progresión aritmética si son primos o no (es decir, aquellos en los coprime a 2310).

Yo podría hacer la prueba de la división, pero para los grandes números, exponenciación modular/ de la multiplicación es el camino a seguir. Puedo hacer una tabla de hasta 2^33 de potencias de dos. Dados p, I multiplicar por la mayor potencia de 2 menor que p a obtener un producto de menos de p y, a continuación, haga doble con cuidado y restar p, y, a continuación, repita hasta que llego a 2^67 mod p. Lo bueno de esto es que no se puede aprovechar de un trabajo anterior: Si tengo 2^s = p + K para algunos pequeños K, el siguiente primo p = p +r tiene 2^s = p + (K-r) + r, y por lo que algunos trabajos se pueden guardar en algunas iteraciones. Puedo ver el procesamiento de dos o tres números primos en paralelo de esta manera con la mano.

Gerhard "de Extrañar Que en TI Fue Utilizado" Paseman, 2015.05.22