Berlekamp-Rabin algoritme

Berlekamp-Rabin algoritmen (også Berlekamps metode ) er en sandsynlighedsmetode til at finde rødderne af polynomier over et felt med polynomisk kompleksitet. Metoden blev beskrevet af den amerikanske matematiker Alvin Berlekamp i 1970 [1] som et spin-off til faktoriseringsalgoritmen for polynomier over endelige felter og blev senere (i 1979) modificeret af Michael Rabin til tilfældet med vilkårlige endelige felter [2] . Den originale version af algoritmen foreslået af Berlekamp i 1967 [3] var ikke polynomium [4] . Den version af algoritmen, der blev offentliggjort i 1970 baseret på resultaterne af Zassenhaus arbejdede med store værdier af , hvor titelmetoden blev brugt som en hjælper [1] . På udgivelsestidspunktet var metoden almindelig i det faglige miljø, men sjældent fundet i litteraturen [4] . $\mathbb {F} _{p}$ $s$

Historie

Metoden blev foreslået af Alvin Berlekamp i hans arbejde med faktorisering af polynomier over endelige felter [1] . I den reduceres faktoriseringen af et polynomium til irreducerbare faktorer over et felt til at finde rødderne af nogle andre polynomier over et felt . Samtidig var der i det originale arbejde intet bevis for rigtigheden af algoritmen [2] . Algoritmen blev færdiggjort og generaliseret til tilfældet med vilkårlige endelige felter af Michael Rabin [2] . I 1986 beskrev René Peralta en lignende algoritme [5] der løser problemet med at finde kvadratroden i et felt [6] , og i 2000 blev Peraltas metode generaliseret til at løse kubiske ligninger [7] . ${\mathbb F}_{{p^{k}}}$ $\mathbb {F} _{p}$ $\mathbb {F} _{p}$

I Berlekamps algoritme er et polynomium først repræsenteret som et produkt , hvor er produktet af polynomier af grad . Derefter reduceres faktoriseringen af hvert sådant gradspolynomium til at finde rødderne af det nye gradspolynomium . Artiklen, der introducerer faktoriseringsalgoritmen, foreslog også tre metoder til at finde rødderne til et polynomium i et Galois-felt . De to første reducerer det at finde rødder i en mark til at finde rødder i en mark . Den tredje metode, som er emnet for denne artikel, løser problemet med at finde rødder i feltet , som sammen med de to andre løser faktoriseringsproblemet [1] . ${\displaystyle f(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n))$ $f(x)=h_{1}(x)h_{2}(x)\dots h_{n}(x)$ $Hej}$ $r_{i}$ $jeg$ $h_{i}(x)$ ${\displaystyle ir_{i))$ $H(x)$ $r_{i}$ ${\mathbb F}_{{p^{k}}}$ ${\mathbb F}_{{p^{k}}}$ $\mathbb {F} _{p}$ $\mathbb {F} _{p}$

Den version af faktoriseringsalgoritmen foreslået af Berlekamp i hans første papir i 1967 [3] løb i , hvor er antallet af irreducerbare faktorer i polynomiet. Algoritmen var således ikke-polynomiel og var upraktisk, når primtallet var stort nok. I 1969 blev dette problem løst af Hans Zassenhaus , som viste, hvordan man kan reducere flaskehalsen i algoritmen til problemet med at finde rødderne til et eller andet polynomium [4] . I 1970 blev Berlekamps artikel genudgivet under hensyntagen til løsningerne fra Zassenhaus [1] . $O(n^{3}+prn)$ $r$ $s$

