Berlekamp-Rabin algoritm

Berlekamp-Rabin-algoritmen (även Berlekamps metod ) är en probabilistisk metod för att hitta rötter till polynom över ett fält med polynomkomplexitet . Metoden beskrevs av den amerikanske matematikern Alvin Berlekamp 1970 [1] som en spin-off till faktoriseringsalgoritmen för polynom över ändliga fält och modifierades senare (1979) av Michael Rabin för fallet med godtyckliga ändliga fält [2] . Den ursprungliga versionen av algoritmen som föreslogs av Berlekamp 1967 [3] var inte polynom [4] . Den version av algoritmen som publicerades 1970 baserad på resultaten från Zassenhaus arbetade med stora värden på , där titelmetoden användes som hjälpmedel [1] . Vid publiceringstillfället var metoden vanlig i den professionella miljön, men återfanns sällan i litteraturen [4] . $\mathbb {F} _{p}$ $sid$

Historik

Metoden föreslogs av Alvin Berlekamp i hans arbete med faktorisering av polynom över ändliga fält [1] . I den reduceras faktoriseringen av ett polynom till irreducible faktorer över ett fält till att hitta rötterna till några andra polynom över ett fält . Samtidigt fanns det i originalverket inga bevis för algoritmens riktighet [2] . Algoritmen slutfördes och generaliserades till fallet med godtyckliga finita fält av Michael Rabin [2] . 1986 beskrev René Peralta en liknande algoritm [5] som löser problemet med att hitta kvadratroten i ett fält [6] , och 2000 generaliserades Peraltas metod för att lösa kubikekvationer [7] . ${\mathbb F}_{{p^{k}}}$ $\mathbb {F} _{p}$ $\mathbb {F} _{p}$

I Berlekamps algoritm representeras ett polynom först som en produkt , där är produkten av polynom av grad . Sedan reduceras faktoriseringen av varje sådan gradpolynom till att hitta rötterna till det nya gradpolynomet . Artikeln som introducerar faktoriseringsalgoritmen föreslog också tre metoder för att hitta rötterna till ett polynom i ett Galois-fält . De två första reducerar att hitta rötter i ett fält till att hitta rötter i ett fält . Den tredje metoden, som är föremål för denna artikel, löser problemet med att hitta rötter i fältet , som tillsammans med de andra två 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}$ $i$ $Hej X)$ ${\displaystyle ir_{i))$ $H(x)$ $r_{i}$ ${\mathbb F}_{{p^{k}}}$ ${\mathbb F}_{{p^{k}}}$ $\mathbb {F} _{p}$ $\mathbb {F} _{p}$

Den version av faktoriseringsalgoritmen som föreslogs av Berlekamp i hans första papper 1967 [3] sprang i , där är antalet irreducible faktorer av polynomet. Algoritmen var alltså icke-polynom och var opraktisk när primtalet var tillräckligt stort. 1969 löstes detta problem av Hans Zassenhaus , som visade hur man kan reducera flaskhalsen i algoritmen till problemet att hitta rötterna till något polynom [4] . 1970 återpublicerades Berlekamps artikel, med hänsyn tagen till lösningarna från Zassenhaus [1] . $O(n^{3}+prn)$ $r$ $sid$

1980 genomförde Michael Rabin en rigorös analys av algoritmen, generaliserade den till att fungera med ändliga fält av formen och bevisade att felsannolikheten för en iteration av algoritmen inte överstiger [2] och 1981 Michael Ben- Eller stärkte denna uppskattning till , där — antalet olika rötter av polynomet [8] . Frågan om existensen av en polynom deterministisk algoritm för att hitta rötterna till ett polynom över ett ändligt fält förblir öppen - de huvudsakliga polynomfaktoriseringsalgoritmerna , Berlekamp-algoritmen och Cantor-Zassenhaus-algoritmen är sannolikhet. 1981 visade Paul Camion [9] att en sådan algoritm existerar för ett givet antal , men detta resultat är rent teoretiskt och frågan om möjligheten att konstruera de uppsättningar som beskrivits av honom i praktiken förblir öppen [10] . ${\mathbb F}_{{p^{k}}}$ $1/2$ ${\textstyle 1-1/2^{k-1}+O\left(1/{\sqrt {p}}\right)}$ $k$ $f(x)$ $sid$

