Fattorizzazione rapida del polinomio con coefficienti di interi

Question

Voglio decomporre rapidamente il polinomio su un anello di interi (il polinomio originale ha coefficienti interi e tutti i fattori hanno coefficienti interi).

Ad esempio, desidero decomporre 4*x^6 + 20*x^5 + 29*x^4 - 14*x^3 - 71*x^2 - 48*x come (2*x^4 + 7*x^3 + 4*x^2 - 13*x - 16)*(2*x + 3)*x.

Quale algoritmo devo scegliere per evitare la complessità del codice e l'inefficienza di approccio (parlando della quantità totale di operazioni aritmetiche e consumo di memoria)?

Ho intenzione di utilizzare il linguaggio di programmazione C.

Ad esempio, forse ci sono alcuni buoni algoritmi per la fattorizzazione polinomiale su ring of integers modulo prime number?

Answer 1

In base a questo answer su mathoverflow, Sage utilizza il fattore di fattorizzazione FLINT.

FLINT (Libreria rapida per la teoria dei numeri) è una libreria C a supporto dei calcoli nella teoria dei numeri. È anche un progetto di ricerca sugli algoritmi nella teoria dei numeri.

Quindi è possibile osservare e persino utilizzare la realizzazione di algoritmi di decomposizione in quella libreria che è ben collaudata e stabile.

Answer 2

Poiché Sage è gratuito e open source, dovresti essere in grado di trovare l'algoritmo utilizzato da Sage e quindi chiamarlo o, nel peggiore dei casi, ri-implementarlo in C. Tuttavia, se davvero devi scrivere una procedura da zero, questa è quello che vorrei fare: innanzitutto trovare il gcd di tutti i coefficienti e dividerlo, il che rende il vostro polinomio "contenuto libero". Quindi prendi la derivata e trova il gcd polinomiale del polinomio originale e la sua derivata. Prendete questo fattore fuori dal polinomio originale per divisione polinomiale, che suddivide il vostro problema in due parti: fattorizzazione di un polinomio quadrato libero da contenuto (p/gcd (p, p ')) e factoring di un altro polinomio (gcd (p, p ')) che potrebbe non essere libero da quadrati. Per quest'ultimo, ricomincia dall'inizio, finché non hai ridotto il problema al factoring di uno o più polinomi privi di contenuto e quadrati.

Il prossimo passo sarebbe implementare un algoritmo di factoring mod p. L'algoritmo di Berlekamp è probabilmente il più semplice, anche se Cantor-Zassenhaus è allo stato dell'arte.

Infine, applicare l'algoritmo di Zassenhaus al fattore sui numeri interi. Se la trovi troppo lenta, può essere migliorata usando l'algoritmo di riduzione della base del reticolo "Lenstra-Lenstra-Lovasz". http://en.wikipedia.org/wiki/Factorization_of_polynomials#Factoring_univariate_polynomials_over_the_integers

Come potete vedere, questo è tutto piuttosto complicato e dipende da una grande quantità di teoria dell'algebra astratta. È molto meglio usare la stessa libreria utilizzata da Sage, o implementare nuovamente l'implementazione di Sage, o anche solo chiamare una versione in esecuzione del kernel Sage dal tuo programma.