Berlekamp-algoritme

Den Berlekamp algoritmen er en metode for faktorisering polynomer med koeffisienter i et avgrenset felt , som er basert på GCD beregning av polynomene og matriseoperasjoner . Den ble oppdaget av Elwyn Berlekamp i 1967 , og forble den algoritmen som hadde best resultater angående dette problemet til 1981 , og oppdagelsen av Cantor-Zassenhaus-algoritmen .

Beskrivelse

Algoritmen krever arbeid på et enhetlig polynom f ( x ) uten en kvadratfaktor , dvs. eksponentene til faktorene i den irredusible nedbrytningen av f er alle like 1. Vi betegner graden av n og q antall elementer av det endelige felt F q som man plasserer seg på.

Fokuset er å finne og bruke polynomer g slik at g q - g er delelig med f . I kvotientringen F q [ x ] / ( f ( x )) danner bildene av disse polynomene en under- F q- algebra , kalt "Berlekamp algebra". Ethvert element i kvotienten F q [ x ] / ( f ( x )) er identifisert med et polynom g av grad strengere enn n og g er i Berlekamp-algebra hvis og bare hvis

{\ displaystyle \ prod _ {s \ in \ mathbb {F} _ {q}} {\ rm {pgcd}} (f (x), g (x) -s) = f (x).}

Demonstrasjon

Vi legger først merke til at polynomene g ( x ) - s er to-to- prime mellom seg, derfor ved å betegne P ( x ) deres produkt:

${\ displaystyle \ prod _ {s \ in \ mathbb {F} _ {q}} {\ rm {pgcd}} (f (x), g (x) -s) = {\ rm {pgcd}} (f (x), P (x)).}$

Nå er P ( x ) lik M ( g ( x )) med

${\ displaystyle M (y): = \ prod _ {s \ in \ mathbb {F} _ {q}} (ys) = y ^ {q} -y,}$

den siste likheten skyldes at disse to polynomene er enhetlige, av grad q og null på F q .

Polynomet P er derfor lik g q - g . Derfor er pgcd ( f , P ) = f hvis og bare hvis f deler g q - g , dvs. hvis g er i Berlekamp-algebra.

Hvis dessuten g ikke er " triviell " (det vil si ikke konstant), er ingen av faktorene pgcd ( f , g - s ) lik f, derfor er minst en faktor forskjellig fra f og fra 1 Vi har dermed spaltet polynomial f til et produkt av enhetspolynomer, hvorav den ene er forskjellig fra f og fra 1: vi har tatt hensyn til f . For å oppnå en produktfaktorisering av irredusible polynomer er det tilstrekkelig å anvende denne metoden rekursivt .

For å finne ikke-trivielle polynomier g i Berlekamps algebra, starter vi fra observasjonen at kraften q -th av et polynom g ( x ) = g 0 + g 1 x +… + g n –1 x n –1 , med koeffisienter i F q , skrives g ( x ) q = g 0 + g 1 x q +… + g n –1 x q ( n –1) ( jf. Frobenius endomorfisme ). Ved å merke seg således reduksjonsmodulen f for monomialene x iq :

{\ displaystyle x ^ {iq} \ equiv \ sum _ {j = 0} ^ {n-1} \ alpha _ {i, j} x ^ {j} \ mod \; f (x),}

vi får da:

{\ displaystyle g (x) ^ {q} \ equiv \ sum _ {j = 0} ^ {n-1} (\ sum _ {i} g_ {i} \ alpha _ {i, j}) x ^ { j} \ mod \; f (x).}

Monomialene x j , for j = 0,…, n - 1, danner en F q - basis for vektorområdet F q [ x ] / ( f ( x )); vi oppnår dermed, ved identifisering av koeffisientene, at g er et element i Berlekamp-algebra hvis og bare hvis følgende matriseidentitet er verifisert:

{\ displaystyle {\ begin {pmatrix} g_ {0} & \ ldots & g_ {n-1} \ end {pmatrix}} {\ begin {pmatrix} \ alpha _ {0,0} & \ dots & \ alpha _ {0, n-1} \\\ vdots && \ vdots \\\ alpha _ {n-1.0} & \ dots & \ alpha _ {n-1, n-1} \ end {pmatrix}} = {\ begin {pmatrix} g_ {0} & \ ldots & g_ {n-1} \ end {pmatrix}}.}