I den första upplagan av den andra volymen av " Konsten att programmera " om numeriska algoritmer, skriver Donald Knuth att liknande faktoriseringsprocedurer var kända 1960, men att de sällan hittades i det offentliga området [4] . Ett av de första publicerade exemplen på användningen av metoden finns i arbetet av Golomb , Welsh och Hales från 1959 om faktorisering av trinomial över , där ett specialfall övervägdes [11] . $\mathbb {F} _{2}$ $p=2,z=1$

Algoritm

Förklaring av problemet

Låta vara ett udda primtal. Betrakta ett polynom över fältet av rester modulo . Det är nödvändigt att hitta alla siffror så att för alla möjliga [2] [12] . $sid$ ${\textstil f(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n))$ $\mathbb {Z} _{p}$ $sid$ ${\displaystyle \lambda _{1},\dots ,\lambda _{k))$ ${\textstyle f(\lambda _{i})\equiv 0{\pmod {p))}$ $i$

Randomisering

Låt . Att hitta alla rötter till ett sådant polynom motsvarar att dela upp det i linjära faktorer. För att hitta en sådan partition räcker det att lära sig att dela upp polynomet i två valfria faktorer och sedan köra rekursivt in i dem. För att göra detta introducerar vi ett polynom , där är ett slumptal från . Om ett sådant polynom kan representeras som en produkt , då i termer av det ursprungliga polynomet betyder detta att , vilket ger en faktorisering av det ursprungliga polynomet [1] [12] . ${\textstil f(x)=(x-\lambda _{1})(x-\lambda _{2})\dots (x-\lambda _{n})}$ ${\textstil 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 av element $\mathbb {F} _{p}$

Enligt Eulerkriteriet är exakt en av följande egenskaper uppfylld för varje monomial [1] : $(x-\lambda )$

Monomialet är lika med om , $x$ $\lambda=0$
Monomial delar sig om är en kvadratisk restmodulo , ${\textstil g_{0}(x)=(x^{(p-1)/2}-1)}$ $\lambda$ $sid$
Monomial delar om är en kvadratisk icke-rest modulo detta. ${\textstyle g_{1}(x)=(x^{(p-1)/2}+1)}$ $\lambda$

Således, om det inte är delbart med , vilket kan kontrolleras separat, då är det lika med produkten av de största gemensamma divisorerna och [12] . $f_{z}(x)$ $x$ $f_{z}(x)$ $\gcd(f_{z}(x);g_{0}(x))$ $\gcd(f_{z}(x);g_{1}(x))$

Berlekamp-metoden

Ovanstående leder till följande algoritm [1] :

Polynomets koefficienter är explicit beräknade , $f_{z}(x)=f(xz)$
Beräkna resten av divisionen genom att kvadrera successivt och ta resten av , ${\textstil x,x^{2},x^{2^{2)),x^{2^{3)),x^{2^{4)),\dots ,x^{2^{ \lfloor \log _{2}p\rfloor }}}$ $f_{z}(x)$ $f_{z}(x)$
Binär exponentiering beräknar resten av divisionen genom att använda polynomen som beräknades i det sista steget, ${\textstyle x^{(p-1)/2}}$ ${\textstyle f_{z}(x)}$
Om , ger ovanstående en icke-trivial faktorisering, ${\textstil x^{(p-1)/2}\not \equiv \pm 1{\pmod {f_{z}(x)))}$ $\gcd$ $f_{z}(x)$
Annars är alla rötter rester eller icke-rester samtidigt och det är värt att prova ett annat värde . $f_{z}(x)$ $z$

Om det också delas med något polynom som inte har rötter i , då när man beräknar med och , erhålls en partition av det kvadratfria polynomet i icke-triviala faktorer, så algoritmen låter dig hitta alla rötter till alla polynom över , och inte bara de som är uppdelade i en produkt av monomial [12] . $f(x)$ $g(x)$ $\mathbb {Z} _{p}$ $\gcd$ $g_{0}(x)$ $g_{1}(x)$ $f_{z}(x)/g_{z}(x)$ $\mathbb {Z} _{p}$

Extrahera kvadratroten

Låt det vara nödvändigt att lösa en jämförelse vars lösningar är elementen och resp. Att hitta dem motsvarar att faktorisera ett polynom över ett fält . I det här speciella fallet är problemet förenklat, eftersom det för lösningen räcker att bara beräkna . För det resulterande polynomet kommer exakt ett av påståendena att vara sant: ${\textstyle x^{2}\equiv a{\pmod {p}}}$ $\beta$ $-\beta$ ${\textstil f(x)=x^{2}-a=(x-\beta )(x+\beta )}$ $\mathbb {Z} _{p}$ $\gcd(f_{z}(x);g_{0}(x))$

GCD är , vilket innebär att och är kvadratiska icke-rester samtidigt, $ett$ $z+\beta$ $z-\beta$
GCD är , vilket innebär att båda talen är kvadratiska rester, $f_{z}(x)$
GCD är lika med en monomial , vilket innebär att exakt ett nummer av två är en kvadratisk rest. $(xt)$

I det tredje fallet måste den resulterande monomialen vara lika med eller , eller . Detta gör att lösningen kan skrivas som [1] . $(xz-\beta )$ $(x-z+\beta )$ ${\textstyle \beta =(tz){\pmod {p}}}$

Exempel

Låt oss lösa jämförelsen . För att göra detta måste du faktorisera . Låt oss överväga de möjliga värdena : ${\textstyle x^{2}\equiv 5{\pmod {11}}}$ $f(x)=x^{2}-5=(x-\beta )(x+\beta )$ $z$

Låt . Sedan varifrån . Båda numren är icke-rester och du måste ta en annan . $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$

Låt . Sedan varifrån . Därav , därav . $z=2$ $f_{z}(x)=(x-2)^{2}-5=x^{2}-4x-1$ ${\textstil \gcd(x^{2}-4x-1;x^{5}-1)\equiv x-9{\pmod {11))}$ ${\textstil x-9=x-2-\beta }$ $\beta \equiv 7{\pmod {11}}$ ${\textstyle -\beta \equiv -7\equiv 4{\pmod {11}}}$

Verifiering visar att och är giltig . ${\textstyle 7^{2}\equiv 49\equiv 5{\pmod {11))}$ ${\textstyle 4^{2}\equiv 16\equiv 5{\pmod {11))}$

Motivering av metoden

Algoritmen hittar en uppdelning i icke-triviala faktorer i alla fall, förutom de där alla siffror är rester eller icke-rester samtidigt. Enligt teorin om cyklotomi [1] kan sannolikheten för en sådan händelse för fallet när de själva är både rester eller icke-rester samtidigt (det vill säga när det inte är lämpligt för vår procedur) uppskattas som [8] , där är antalet olika nummer bland [1] . Således överstiger sannolikheten för algoritmfel inte . $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$

Tillämpning på faktorisering av polynom

Det är känt från teorin om finita fält att om graden av ett irreducible polynom är , då ett sådant polynom är en divisor och är inte en divisor för . $q(x)$ $d$ $x^{p^{d}}-x$ $x^{p^{t}}-x$ $t<d$

Således, sekventiellt med tanke på polynomen där och för , kan vi dela upp polynomet i faktorer av formen , där är produkten av alla irreducerbara polynom av grad som delar polynomet . Genom att veta graden av , kan vi bestämma antalet sådana polynom lika med . Låt . Om vi betraktar polynomet , där , måste ordningen för ett sådant polynom i fältet dela talet . Om det inte är delbart med , då är polynomet delbart med men inte 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)$ $Hej X)$ $i$ $f(x)$ $Hej 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}$ ${\textstil x^{d_{j}}-x}$ ${\textstyle p_{j}(xz)}$ ${\textstyle p_{k}(xz)}$

Baserat på detta föreslog Zassenhaus att leta efter divisorer av ett polynom i formen , där är någon tillräckligt stor divisor , till exempel . I ett särskilt fall erhålls exakt Berlekamp-metoden enligt beskrivningen ovan [4] . $h_{i}(xz)$ ${\textstil \gcd(h_{i}(xz),x^{f}-1)}$ $f$ $p^{i}-1$ ${\textstyle f={\frac {p^{i}-1}{2}}}$ $i=1$

Öppettider

Steg för steg kan körtiden för en iteration av algoritmen uppskattas enligt följande, under antagande av att graden av polynomet är : $n$

Med tanke på att enligt Newtons binomialformel görs övergången från till i , ${\textstyle (xz)^{k}=\sum \limits _{i=0}^{k}{\binom {k}{i}}(-z)^{ki}x^{i}}$ $f(x)$ $f(xz)$ $O(n^{2})$
Produkten av polynom och att ta resten av ett polynom modulo en annan görs i , så beräkningen görs i , ${\textstyle O(n^{2})}$ ${\textstyle x^{2^{k}}{\bmod {f}}_{z}(x)}$ ${\textstyle O(n^{2}\log p)}$
I likhet med föregående punkt görs binär exponentiering i , $O(n^{2}\log p)$
Att ta från två polynom enligt Euklids algoritm görs i . $\gcd$ $O(n^{2})$

