Factoriser un polynôme sur un corps fini ou les entiers

20

Sans utiliser de fonctions d'affacturage / polynôme intégrées, factorisez complètement un polynôme en irréductibles sur les entiers ou un champ fini.

Contribution

Votre programme / fonction recevra un nombre premier (ou zéro) nen entrée. Le champ / anneau est le champ fini de cet ordre (c'est-à-dire Z/nZ), ou juste Zs'il l' nest 0. Votre programme peut échouer s'il nne l'est pas 0ou s'il s'agit d' un programme principal. Le polynôme sera en F[x].

Votre programme / fonction recevra également le polynôme en entrée.

Il y a une certaine flexibilité dans l'entrée, assurez-vous de spécifier comment vous avez l'intention de recevoir l'entrée. Par exemple, le polynôme peut être entré sous forme de liste de coefficients, ou sous la forme que la plupart des gens attendent (ex:) 50x^3 + x^2, ou sous une autre forme raisonnable. Ou le format de saisie du champ / anneau peut également être différent.

Production

Votre programme / fonction affichera le polynôme factorisé complètement. Vous pouvez laisser plusieurs racines étendues (c'est- (x + 1)(x + 1)à- dire au lieu de (x + 1)^2). Vous pouvez supprimer les espaces entre les opérateurs binaires. Vous pouvez remplacer la juxtaposition par *. Vous pouvez insérer des espaces dans des endroits étranges. Vous pouvez réorganiser les facteurs dans l'ordre que vous souhaitez. Le xterme pourrait bien être (x). xpeut être écrit comme x^1; cependant, le terme constant peut ne pas avoir x^0. Les +signes étrangers sont autorisés. Vous ne pouvez pas avoir un terme avec un 0devant, ils doivent être laissés de côté. Le terme principal de chaque facteur doit être positif, les signes négatifs doivent être extérieurs.

Cas de test, votre programme devrait être en mesure de produire une sortie pour chacun d'eux dans un délai raisonnable (disons <= 2 heures):

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

Production: (x + 1)^3

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

Production: (x + 1)(x^2 + 1)

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

Production: (3x + 2)(2x - 5)(x^2 + 3)

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

Production: x(x + 4)(x + 4)(x + 1)

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

Production: (x^3 + 4x + 1)(x^2 + 1)

Un merci spécial à Peter Taylor pour avoir critiqué mes cas de test

code-golf math polynomials abstract-algebra Justin
la source
1
Je pense que cela me donne un flash-back sur certains des mathématiques de premier cycle les plus difficiles . Suis-je même dans la bonne direction ici?
Digital Trauma
1
Cela me rappelle le temps où j'avais des cauchemars essayant d' imprimer correctement les polynômes ...
Sp3000
Désolé que je n'ai pas compris, mais quel est le premier numéro d'entrée censé faire? ou comment cela affecte-t-il la sortie?
Optimizer
@Optimizer Le premier numéro d'entrée détermine le champ / les entiers sur lesquels vous travaillez. Si le nombre est différent de zéro, vous travaillez sur le champ fini de cette commande. Un champ d'ordre fini pa les éléments {0, 1, ... , p-1}et il est sous mod d'addition / multiplication p. Fondamentalement, réduisez n'importe quel coefficient par mod pet vous êtes bon. Notez également que s'il a une racine, c'est-à-dire un facteur linéaire, l'un des {0, ... , p-1}produira 0(mod p) lorsqu'il sera branché sur le polynôme.
Justin
1
@flawr, l'approche standard de l'affacturage Zconsiste à prendre en Z/pZcompte un pascenseur approprié , puis Hensel. Cependant, l'approche golfable est probablement (et c'est certainement la voie que je regarde) d'utiliser une simple limite sur la hauteur des facteurs et de la forcer brutalement.
Peter Taylor

Réponses:

17

GolfScript (222 octets)

~.@:[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!!*+\!!*}%')'}/

Démo en ligne

Remarques

  1. Le format d'entrée est nsuivi d'un tableau GolfScript de coefficients du plus important au moins significatif. Par exemple, 0, x^5 + 5x^3 + x^2 + 4x + 1devrait être formaté comme 0 [1 0 5 1 4 1].
  2. Sur un champ fini, il n'y a qu'un nombre fini de polynômes suffisamment petits pour être pertinents. Mais ce n'est pas le cas Z. Je gère Zen utilisant une forme détendue de la hauteur de Mignotte. Un excellent document sur les limites de hauteur dans l'affacturage est Bounds on Factors in Z [x] , John Abbott, 2009 (le lien est vers la préimpression arxiv; son CV dit qu'il a été accepté par le Journal of Symbolic Computation ). La forme la plus détendue qui y soit donnée est en termes de norme L-2, mais pour économiser des octets, je me détends davantage et utilise la norme L-1 à la place. Ensuite, c'est un cas de forçage brutal par la division de première instance.
  3. Sur un champ fini, chaque polynôme est un temps constant un polynôme monique, donc je ne fais que la division d'essai par polynômes moniques et économise une réciproque dans le champ. Cependant, ce Zn'est qu'un anneau et il est donc nécessaire de faire la division d'essai par des facteurs candidats non moniques. Je réussis à ne pas implémenter de nombres rationnels en effectuant un test de division des facteurs de premier plan et en accumulant un indicateur "d'erreur" e.
  4. Les deux points 2 et 3 impliquent que le cas de l'affacturage Zest généralement plus lent et ne peut pas être testé avec la démo en ligne. Cependant, le plus lent des cas de test officiels prend 10 minutes, ce qui est bien dans le délai "raisonnable".
Peter Taylor
la source