Algoritmen består derfor i å beregne matrisen A til $α i , j og$ deretter å prøve, med den Gaussiske pivotmetoden , å finne en radvektor ( g 0 … g n –1 ) slik at ( g 0 … g n - 1 ) ( A - I n ) = 0, hvor I n betegner identitetsmatrisen (eller hvis man foretrekker: en kolonnevektor av kjernen i applikasjonen representert av den transponerte matrisen , A t - I n ); hvis vi finner et ikke-trivielt, kan vi faktor f ved gcd-beregninger via den euklidiske algoritmen . Til slutt viser vi at hvis det ikke er noe ikke-trivielt element i Berlekamps algebra, så er polynomet f ikke reduserbart. Mer presist: dimensjonen til denne algebraen er lik antall irredusible faktorer av f .

Demonstrasjon

La f 1 ,…, f k være de forskjellige irredusible enhetspolynomene som f er produktet av. Etter den kinesiske restsatsen har vi en isomorfisme av F q- algebraer:

{\ displaystyle \ mathbb {F} _ {q} [x] / (f) \ simeq \ mathbb {F} _ {q} [x] / (f_ {1}) \ oplus \ ldots \ oplus \ mathbb {F } _ {q} [x] / (f_ {k}).}

Ethvert polynom g som har sine k konstante komponenter i denne nedbrytningen er selvfølgelig i Berlekamp-algebra, men også omvendt, hvis g er i algebra, identiteten

{\ displaystyle g ^ {q} -g = \ prod _ {s \ in \ mathbb {F} _ {q}} (gs)}

(allerede begrunnet og brukt i forrige bevis) viser at hver f i deler en av g-ene . Kardinalen til denne algebraen er derfor q k, så dens dimensjon på F q er k .

Et eksempel

Vi bruker algoritmen på polynomet , som vi vil faktorisere i . ${\ displaystyle Q = 2X ^ {3} + 2X + 1}$ ${\ displaystyle \ mathbb {F} _ {3}}$

Første trinn: Enhetsform uten kvadratfaktor

Vi stiller . Så, som faktisk er enhetlig. For å redusere til et polynom uten en kvadratfaktor, deler vi med . Her er allerede uten en kvadratfaktor. Når vi er spaltet , går vi tilbake til nedbrytningen av følgende: hvis , vi har , noe som gir en faktorisering av . ${\ displaystyle P (X) = 2 ^ {2} Q ({\ dfrac {X} {2}})}$ ${\ displaystyle P = X ^ {3} + X + 1 ~ mod ~ 3}$ ${\ displaystyle pgcd (P, P ')}$ $P$ $P$ $Spørsmål$ ${\ displaystyle P = FG}$ ${\ displaystyle Q (X) = {\ dfrac {P (2X)} {2 ^ {4}}} = {\ dfrac {F (2X) G (2X)} {2 ^ {2}}}}$ $Spørsmål$

Andre trinn: Beregning av matrisen

For å beregne matrisen på kartet , beregner vi bildet av basisvektorene til Berlekamps algebra, det vil si . Vi må derfor beregne og modulere . Vi har : ${\ displaystyle M ~: ~ a \ mapsto a ^ {3} -a}$ ${\ displaystyle 1, X, X ^ {2}}$ ${\ displaystyle X ^ {3}}$ ${\ displaystyle X ^ {6}}$ $P$

${\ displaystyle X ^ {3} = - X-1}$

${\ displaystyle X ^ {4} = - X ^ {2} -X}$

${\ displaystyle X ^ {5} = - X ^ {2} + X + 1}$

${\ displaystyle X ^ {6} = X ^ {2} -X + 1}$

Matrisen til i det kanoniske grunnlaget er derfor: $M$ ${\ displaystyle \ left ({\ begin {array} {ccc} 0 & -1 & 1 \\ 0 & 1 & -1 \\ 0 & 0 & 0 \\\ end {array}} \ right)}$

Tredje trinn: Beregning av kjernen

Polynomet , ikke konstant, er i kjernen til denne matrisen. ${\ displaystyle g = X ^ {2} + X}$

Fjerde trinn: Faktorisering

${\ displaystyle P = pgcd ((X ^ {2} + X), P) * pgcd ((X ^ {2} + X-1), P) * pgcd ((X ^ {2} + X + 1) , P) = (X-1) (X ^ {2} + X-1)}$

Denne nedbrytningen består imidlertid av irreduserbare faktorer (man kan være sikker på dette ved å bruke algoritmen på hver faktor). Så . ${\ displaystyle Q = (2X ^ {2} + X + 1) (X + 1)}$

Kompleksiteten i algoritmen

Søket etter en ikke-konstant faktor av et polynom P av grad n in er i . ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle O (sb ^ {3})}$

Demonstrasjon

Husk først at for to polynomer P og Q er kompleksiteten til den euklidiske delingen av P av Q i størrelsesorden, og den for gcd er i . ${\ displaystyle O (deg (q) (deg (p) -deg (q) +1))}$ ${\ displaystyle O (deg (p) deg (q))}$

Det første trinnet i algoritmen er derfor inne . ${\ displaystyle O (n ^ {2})}$

Deretter består beregningen av matrisen i å lage euklidiske inndelinger av polynomer, hvor graden økes med , av P. Dette trinnet er da i Oppløsningen til størrelsessystemet gjøres av Gaussisk pivot og har derfor en kompleksitet i . $ikke$ ${\ displaystyle nq}$ ${\ displaystyle O (n (n (nq-n + 1))) = O (qn ^ {3})}$ ${\ displaystyle n ^ {2}}$ ${\ displaystyle O (n ^ {3})}$

Endelig gjenstår det bare å beregne den verste graden av graden på det meste , som gjøres i . Til slutt har vi ønsket resultat. $ikke$ $ikke$ ${\ displaystyle O (n ^ {3})}$

applikasjoner

En viktig anvendelse av Berlekamps algoritme ligger i datamaskinberegning av diskrete logaritmer på endelige felt hvor det er et primtall og et naturlig tall større enn eller lik 2. Beregningen av diskrete logaritmer er et viktig problem for asymmetrisk kryptografi og korrigerende koder . For et endelig felt er den raskeste metoden indeksberegningsalgoritmen (in) , som inkluderer faktorisering av kroppselementer. Hvis vi representerer feltet på en vanlig måte - det vil si som polynomer i feltet , redusert modulo til et irredusibelt gradspolynom - så er det en enkel polynomfaktorisering, slik som oppnås med Berlekamp-algoritmen. ${\ displaystyle \ mathbb {F} _ {p} ^ {n}}$ $s$ $ikke$ ${\ displaystyle \ mathbb {F} _ {p} ^ {n}}$ ${\ displaystyle \ mathbb {F} _ {p}}$ $ikke$

På den annen side utgjør Berlekamps algoritme det første trinnet i faktorisering av polynomer med heltallskoeffisienter, som også bruker Hensels lemma og LLL-algoritmen .

Referanser

(fr) Denne artikkelen er delvis eller helt hentet fra Wikipedia-artikkelen på engelsk med tittelen “ Berlekamps algoritme ” ( se forfatterlisten ) .
(en) ER Berlekamp , “ Factoring Polynomials Over Endite Fields ” , Bell Syst. Teknisk. J. , vol. 46, n o 8,1967, s. 1853-1859 ( DOI 10.1002 / j.1538-7305.1967.tb03174.x , les online )
Michel Demazure , Course of algebra: primality, divisibility, codes [ detalj of editions ]
(en) Rudolf Lidl og Harald Niederreiter , Introduksjon til endelige felt og deres applikasjoner , CUP ,1994, 416 s. ( ISBN 978-0-521-46094-1 , online presentasjon ) , s. 133-141
Abuaf Roland og Boyer Ivan , " Faktorisering i ${\ displaystyle \ mathbb {Z} [X]}$ ", masterfag foreslått av François Loeser ,2007( les online )