Således kan en iteration av algoritmen utföras för aritmetiska operationer med element , och att hitta alla rötter till polynomet kräver ett medelvärde [8] . I det speciella fallet att extrahera kvadratroten är värdet två, så körtiden uppskattas som en iteration av algoritmen [12] . $O(n^{2}\log p)$ $\mathbb {F} _{p}$ $O(n^{2}\log n\log p)$ $n$ $O(\log p)$

Anteckningar

↑ 1 2 3 4 5 6 7 8 9 10 11 Berlekamp ER Factoring polynom över stora finita fält // Mathematics of Computation. - 1970. - Vol. 24 , iss. 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 , utgåva 2 ). - S. 273-280 . — ISSN 0097-5397 . - doi : 10.1137/0209024 . Arkiverad från originalet den 23 juni 2019.
↑ 1 2 Berlekamp ER Factoring polynomials over finita fields // The Bell System Technical Journal. - 1967. - Oktober ( vol. 46 , utg. 8 ). - P. 1853-1859 . — ISSN 0005-8580 . - doi : 10.1002/j.1538-7305.1967.tb03174.x . Arkiverad från originalet den 17 februari 2019.
↑ 1 2 3 4 5 Knuth DE Konsten att programmera datorer . - Reading, Massachusetts: Addison-Wesley Publishing Company, 1968. - Vol. 2. - s. 381-390. — 624 sid. - ISBN 0-201-03802-1 . Arkiverad 3 augusti 2019 på Wayback Machine
↑ Sze TW Om att ta kvadratrötter utan kvadratiska icke-rester över finita fält // Mathematics of Computation. - 2011. - 3 januari ( vol. 80 , utg. 275 ). - P. 1797-1811 . — ISSN 0025-5718 . - doi : 10.1090/s0025-5718-2011-02419-1 .
↑ Peralta R. En enkel och snabb probabilistisk algoritm för att beräkna kvadratrötter modulo ett primtal (Corresp. ) // IEEE Transactions on Information Theory. - 1986. - November ( vol. 32 , utgåva 6 ). - s. 846-847 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1986.1057236 . Arkiverad från originalet den 30 juni 2019.
↑ Padró C., Sáez G. Ta kubrötter i Zm // Applied Mathematics Letters. - 2002. - Augusti ( vol. 15 , utg. 6 ). - s. 703-708 . — ISSN 0893-9659 . - doi : 10.1016/s0893-9659(02)00031-9 .
↑ 1 2 3 Ben-Or M. Probabilistiska algoritmer i finita fält // 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981). - 1981. - Oktober. - s. 394-398 . - doi : 10.1109/SFCS.1981.37 . Arkiverad från originalet 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 rotupptäckning över finita fält med hjälp av Graeffe-transformer // Tillämplig algebra inom teknik, kommunikation och beräkningar. - 2015. - Vol. 27 , iss. 3 . — S. 239 . — ISSN 0938-1279 . - doi : 10.1007/s00200-015-0280-5 .
↑ Golomb SW, Hales A., Welch LR Om faktoriseringen av trinomial över GF(2 ) // Shift Register Sequences. - World Scientific, 2017. - Mars. - 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 sid. - (Springer International Series in Engineering and Computer Science). — ISBN 9780792392828 . Arkiverad 30 juni 2019 på Wayback Machine

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm