Fatorar um polinômio sobre um campo finito ou os números inteiros

20

Sem usar nenhuma função interna de fatoração / polinômio, fatore um polinômio completamente em irredutíveis sobre os números inteiros ou em um campo finito.

Entrada

Seu programa / função receberá algum número primo (ou zero) ncomo entrada. O campo / anel é o campo finito dessa ordem (ou seja Z/nZ), ou apenas Zse nfor 0. Seu programa pode falhar se nnão for 0ou for primo. O polinômio será inserido F[x].

Seu programa / função também receberá o polinômio como entrada.

Há alguma flexibilidade na entrada, certifique-se de especificar como você pretende receber entrada. Por exemplo, o polinômio pode ser inserido como uma lista de coeficientes, ou na forma que a maioria das pessoas espera (ex:) 50x^3 + x^2, ou em alguma outra forma razoável. Ou o formato de entrada do campo / toque também pode ser diferente.

Saída

Seu programa / função produzirá o polinômio fatorado completamente. Você pode deixar várias raízes expandidas (ou seja, em (x + 1)(x + 1)vez de (x + 1)^2). Você pode remover o espaço em branco entre operadores binários. Você pode substituir a justaposição por *. Você pode inserir espaços em branco em lugares estranhos. Você pode reorganizar os fatores na ordem que desejar. O xtermo poderia ser apenas (x). xpode ser escrito como x^1; no entanto, o termo constante pode não ter x^0. +Sinais estranhos são permitidos. Você pode não ter um termo com um 0na frente, eles devem ser deixados de fora. O termo principal de cada fator deve ser positivo, os sinais negativos devem estar fora.

Nos casos de teste, seu programa deve ser capaz de produzir saída para cada um deles em tempo razoável (por exemplo, <= 2 horas):

Entrada: 2, x^3 + x^2 + x + 1

Saída: (x + 1)^3

Entrada: 0, x^3 + x^2 + x + 1

Saída: (x + 1)(x^2 + 1)

Entrada: 0, 6x^4 – 11x^3 + 8x^2 – 33x – 30

Saída: (3x + 2)(2x - 5)(x^2 + 3)

Entrada: 5, x^4 + 4x^3 + 4x^2 + x

Saída: x(x + 4)(x + 4)(x + 1)

Entrada: 0, x^5 + 5x^3 + x^2 + 4x + 1

Saída: (x^3 + 4x + 1)(x^2 + 1)

Agradecimentos especiais a Peter Taylor por criticar meus casos de teste

Justin
fonte
1
Eu acho que isso está me dando um flashback de algumas das matemáticas mais difíceis da graduação . Estou indo na direção certa aqui?
Digital Trauma
1
Isso me lembra do tempo eu tinha pesadelos tentando imprimir polinômios corretamente ...
SP3000
Lamento não ter entendido, mas qual é o primeiro número de entrada que deve fazer? ou como isso afeta a saída?
Optimizer
@Optimizer O primeiro número de entrada determina em qual campo / números inteiros você está trabalhando. Se o número for diferente de zero, você estará trabalhando no campo finito desse pedido. Um campo finito de ordem ppossui os elementos {0, 1, ... , p-1}e está sob o modo de adição / multiplicação p. Basicamente, reduza qualquer coeficiente por mod pe você é bom. Além disso, observe que, se tiver uma raiz, ou seja, um fator linear, um dos dois {0, ... , p-1}produzirá 0(mod p) quando estiver conectado ao polinômio.
267 Justin justin
1
@ flawr, a abordagem padrão para fatorar sobre Zé fatorar Z/pZpara um pelevador adequado e depois Hensel. No entanto, a abordagem do jogo de golfe provavelmente é (e certamente esse é o caminho que estou vendo) usar um limite simples na altura dos fatores e força bruta.
Peter Taylor

Respostas:

17

GolfScript (222 bytes)

~.@:[email protected]\{abs+}/2@,2/)?*or:^{\1$^base{^q- 2/-}%.0=1=1$0=q>+{{:D[1$.,2$,-)0:e;{.0=0D=%e|:e;(D(@\/:x@@[{x*~)}%\]zip{{+}*q!!{q%}*}%}*e+])0-{;0}{@;@\D.}if}do}*;\).^3$,)2/?<}do;][[1]]-{'('\.,:x;{.`'+'\+'x^'x(:x+x!!*+\!!*}%')'}/

Demonstração online

Notas

  1. O formato de entrada é nseguido por uma matriz de coeficientes GolfScript do mais ao menos significativo. Por exemplo, 0, x^5 + 5x^3 + x^2 + 4x + 1deve ser formatado como 0 [1 0 5 1 4 1].
  2. Em um campo finito, existem apenas muitos polinômios de grau suficientemente pequeno para serem relevantes. No entanto, este não é o caso Z. Eu manejo Zusando uma forma relaxada da altura de Mignotte. Um ótimo artigo sobre limites de altura na fatoração é o Bounds on Factors in Z [x] , John Abbott, 2009 (o link é para a pré-impressão arxiv; seu currículo diz que foi aceito pelo Journal of Symbolic Computation ). A forma mais relaxada dada existe em termos da norma L-2, mas para economizar bytes, relaxo ainda mais e uso a norma L-1. Então é um caso de força bruta pela divisão de julgamento.
  3. Sobre um campo finito, todo polinômio é vezes constante um polinômio monônico, então eu só faço a divisão de teste por polinômios mônicos e salvo um recíproco no campo. No entanto, Zé apenas um anel e, portanto, é necessário fazer a divisão do teste por fatores candidatos não-monônicos. Consigo evitar a implementação de números racionais, realizando um teste de divisão de fatores e acumulando um sinalizador de "erro" e.
  4. Ambos os pontos 2 e 3 implicam que o caso de fatorar sobre Zé geralmente mais lento e não pode ser testado com a demonstração online. No entanto, o mais lento dos casos de teste oficiais leva 10 minutos, o que está dentro do prazo "razoável".
Peter Taylor
fonte