Բեռլեկեմպի ալգորիթմ

Բեռլեկեմպի ալգորիթմ, ալգորիթմ՝ նախատեսված վերջավոր սեռով ունիտար բազմանդամների ֆակտորիզացիայի համար։ Մշակվել է Էլվին Բեռլեկեմպի կողմից 1967 թվականին։ Կարող է օգտագործվել նաև վերջավոր դաշտերի վրա չվերլուծվող բազմանդամների համար։ Ալգորիթմի հիմնական գաղափարը տրված բազմանդամի ներկայացումն է՝ նույն բազմանդամի և որոշ այլ բազմանդամների ընդհանուր բաժանարարի տեսքով, որոնք մինչև ազատ անդամի ճշտությամբ հանդիսանում են $f$-բաժանարարներ։ Բեռլեկեմպի ալգորիթմը ունի դուրսբերման մեծ դժվարություն, այդ պատճառով մշակվել են մի շարք լրացուցիչ մեթոդներ, որոնք թույլատրում են կրճատել անհրաժեշտ մաթեմատիկակն գործողությունների քանակը։ Այնուամենայնիվ, չնայած իր դժվարության, Բեռլեկեմպի ալգորիթմը իրականացվել է համակարգչային հանրահաշվի համակարգում։ Ալգորիթմը մեծ կիրառում է գտել կոդավորման տեսությունում և վերջավոր դաշտերում գծային ռեկուրենտ հարաբերությունների ուսումնասիրություններում։ Հանրահաշվում և թվերի տեսությունում կան բազմաթիվ հաշվողական առաջադրանքներ, որոնք այսպես թե այնպես կապված են վերջավոր դաշտերում բազմանդամների տրոհման հետ, օրինակ, բազմանդամների բազմության տրոհումը ամբողջ թվերի օղակի վրա, հանրահաշվական թվերի դաշտում պարզ ռացիոնալ թվի տրոհման որոնումը, ինչ֊որ հավասարության Գալուայի խմբի որոշումը ռացիոնալ թվերի դաշտի և ընդլայված դաշտերի վրա։

Բեռլեկեմպի ալգորիթմ
Տեսակ	ալգորիթմ
Հայտնաբերող	Էլվին Բեռլեկեմպ
Անվանված է	Էլվին Բեռլեկեմպ

Ստեղծման պատմություն

Ամերիկացի մաթեմատիկոս, Կալիֆոռնիայի համալսարանի պրոֆեսոր Բեռլեկեմպը զբաղվել է սխալների հայտնաբերման և ճշգրտման ցիկլիկ կոդի, այդ թվում նաև Չոուդխուր֊Խոկվինգեմի կոդի ուսումնասիրությամբ, որոնց հատկությունները կախված են վերածնող բազմանդամի բաժանարարներից։ Այդ կոդերի ապակոդավորման շրջանում Բեռլեկեմպի տեխնիկական հաջողությունները պրակտիկայի տեսանկյունից իրենց դարձրեցին առավել կարևոր։ Ալգորիթմը առաջին անգամ շարադրվել է «Factoring Polynomials Over Finite Fields» հոդվածում և ավելի ուշ հրատարակվել է «Algebraic Coding Theory» գրքում։ 1967 թվականի այդ աշխատության մեջ Բեռլեկեմպը գրում է, որ ֆակտորիզացիայի խնդիրը առաջանում է Գոլոմբի աշխատություններում։ Այնուամենայնիվ, $f(x)$ բազմանդամի նորմավորված բազմապատկիչների թվի որոշման $B$ մատրիցի օգտագործումը առաջին անգամ նշվել. Բաթլերի հոդվածում որոշվել է, որ $B-E$ մատրիցայի ռանգը հավասար է $n-k$, այդ փաստի մեկ այլ ապացույց տրվել է Շվարցի կողմից։ Բեռլեկեմպի ալգորիթմը հիշատակվել է մի շարք աշխատություններում և մինչև 1981 թվականին.հայտնվելը հանդիսանում է ֆակտորիզացիայի խնդրի լուծման հիմնական ալգորիթմ։ Մշակվել էր տեխնիկա, որը հնարավորություն էր տալիս բազմանդամը տրոհել$O(n^{(\omega +1)/2+o(1)}+n^{1+o(1)}\log q),$ բազմապատկիչների, որտեղ $\omega$ ֊ն՝ քառակուսի մատրիցի վերաբազմապատկման բարդության գործակիցն է։

