El proyecto Cunningham
El proyecto Cunningham es un proyecto, iniciado en 1925, para factorizar números de la forma b n ± 1 para b = 2, 3, 5, 6, 7, 10, 11, 12 y n grande . El proyecto lleva el nombre de Allan Joseph Champneys Cunningham , quien publicó la primera versión de la tabla junto con Herbert J. Woodall . [1] Hay tres versiones impresas de la tabla, la más reciente publicada en 2002, [2] así como una versión en línea. [3]
De un número de Cunningham se pueden derivar dos tipos de factores sin tener que usar un algoritmo de factorización: factores algebraicos, que dependen del exponente, y factores de Aurifeuillian, que dependen tanto de la base como del exponente.
para k impar . Además, b 2 n − 1 = ( b n − 1)( b n + 1). Así, cuando m divide a n , b m − 1 y b m + 1 son factores de b n − 1 si el cociente de n sobre m es par; solo el primer número es un factor si el cociente es impar. b m + 1 es un factor de b n − 1, si m divide a n y el cociente es impar.
Cuando el número tiene una forma particular (la expresión exacta varía con la base), se puede utilizar la factorización aurifeuliana, que da un producto de dos o tres números. Las siguientes ecuaciones dan factores de Aurifeuillian para las bases del proyecto de Cunningham como producto de F , L y M : [4]
Sea b = s 2 · k con k libre de cuadrados , si una de las condiciones se cumple, entonces tenga la factorización de Aurifeuillian.
Una vez que se eliminan los factores algebraicos y aurifeulianos, los otros factores de b n ± 1 son siempre de la forma 2 kn + 1, ya que todos son factores de [ cita requerida ] . Cuando n es primo, tanto los factores algebraicos como los de Aurifeuillian no son posibles, excepto los factores triviales ( b − 1 para b n − 1 y b + 1 para b n + 1). Para los números de Mersenne , los factores triviales no son posibles para primos n , por lo que todos los factores son de la forma 2 kn + 1. En general, todos los factores de ( b n − 1)/( b − 1) son de la forma 2 kn + 1, donde b ≥ 2 y n es primo, excepto cuando n divide a b − 1, en cuyo caso ( b n − 1)/( b − 1) es divisible por n mismo.