I 1980 udførte Michael Rabin en grundig analyse af algoritmen, generaliserede den til at arbejde med endelige felter af formen og beviste, at fejlsandsynligheden for én iteration af algoritmen ikke overstiger [2] , og i 1981 Michael Ben- Eller styrket dette skøn til , hvor — antallet af forskellige rødder af polynomiet [8] . Spørgsmålet om eksistensen af en polynomiel deterministisk algoritme til at finde rødderne af et polynomium over et endeligt felt forbliver åbent - de vigtigste polynomielle faktoriseringsalgoritmer , Berlekamp-algoritmen og Cantor-Zassenhaus-algoritmen er sandsynlige. I 1981 viste Paul Camion [9] , at en sådan algoritme eksisterer for ethvert givet tal , men dette resultat er rent teoretisk, og spørgsmålet om muligheden for at konstruere de mængder, som er beskrevet af ham i praksis, forbliver åbent [10] . ${\mathbb F}_{{p^{k}}}$ $1/2$ ${\textstyle 1-1/2^{k-1}+O\left(1/{\sqrt {p}}\right)}$ $k$ $f(x)$ $s$

I den første udgave af andet bind af "The Art of Programming " om numeriske algoritmer, skriver Donald Knuth , at lignende faktoriseringsprocedurer var kendt i 1960, men sjældent blev fundet i det offentlige domæne [4] . Et af de første offentliggjorte eksempler på brugen af metoden kan findes i arbejdet af Golomb , Welsh og Hales fra 1959 om faktorisering af trinomialer over , hvor et særligt tilfælde blev overvejet [11] . $\mathbb {F} _{2}$ $p=2,z=1$

Algoritme

Udtalelse af problemet

Lad være et ulige primtal. Overvej et polynomium over feltet af rester modulo . Det er nødvendigt at finde alle tal således, at for alle mulige [2] [12] . $s$ ${\textstyle f(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n))$ $\mathbb {Z} _{p}$ $s$ ${\displaystyle \lambda _{1},\dots ,\lambda _{k))$ ${\textstyle f(\lambda _{i})\equiv 0{\pmod {p))}$ $jeg$

Randomisering

Lad . At finde alle rødderne af et sådant polynomium svarer til at opdele det i lineære faktorer. For at finde en sådan partition er det nok at lære at opdele polynomiet i to vilkårlige faktorer og derefter køre rekursivt ind i dem. For at gøre dette introducerer vi et polynomium , hvor er et tilfældigt tal fra . Hvis et sådant polynomium kan repræsenteres som et produkt , så betyder det i form af det oprindelige polynomium at , hvilket giver en faktorisering af det oprindelige polynomium [1] [12] . ${\tekststil f(x)=(x-\lambda _{1})(x-\lambda _{2})\dots (x-\lambda _{n})}$ ${\tekststil f_{z}(x)=f(xz)=(x-\lambda _{1}-z)(x-\lambda _{2}-z)\dots (x-\lambda _{n }-z)}$ $z$ $\mathbb {Z} _{p}$ $f_{z}(x)=p_{0}(x)p_{1}(x)$ $f(x)=p_{0}(x+z)p_{1}(x+z)$ $f(x)$

Klassificering af elementer $\mathbb {F} _{p}$

Ifølge Euler-kriteriet er nøjagtigt en af følgende egenskaber opfyldt for ethvert monomer [1] : $(x-\lambda )$

Monomialet er lig med hvis , $x$ $\lambda=0$
Monomialet deler hvis er en kvadratisk restmodulo , ${\tekststil g_{0}(x)=(x^{(p-1)/2}-1)}$ $\lambda$ $s$
Monomialet deler if er en kvadratisk ikke-rest modulo dette. ${\textstyle g_{1}(x)=(x^{(p-1)/2}+1)}$ $\lambda$

Således, hvis det ikke er deleligt med , som kan kontrolleres separat, så er det lig med produktet af de største fælles divisorer og [12] . $f_{z}(x)$ $x$ $f_{z}(x)$ $\gcd(f_{z}(x);g_{0}(x))$ $\gcd(f_{z}(x);g_{1}(x))$

Berlekamp metode

Ovenstående fører til følgende algoritme [1] :