Տրում և որոշում

Ուսումնասիրվում է վերջավոր դաշտի վրա տրված $f(x)$ կարգի բազմանդամի ֆակտորիզացիայի խնդիրը $n$ ($n\geq 2$) $\mathbb {F} _{q}$ ($q=p^{m}$, $p$ պարզ թիվ է) տարբեր ունիտար բազմանդամների $f(x)=f_{1}(x)^{e_{1}}\cdots f_{k}(x)^{e_{k}}$։ Ալգորիթմում օգտագործման համար $B=(b_{ij})_{i=0,\;j=0}^{n-1,\;n-1}$ մատրիցան կառուցվում է համաձայն հետևյալ պայմանների. ${x^{iq}}\equiv \sum _{j=0}^{n-1}b_{ij}x^{j}{\pmod {f(x)}}\quad i={\overline {0,n-1}}$։ $h(x)\in \mathbb {F} _{q}[x]$ բազմանդամն այնպիսին է, որ $1\leqslant \deg {h(x)}<n,\quad {h(x)}^{q}\equiv h(x){\pmod {f(x)}}$,կոչվում է $f$-տրոհվող բազմանդամ։

Մասնավոր դեպք

Բեռլեկեմպի ալգորիթմի բլոկսխեմա, մասնավոր դեպք

$\mathbb {F} _{q}$ վերջավոր դաշտի վրա

$f(x)=f_{1}(x)\cdots f_{k}(x)$ տեսքի բազմանդամի ֆակտորիզացիայի ալգորիթմը կազմված է հետևյալ քայլերից.

1. $B$ մատրիցի հաշվում .
2. $(B-E_{n})^{T}\mathbf {x} =\mathbf {0}$ գծային հավասարումների համակարգի լուծումների ենթատարարածության ${\overline {e_{1}}},\dots ,{\overline {e_{k}}}$ բազիսի որոնում, դրա հետ մեկտեղ հաջողվում է ընտրել ${\overline {e_{1}}}=(1,\;0,\;....\;,\;0)$ վեկտորը, քանի որայն միշտ ներկա կլինի լուծումների տարածության բազիսում նկատի ունենալով, որ $x^{iq}\equiv 1{\pmod {f(x)}}$, $i=0$ դեպքում։
3. Գտնված $k$ թիվը հանդիսանում է $f(x)$ դուրս չբերվող բաժանարարների թիվը։
   • Եթե $k=1$, ապա բազմանդամը հանդիսանում է դուրս չբերվող։
   • Եթե $k>1$, ապա ${\overline {e_{l}}}$ վեկտորները ունեն $(h_{l,\;0},\dots ,h_{l,\;n-1})$ տեսքը։ Այդ թվերով կառուցում են $f$-տրոհվող բազմանդամները։

     $h_{l}(x)=\sum _{i=0}^{n-1}h_{l,\;i}\;x^{i},\quad l={\overline {2,\;k}},\quad h_{1}(x)=1.$։

4. Տրոհման որոնում։

   $f(x)=\prod _{c\in \mathbb {F} _{q},}\gcd(f(x),h_{2}(x)-c)$

   $f(x)=\prod _{m}g_{m,\;2}(x)$ տեսքով,

   որտեղ $g_{m,\;s}(x),\quad s={\overline {2,k}}$ ընդհանուր դեպքում չեն հանդիսանում դուրս չբերվող։$g_{m,\;s}(x)$ ֆունկցիաները ֆակտորիզացվում են նույն կերպով , այսինքն,

   $g_{m,\;s}(x)=\prod _{c\in \mathbb {F} _{q},}\gcd(g_{m,\;s}(x),h_{s+1}(x)-c),\quad s={\overline {2,k-1}}$.

Ընդհանուր դեպք

Բեռլեկեմպի ալգորիթմի բլոկսխեմա, մասնավոր դեպքի վերաբերյալ

Կամայական ունիտար բազմանդամի ֆակտորիզացման խնդիրը բերում է մասնավոր դեպքի քննարկման։ Դրա համար որոշվում է

$d(x)=\gcd(f(x),\;f^{'}(x))$ բազմանդամը,

Էվկլիդեսի ալգորիթմի օգտագործմամբ.

• Եթե $d(x)=1,$ ապա բազմանդամը չի պարունակում կրկնվող արմատներ,քանի որ կրկնվող արմատը միաժամանակ հանդիասանում է ածանցյալի արմատը.
• Եթե $d(x)=f(x),$ ապա $f^{'}(x)=0,$, և նշանակում է, որ $f(x)=g(x)^{p},\quad g(x)\in \mathbb {F} _{q}[x].$ Եթե $g^{'}(x)=0,$ ապա $g(x)$ համար անհրաժեշտ է նշված գործընթացը կրկնել այքան ժամանակ, մինչև չենք ստանա $f(x)=h(x)^{p^{s}},h{'}(x)\neq 0.$ տրոհումը։$h(x)$ բազմանդամը բավարարում է մասնավոր դեպքի պայմաններին .
• Այլապես, $d(x)$ բազմանդամը հանդիսանում է $f(x)$ բազմանդամի ոչ տրիվյալ բաժանարար.Իր հերթին, ${\frac {f(x)}{d(x)}}$ բազմանդամը չունի կրճատ չտրոհվող բազմապատիկներ. Եթե $d(x)$ ներառում է կրճատ բազմապատիկներ, ապա նրա համար նույնպես կիրառվում է նկարագրված պրոցեդուրան։ Իմանալով այդ տրոհումները, հեշտ է ստանալ $f(x)$ տրոհումը։

Այդ ձևով, $\mathbb {F} _{q}[x]$ վերջավոր դաշտի վրա կամայական ունիտար բազմանդամի տրոհման խնդիրը տարվում է բազմանդամների վերջավոր թվով բազմապատիկների տրոհման, որոնք չունեն կրճատ չբերվող ժազմապատիկներ, այսինքն մասնավոր դեպքի։

Հիմնավորում

Թող։

$f(x)=f_{1}(x)^{e_{1}}\cdots f_{k}(x)^{e_{k}}$, որտեղ $\quad e_{i}=1,\quad i={\overline {1,k}}$.

Համաձայն մնացորդների մասին չինական թեորեմի $\mathbb {F} _{q}$ դաշտի էլեմենտների ցանկացած $(c_{1},\;...,\;c_{k})$ հավաքածուի համար գոյություն ունի միակ բազմանդամ։

$h(x)\in \mathbb {F} _{q}[x],$

այնպիսին է, որ։

$h(x)\equiv c_{i}{\pmod {f_{i}(x)}},\;i={\overline {1,\;k}},\quad \deg {h(x)}<\deg {f(x)}$.

$h(x)$ բազմանդամը բավարարում է պայմանը ։

${h(x)}\equiv c_{i}\equiv c_{i}^{q}\equiv h(x)^{q}{\pmod {f_{i}(x)}},\quad i={\overline {1,\;k}}$,

և այդ պատճառով ։

$h(x)^{q}\equiv h(x){\pmod {f(x)}},\quad \deg {h(x)}<deg{f(x)}$.

$h(x)^{q}-h(x)=\prod _{c\in \mathbb {F} _{q}}(h(x)-c)\equiv 0{\pmod {f(x)}}$ պայմանից,

և աջ մասի բազմապատիկների փոխադարձ պարզկությունից հետևում է, որ $f(x)$ բազմանդամի յուրաքանչյուր չտրոհվող բաժանարար բաժանում է $h(x)-c$ բազմանդամներից միայն ու միայն մեկը. Այսպիսով,ապացուցվեց տրոհման ճշմարտությունն ու միակությունը։

$f(x)=\prod _{c\in \mathbb {F} _{q}}\gcd(f(x),h(x)-c).$

$h(x)=a_{0}+a_{1}x^{1}+\dots +a_{n-1}x^{n-1}\in \mathbb {F} _{q}$ բազմանդամիը գտնելու համար դիտարկենք

$h(x)^{q}\equiv h(x){\pmod {f(x)}}$ համեմատությունը,

որը հավասարազոր է պայմանին։

$\sum _{i=0}^{n-1}a_{i}x^{iq}\equiv \sum _{i=0}^{n-1}a_{i}x^{i}{\pmod {f(x)}}$.

$B$ մատրիցի որոշման համար ստանում ենք։

$\sum _{i=0}^{n-1}a_{i}\sum _{j=0}^{n-1}b_{ij}x^{j}=\sum _{i=0}^{n-1}a_{i}x^{i}$, դրա համար։

$\sum _{i=0}^{n-1}a_{i}b_{ij}=a_{j},\quad j={\overline {0,\;n-1}}$.

Ստացված հավասարությունների համակարգը որոշում է $f$-տրոհվող բազմանդամների գործակիցները և կարող է գրի առնվել

$\quad (a_{0},\;a_{1},...,a_{n-1})B=(a_{0},\;a_{1},\;...,a_{n-1})$

կամ։

$\quad (a_{0},\;a_{1},...,a_{n-1})(B-E_{n})=\mathbf {0}$ տեսքերով։

Ալգորիթմի բարդություն

Ալգորիթմի բարդությունը կազմում է $O(n^{3}+qkn)$ մաթեմատիկական գործողություն. Ալգորիթմը էֆեկտիվ կլինի միայն ոչ մեծ դաշտերի համար։ Դա կախված է բոլոր $c\in \mathbb {F} _{q}$ շատության անհրաժեշտության հետ։

Կատարելագործում

• Պարզ դաշտի դեպքում, եթե $p$ արժեքը մեծ է, ապա $c\in {\mathbb {Z} /p\mathbb {Z} }$ արժեքների շատությունը շատ ժամանակ կկազմի։ Սակայն,հնարավոր է որոշել $M$ բազմությունը,կազմված $c$ ֊ից, որոնց համար $\gcd(f(x),h(x)-c)$ ոչ տրիվյալ են. Դրա համար անհրաժեշտ է գտնել $R(c)$ ռեզուլտանտնի արմատները, որոնք և կկազմեն $M$ բազմությունը։
• $f(x)\in GF(q)[x]$ ունիտար բազմանդամի տրոհման ևս մեկ մեթոդ,կրճատ չտրոհվող բազմապատիկներ չունեցող, հիմնված է Բեռլեկեմպի ալգորիթմով անկյունագծային տեսքի A մատրիցի որոշակի էֆեկտիվ հաշվարկների բերմանը։. Այնուամենայնիվ, անկյունագծայնացման պրոցեսը բականին դժվար է։
• Կալտոֆենի և Լոբոյի աշխատության մեջ առաջարկվել էր Բեռլեկեմպի ալգորիթմի հավանական տարբերակ, որը թույլ է տալիս $n$ կարգի $f(x)\in GF(q)[x]$ բազմանդամը տրոհել բազմապատիկների $O((n\log n+\log q)\cdot n(\log n)\log(\log n))$ թվաբանական գործողություններով։ Կալտոֆեն֊Լոբոյի ալգորիթմը ռեալիզացվել է համակարգչով, և բարձր կարգի բազմանդամի համար դարձավ էֆեկտիվ , օրինակ, $\mathbb {Z} /127\mathbb {Z}$ դաշտի վրա 10001 կարգի բազմանդամի համար այն համակարգչով աշխատում է մոտավորապես 102.5 ժամ Sun-4։

Համակարգչային հանրահաշվի համակարգում ռեալիզացում

Համակարգչային հանրահաշվի համակարգում PARI/GP Բեռլեկեմպի ալգորիթմը կարող է կիրառվել factormod անմիջական հրամանով։

Գրականություն

• Berlekamp, Elwyn R. (1967). «Factoring Polynomials Over Finite Fields». Bell System Technical Journal. 46: 1853–1859. MR 0219231. BSTJ Later republished in: Berlekamp, Elwyn R. (1968). Algebraic Coding Theory. McGraw Hill. ISBN 0-89412-063-8.
• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4
• Лидл Р., Нидеррайтер Г. Конечные поля = Finite Fields / Под ред. В. И. Нечаева. — 1-е изд. — М.: Мир, 1988. — Т. 1. — 430 с. — ISBN 5-03-000065-8
• Ван дер Варден Б.Л. Алгебра. — M.: Наука, 1976. — 646 с.