Sin utilizar ninguna función de factorización / polinomio incorporada, factorice un polinomio completamente en irreductibles sobre los enteros o un campo finito.
Entrada
Su programa / función recibirá algún número primo (o cero) n
como entrada. El campo / anillo es el campo finito de ese orden (es decir Z/nZ
), o solo Z
si lo n
es 0
. Su programa puede fallar si no lo n
es 0
o es un primer. El polinomio estará en F[x]
.
Su programa / función también recibirá el polinomio como entrada.
Hay cierta flexibilidad en la entrada, asegúrese de especificar cómo piensa recibirla. Por ejemplo, el polinomio podría ingresarse como una lista de coeficientes, o en la forma que la mayoría de la gente espera (ej . 50x^3 + x^2
:), o en alguna otra forma razonable. O el formato de entrada del campo / anillo también podría ser diferente.
Salida
Su programa / función generará el polinomio factorizado completamente. Puede dejar múltiples raíces expandidas (es decir, en (x + 1)(x + 1)
lugar de (x + 1)^2
). Puede eliminar espacios en blanco entre operadores binarios. Puede reemplazar la yuxtaposición con *
. Puede insertar espacios en blanco en lugares extraños. Puede reordenar los factores en el orden que desee. El x
término podría ser simplemente (x)
. x
se puede escribir como x^1
; Sin embargo, el término constante puede no tener x^0
. Se permiten +
signos extraños. Es posible que no tenga un término con un 0
frente, deben omitirse. El término principal de cada factor debe ser positivo, los signos negativos deben estar afuera.
Casos de prueba, su programa debería poder producir resultados para cada uno de estos en un tiempo razonable (por ejemplo, <= 2 horas):
Entrada: 2, x^3 + x^2 + x + 1
Salida: (x + 1)^3
Entrada: 0, x^3 + x^2 + x + 1
Salida: (x + 1)(x^2 + 1)
Entrada: 0, 6x^4 – 11x^3 + 8x^2 – 33x – 30
Salida: (3x + 2)(2x - 5)(x^2 + 3)
Entrada: 5, x^4 + 4x^3 + 4x^2 + x
Salida: x(x + 4)(x + 4)(x + 1)
Entrada: 0, x^5 + 5x^3 + x^2 + 4x + 1
Salida: (x^3 + 4x + 1)(x^2 + 1)
Un agradecimiento especial a Peter Taylor por criticar mis casos de prueba
p
tiene los elementos{0, 1, ... , p-1}
y está bajo el modo de suma / multiplicaciónp
. Básicamente, reduzca cualquier coeficiente por modp
y estará bien. Además, tenga en cuenta que si tiene una raíz, es decir, un factor lineal, uno de{0, ... , p-1}
ellos producirá0
(modp
) cuando esté conectado al polinomio.Z
es factorizarZ/pZ
para unp
levantamiento adecuado y luego Hensel. Sin embargo, el enfoque golfable es probablemente (y esta es ciertamente la ruta que estoy mirando) usar un límite simple en la altura de los factores y la fuerza bruta.Respuestas:
GolfScript (222 bytes)
Demostración en línea
Notas
n
seguido por una matriz de coeficientes GolfScript de los más significativos a los menos significativos. Por ejemplo,0, x^5 + 5x^3 + x^2 + 4x + 1
debe formatearse como0 [1 0 5 1 4 1]
.Z
. Lo manejoZ
usando una forma relajada del límite de altura de Mignotte. Un gran artículo sobre límites de altura en la factorización es Bounds on Factors in Z [x] , John Abbott, 2009 (el enlace es para preimpresión arxiv; su CV dice que ha sido aceptado por el Journal of Symbolic Computation ). La forma más relajada dada es en términos de la norma L-2, pero para guardar bytes me relajo aún más y uso la norma L-1 en su lugar. Entonces es un caso de fuerza bruta por división de juicio.Z
es solo un anillo y, por lo tanto, es necesario hacer una división de prueba por factores candidatos no monicos. Me las arreglo para no implementar números racionales haciendo una prueba de división de factor principal y acumulando un indicador de "error"e
.Z
es generalmente más lento y no se puede probar con la demostración en línea. Sin embargo, el más lento de los casos de prueba oficiales toma 10 minutos, lo cual está dentro del límite de tiempo "razonable".fuente