Polynomiets koefficienter beregnes eksplicit , $f_{z}(x)=f(xz)$
Beregn resten af divisionen ved successiv kvadrering og tag resten af , ${\tekststil x,x^{2},x^{2^{2)),x^{2^{3)),x^{2^{4)),\dots ,x^{2^{ \lgulv \log _{2}p\rgulv }}}$ $f_{z}(x)$ $f_{z}(x)$
Binær eksponentiering beregner resten af divisionen ved at bruge polynomier beregnet i sidste trin, ${\tekststil x^{(p-1)/2}}$ ${\textstyle f_{z}(x)}$
Hvis , så giver ovenstående en ikke-triviel faktorisering, ${\textstyle x^{(p-1)/2}\not \equiv \pm 1{\pmod {f_{z}(x)))}$ $\gcd$ $f_{z}(x)$
Ellers er alle rødder rester eller ikke-rester på samme tid, og det er værd at prøve en anden værdi . $f_{z}(x)$ $z$

Hvis det også divideres med et eller andet polynomium , der ikke har rødder i , så vil der ved beregning med og fås en opdeling af det kvadratfrie polynomium i ikke-trivielle faktorer, så algoritmen giver dig mulighed for at finde alle rødderne af evt. polynomier over , og ikke kun dem, der er opdelt i et produkt af monomer [12] . $f(x)$ $g(x)$ $\mathbb {Z} _{p}$ $\gcd$ $g_{0}(x)$ $g_{1}(x)$ $f_{z}(x)/g_{z}(x)$ $\mathbb {Z} _{p}$

Udtræk af kvadratroden

Lad det være nødvendigt at løse en sammenligning , hvis løsninger er elementerne og hhv. At finde dem svarer til at faktorisere et polynomium over et felt . I dette særlige tilfælde er problemet forenklet, da det for løsningen er nok kun at beregne . For det resulterende polynomium vil præcis et af udsagn være sandt: ${\textstyle x^{2}\equiv a{\pmod {p}}}$ $\beta$ $-\beta$ ${\tekststil f(x)=x^{2}-a=(x-\beta )(x+\beta )}$ $\mathbb {Z} _{p}$ $\gcd(f_{z}(x);g_{0}(x))$

GCD er , hvilket indebærer, at og er kvadratiske ikke-rester på samme tid, $en$ $z+\beta$ $z-\beta$
GCD er , hvilket indebærer, at begge tal er kvadratiske rester, $f_{z}(x)$
GCD er lig med en monomial , hvilket indebærer, at præcis ét tal ud af to er en kvadratisk rest. $(xt)$

I det tredje tilfælde skal den resulterende monomial være lig med eller , eller . Dette gør det muligt at skrive løsningen som [1] . $(xz-\beta )$ $(x-z+\beta )$ ${\textstyle \beta =(tz){\pmod {p}}}$

Eksempel

Lad os løse sammenligningen . For at gøre dette skal du faktorisere . Lad os overveje de mulige værdier : ${\textstyle x^{2}\equiv 5{\pmod {11}}}$ $f(x)=x^{2}-5=(x-\beta )(x+\beta )$ $z$

Lad . Så hvorfra . Begge numre er ikke-rester, og du skal tage et andet . $z=3$ $f_{z}(x)=(x-3)^{2}-5=x^{2}-6x+4$ $\gcd(x^{2}-6x+4;x^{5}-1)=1$ $3\pm \beta$ $z$

Lad . Så hvorfra . Derfor , derfor . $z=2$ $f_{z}(x)=(x-2)^{2}-5=x^{2}-4x-1$ ${\textstyle \gcd(x^{2}-4x-1;x^{5}-1)\equiv x-9{\pmod {11))}$ ${\tekststil x-9=x-2-\beta }$ $\beta \equiv 7{\pmod {11}}$ ${\textstyle -\beta \equiv -7\equiv 4{\pmod {11}}}$

Verifikation viser det og er gyldigt . ${\textstyle 7^{2}\equiv 49\equiv 5{\pmod {11))}$ ${\textstyle 4^{2}\equiv 16\equiv 5{\pmod {11))}$

Begrundelse for metoden

