Metoda Kronecker

Metoda Kronecker este o metodă de descompunere a unui polinom cucoeficienți întregi în factori ireductibili peste inelul de numere întregi; propusă în 1882 de Kronecker .

Algoritmul Kronecker găsește pentru un polinom dat un polinom astfel încât să fie divizibil cu , sau demonstrează că nu există un astfel de polinom. $F(x)$ $f(x)$ $F(x)$ $f(x)$

Descrierea metodei

Algoritmul Kronecker se bazează pe următoarele considerații:

Dacă gradul polinomului este , atunci gradul a cel puţin unui factor al polinomului nu depăşeşte ; $F$ $n$ $f$ $\left\lfloor {n \over 2}\right\rfloor$
Valorile ambelor și ale punctelor întregi sunt numere întregi și ) împărțiri pentru orice număr întreg ; $F$ $f$ $f(i$ $F(i)$ $i$
Pentru un fix , dacă nu este egal cu 0, atunci poate lua doar o mulțime finită de valori, constând din divizori ai numărului ; $i$ $F(i)$ $f(i)$ $F(i)$
Coeficienții unui polinom sunt recuperați în mod unic din valorile sale într-un punct. $f$

Astfel, pentru că există un număr finit de posibilități; prin împărțire directă, verificăm dacă am primit divizorul polinomului . $f$ $F$

Declarație strictă:

Să considerăm un polinom de grad . Să aducem peste . Atunci unul dintre cele două polinoame și are cel mult grad . Lăsați fără pierdere de generalitate . Atunci , prin urmare . Luați în considerare diferite numere întregi astfel încât . Deoarece numerele au un număr finit de divizori întregi, este posibil să se repete peste toate seturile posibile de valori pentru . Pentru fiecare astfel de mulțime, construim un polinom de interpolare de grad . Dacă acum , la polinoame și puteți aplica aceeași metodă și așa mai departe până când toți factorii devin ireductibili. În caz contrar, dacă , polinomul este deja ireductibil. $f(x)\in \mathbb {Z} [x]$ $n$ $f(x)$ $\mathbb {Z}$ $f(x)=g(x)h(x)$ $g(x)$ $h(x)$ $n/2$ $\operatorname {grade} \,g(x)\leqslant n/2$ $\forall a\in \mathbb {Z} \;g(a)\in \mathbb {Z}$ $f(a)\vdots g(a)$ $m=n/2+1$ $a_{i},i={\overline {1,m))$ $f(a_{i})\not =0$ $f(a_{i})$ $g(a_{i})$ $g^{*}(x)$ $m-1=n/2$ $f(x){\mathrel {\vdots }}g^{*}(x)$ $g^{*}(x)$ ${\frac {f(x)}{g^{*}(x)))$ $\forall g^{*}(x)\f(x){\mathrel {\cancel {\vdots ))}g^{*}(x)$ $f(x)$

Algoritm Kronecker unidimensional

Notarea algoritmului

Dat: $f(x)\in \mathbb {Z} [x]$

Necesar: $g(x)\in \mathbb {Z} [x]$

Unde: este gradul polinomului , este gradul polinomului , este un număr întreg. $n$ $f$ $m$ $g$ $i$

Цикл от $i=0$ до $[n/2]$

Если (

f(i)=0

) то

g=x-i

m=1

Ответ найден. Конец если

Конец цикла

Если (ответ не найден) то

U

— множество делителей

f(0)

(целочисленных) Цикл от

i=1

до

[n/2]

M

— множество делителей

f(i)

(целочисленных)

U:=

декартово произведение

U

M

Цикл для каждого

u\in U

Построить многочлен

g

степени

i

, такой, что

g(j)=u(j)

для

j=0...i

Если (

f

делится на

g

) то

m=i

Решение успешно найдено, ответ

g

Конец если Конец цикла Конец цикла

Конец если

Конец.

COMETARIU. Este suficient să înveți cum să factorizezi polinoame cu un coeficient de conducere egal cu unu. Într-adevăr, dacă coeficientul principal este , atunci înmulțind cu și făcând substituția , reducem problema la acest caz. După rezolvare, rămâne de făcut substituția inversă și de a reduce cu factorul comun a n−1 . Cu toate acestea, această metodă se dovedește de obicei a fi ineficientă: din cauza creșterii coeficienților, diverse estimări și viteza algoritmilor se deteriorează. Prin urmare, în majoritatea algoritmilor de lucru, astfel de transformări nu sunt efectuate. $A$ $a^{n-1}$ $x=y/a$

Implementarea Maple

kronecker := proc ( f :: polinom ) local g , i , n , U , V , j ; cu ( linalg ) ; n := grad ( f ) / 2 ; U := factorul meu ( subs ( x = 0 , f )) ; pentru i de la 1 la n do U := U , factorul meu ( subs ( x = i , f )) ; V := mcarp ( U ) ; pentru j în V do g := interp ([ $0 .. i ] , j , x ) ; dacă rem ( f , g , x ) = 0 și nu tastați ( g , 'constant' ) atunci tipăriți ( g ) ; termina daca ; sfârşitul face ; sfârşitul d o ; sfârșitul procesului ; myfactor := proc ( n :: integer ) local a , b , i , j ; b := [] ; pentru i de la 1 la abs ( n ) do if ( irem ( n , i ) = 0 ) atunci b := ArrayTools [ Concatenate ]( 2 , b , i ) ; b := ArrayTools [ Concatenate ]( 2 , b ,- i ) ; termina daca ; sfârşitul face ; convert ( b , 'listă' ) ; sfârșitul procesului ; # Următoarele 2 funcții calculează produsul cartezian al mulțimilor multiple . # Sunt preluate de pe http : //people.oregonstate.edu/~peterseb/mth355/docs/355f2001-cartesian-product.pdf crap : = proc ( X , Y ) local Z , x , y ; Z : = {} for x in X do for y in Y do Z := Z uniune {[x,y]} ; sfârşitul face ; sfârşitul face ; întoarcere Z ; sfârșitul procesului ; mcarp := proc () local Z , k , x , y ; opțiunea reține ; dacă nargs = 0 atunci Z := {} ; elif nargs = 1 atunci Z := args [ 1 ] ; else Z := {} ; for x in mcarp ( seq ( args [ k ] , k = 1 .. nargs - 1 ) ) do for y in args [ nargs ] do Z := Z union {[op(x),y]} ; sfârşitul face ; sfârşitul face ; termina daca ; întoarcere Z ; sfârșitul procesului ;

Exemplu

$f(x)=x^{5}-x^{4}-2x^{3}-8x^{2}+6x-1$ (acesta este un polinom cu coeficienți întregi și fără rădăcini raționale). Dacă unde gradul k al polinomului nu este mai mare decât gradul , atunci . Apoi . Divizori ai acestor numere: pentru primul +1 și -1, pentru al doilea +1, -1, +5, -5, pentru al treilea +1, -1, +3, -3, +7, -7, + 21, - 21. În total, se obțin combinații . Două combinații care diferă doar prin semn dau în esență un polinom. Prin urmare, doar jumătate poate fi verificată. Au mai rămas 32 de cazuri. Parcurgând toate aceste cazuri, puteți găsi un singur polinom de împărțire de gradul 2 . Aceasta este . Ambii factori ai acestei expansiuni sunt ireductibili (ca polinoame de gradul 2 și 3, care nu au rădăcini raționale). $f(x)=g(x)h(x)$ $g(x)$ $h(x)$ $k=2$ $f(0)=-1;f(1)=-5;f(2)=-21$ $2\cdot 4\cdot 8=64$ $f(x)$ $g(x)=x^{2}-3x+1$

Algoritm multivariat Kronecker

Înregistrarea condițiilor problemei

Fie un domeniu de integritate cu o factorizare unică, . Este necesar să se descompună în factori ireductibili. $D$ $f(x_{1},...,x_{n})\in D[x_{1},...,x_{n}]$ $f$

Notarea algoritmului

Având în vedere : $f\in \mathbb {Z} [x_{1},...,x_{n}]$

Este necesar : - descompunere $G$

Variabile : polinom , expansiune polinomială , set de elemente de tip . ${\bar {f}}\in \mathbb {Z} [y]$ ${\bar {G}}$ ${\bar {f)}$ $M$ $\mathbb {Z}$

Idee de implementare : Reduceți problema la un caz unidimensional prin introducerea unei noi necunoscute și înlocuirea tuturor variabilelor cu puteri suficient de mari ale acestei necunoscute. Factorizați polinomul rezultat. Efectuați înlocuirea înapoi, diviziunea de testare pentru a vă asigura că se obține expansiunea dorită.

Început
Alegeți un număr întreg mai mare decât puterile variabilelor individuale pentru a înlocui toate variabilele cu puterile noii necunoscute : $d$ $f$ $y$