Algoritmen finder en opdeling i ikke-trivielle faktorer i alle tilfælde, bortset fra dem, hvor alle tal er rester eller ikke-rester på samme tid. Ifølge teorien om cyklotomi [1] kan sandsynligheden for en sådan hændelse for det tilfælde, hvor de selv er både rester eller ikke-rester på samme tid (det vil sige, når det ikke er egnet til vores procedure) estimeres som [8] , hvor er antallet af forskellige tal blandt [1] . Således overstiger sandsynligheden for algoritmefejl ikke . $f_{z}(x)$ ${\displaystyle z+\lambda _{1},z+\lambda _{2},\dots ,z+\lambda _{n))$ ${\displaystyle \lambda _{1},\dots ,\lambda _{n))$ $z=0$ $1/2^{k-1}$ $k$ ${\displaystyle \lambda _{1},\dots ,\lambda _{n))$ $1/2$

Anvendelse til faktorisering af polynomier

Det er kendt fra teorien om endelige felter , at hvis graden af et irreducerbart polynomium er , så er et sådant polynomium en divisor og er ikke en divisor for . $q(x)$ $d$ $x^{p^{d}}-x$ $x^{p^{t}}-x$ $t<d$

Således sekventielt overvejer polynomier hvor og for , Vi kan opdele polynomiet i faktorer af formen , hvor er produktet af alle irreducible polynomier af grad , der deler polynomiet . Ved at kende graden af , kan vi bestemme antallet af sådanne polynomier lig med . Lad . Hvis vi betragter polynomiet , hvor , så skal rækkefølgen af et sådant polynomium i feltet dividere tallet . Hvis ikke deleligt med , Så er polynomiet deleligt med men ikke med . $h_{i}(x)=\gcd(f_{i}(x),x^{p^{i}}-1)$ $f_{1}(x)=f(x)$ $f_{i}(x)=f_{i-1}(x)/h_{i-1}(x)$ $i>1$ $f(x)$ $f(x)=h_{1}(x)\dots h_{n}(x)$ $h_{i}(x)$ $jeg$ $f(x)$ $h_{i}(x)$ $r_{i}=\deg h_{i}(x)/i$ $h_{i}(x)=p_{1}(x)\dots p_{r_{i}}(x)$ $p_{j}(xz)$ ${\textstyle z\in \mathbb {F} _{p}}$ $d_{j}$ ${\textstyle \mathbb {F} _{p^{i))}$ $p^{i}-1$ $d_{j}$ $d_{k}$ ${\tekststil x^{d_{j}}-x}$ ${\textstyle p_{j}(xz)}$ ${\textstyle p_{k}(xz)}$

Baseret på dette foreslog Zassenhaus at lede efter divisorer af et polynomium på formen , hvor er en tilstrækkelig stor divisor , for eksempel . I et bestemt tilfælde opnås præcis Berlekamp-metoden som beskrevet ovenfor [4] . $h_{i}(xz)$ ${\tekststil \gcd(h_{i}(xz),x^{f}-1)}$ $f$ $p^{i}-1$ ${\textstyle f={\frac {p^{i}-1}{2}}}$ $i=1$

Åbningstider

Trin for trin kan køretiden for en iteration af algoritmen estimeres som følger, idet det antages, at graden af polynomiet er : $n$

I betragtning af, at ifølge Newtons binomiale formel , sker overgangen fra til i , ${\textstyle (xz)^{k}=\sum \limits _{i=0}^{k}{\binom {k}{i}}(-z)^{ki}x^{i}}$ $f(x)$ $f(xz)$ $O(n^{2})$
Produktet af polynomier og at tage resten af et polynomium modulo en anden udføres i , så beregningen udføres i , ${\textstyle O(n^{2})}$ ${\textstyle x^{2^{k}}{\bmod {f}}_{z}(x)}$ ${\textstyle O(n^{2}\log p)}$
I lighed med det foregående punkt udføres binær eksponentiering i , $O(n^{2}\log p)$
At tage fra to polynomier ifølge Euklids algoritme udføres i . $\gcd$ $O(n^{2})$

Der kan således udføres én iteration af algoritmen for aritmetiske operationer med elementer , og at finde alle polynomiets rødder kræver et gennemsnit [8] . I det særlige tilfælde med at udtrække kvadratroden er værdien to, så køretiden estimeres som én iteration af algoritmen [12] . $O(n^{2}\log p)$ $\mathbb {F} _{p}$ $O(n^{2}\log n\log p)$ $n$ $O(\log p)$

Noter

↑ 1 2 3 4 5 6 7 8 9 10 11 Berlekamp ER Factoring polynomials over large finite fields // Mathematics of Computation. - 1970. - Bd. 24 , udg. 111 . - s. 730-732 . — ISSN 0025-5718 . - doi : 10.1090/S0025-5718-1970-0276200-X .
↑ 1 2 3 4 5 Rabin M. Probabilistic Algorithms in Finite Fields // SIAM Journal on Computing. - 1980. - 1. maj ( vol. 9 , udg. 2 ). - S. 273-280 . — ISSN 0097-5397 . - doi : 10.1137/0209024 . Arkiveret fra originalen den 23. juni 2019.
↑ 1 2 Berlekamp ER Factoring polynomials over finite fields // The Bell System Technical Journal. - 1967. - Oktober ( bind 46 , udg. 8 ). - S. 1853-1859 . — ISSN 0005-8580 . - doi : 10.1002/j.1538-7305.1967.tb03174.x . Arkiveret fra originalen den 17. februar 2019.
↑ 1 2 3 4 5 Knuth DE Kunsten at programmere computer . - Reading, Massachusetts: Addison-Wesley Publishing Company, 1968. - Vol. 2. - S. 381-390. — 624 s. - ISBN 0-201-03802-1 . Arkiveret 3. august 2019 på Wayback Machine
↑ Sze TW Om at tage kvadratrødder uden kvadratiske ikke-rester over endelige felter // Mathematics of Computation. - 2011. - 3. januar ( vol. 80 , udg. 275 ). - S. 1797-1811 . — ISSN 0025-5718 . - doi : 10.1090/s0025-5718-2011-02419-1 .
↑ Peralta R. En enkel og hurtig probabilistisk algoritme til beregning af kvadratrødder modulo et primtal (Corresp. ) // IEEE Transactions on Information Theory. - 1986. - November ( vol. 32 , udg. 6 ). - s. 846-847 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1986.1057236 . Arkiveret fra originalen den 30. juni 2019.
↑ Padró C., Sáez G. At tage terningrødder i Zm // Applied Mathematics Letters. - 2002. - August ( bind 15 , udg. 6 ). - S. 703-708 . — ISSN 0893-9659 . - doi : 10.1016/s0893-9659(02)00031-9 .
↑ 1 2 3 Ben-Or M. Probabilistiske algoritmer i endelige felter // 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981). - 1981. - Oktober. - S. 394-398 . - doi : 10.1109/SFCS.1981.37 . Arkiveret fra originalen den 29. juli 2019.
↑ Camion P. A Deterministic Algorithm for Factorizing Polynomials of Fq [X] // Combinatorial Mathematics, Proceedings of the International Colloquium on Graph Theory and Combinatorics. - Elsevier, 1983. - S. 149-157 . — ISBN 9780444865120 .
↑ Grenet B., van der Hoeven J., Lecerf G. Deterministisk rodfinding over endelige felter ved hjælp af Graeffe-transformationer // Applicable Algebra in Engineering, Communication and Computing. - 2015. - Bd. 27 , udg. 3 . — S. 239 . — ISSN 0938-1279 . - doi : 10.1007/s00200-015-0280-5 .
↑ Golomb SW, Hales A., Welch LR On the factorization of trinomials over GF(2 ) // Shift Register Sequences. - World Scientific, 2017. - Marts. - S. 90-108. - ISBN 978-981-4632-00-3 . - doi : 10.1142/9789814632010_0005 .
↑ 1 2 3 4 5 Menezes AJ, Blake IF, Gao XH, Mullin RC, Vanstone SA Applications of Finite Fields . - Springer USA, 1993. - S. 22-26. — 218 sider. - (Springer International Series in Engineering and Computer Science). — ISBN 9780792392828 . Arkiveret 30. juni 2019 på Wayback Machine

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme