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

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

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

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

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

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

Ուսումնասիրվում է վերջավոր դաշտի վրա տրված $f(x)$ կարգի բազմանդամի ֆակտորիզացիայի խնդիրը $n$ ( $n\geq 2$ ) $\mathbb {F} _{q}$ ( $q=p^{m}$ , $p$ պարզ թիվ է)^[12] տարբեր ունիտար բազմանդամների $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$ -տրոհվող բազմանդամ^[13]։

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

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

f(x)=f_{1}(x)\cdots f_{k}(x)

տեսքի բազմանդամի ֆակտորիզացիայի ալգորիթմը կազմված է հետևյալ քայլերից.

$B$ մատրիցի հաշվում ^[14].
$(B-E_{n})^{T}\mathbf {x} =\mathbf {0}$ գծային հավասարումների համակարգի լուծումների ենթատարարածության ${\overline {e_{1}}},\dots ,{\overline {e_{k}}}$ բազիսի որոնում^[15], դրա հետ մեկտեղ հաջողվում է ընտրել ${\overline {e_{1}}}=(1,\;0,\;....\;,\;0)$ վեկտորը, քանի որայն միշտ ներկա կլինի^[15] լուծումների տարածության բազիսում նկատի ունենալով, որ $x^{iq}\equiv 1{\pmod {f(x)}}$ , $i=0$ դեպքում։
Գտնված $k$ $k$ թիվը հանդիսանում է ^[14] $f(x)$ $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.$ ։
Տրոհման որոնում^[15]։
$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)$ ֆունկցիաները ֆակտորիզացվում են նույն կերպով ^[15], այսինքն,
$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,$ ապա բազմանդամը չի պարունակում կրկնվող արմատներ,քանի որ կրկնվող արմատը միաժամանակ հանդիասանում է ածանցյալի արմատը^[16].
Եթե $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)$ բազմանդամը բավարարում է մասնավոր դեպքի պայմաններին ^[16].
Այլապես, $d(x)$ բազմանդամը հանդիսանում է $f(x)$ բազմանդամի ոչ տրիվյալ բաժանարար.Իր հերթին, ${\frac {f(x)}{d(x)}}$ բազմանդամը չունի կրճատ չտրոհվող բազմապատիկներ^[16]. Եթե $d(x)$ ներառում է կրճատ բազմապատիկներ, ապա նրա համար նույնպես կիրառվում է նկարագրված պրոցեդուրան։ Իմանալով այդ տրոհումները, հեշտ է ստանալ $f(x)$ տրոհումը։

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

Հիմնավորում

Թող։

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}$ ^[17] դաշտի էլեմենտների ցանկացած $(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)$ բազմանդամը բավարարում է պայմանը ^[17]։

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

,

և այդ պատճառով ^[18]։

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$ բազմանդամներից միայն ու միայն մեկը. Այսպիսով,ապացուցվեց ^[18] տրոհման ճշմարտությունն ու միակությունը։

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)}}

համեմատությունը,

որը հավասարազոր է ^[17] պայմանին։

\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}

, դրա համար^[17]։

\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}

^[17] տեսքերով։

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

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

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

Պարզ դաշտի դեպքում, եթե $p$ արժեքը մեծ է, ապա $c\in {\mathbb {Z} /p\mathbb {Z} }$ արժեքների շատությունը շատ ժամանակ կկազմի։ Սակայն,հնարավոր է որոշել $M$ բազմությունը,կազմված $c$ ֊ից, որոնց համար $\gcd(f(x),h(x)-c)$ ոչ տրիվյալ են^[20]. Դրա համար անհրաժեշտ է գտնել ^[21] $R(c)$ ռեզուլտանտնի արմատները, որոնք և կկազմեն $M$ բազմությունը։
$f(x)\in GF(q)[x]$ ունիտար բազմանդամի տրոհման ևս մեկ մեթոդ,կրճատ չտրոհվող բազմապատիկներ չունեցող, հիմնված է Բեռլեկեմպի ալգորիթմով անկյունագծային տեսքի A մատրիցի որոշակի էֆեկտիվ հաշվարկների բերմանը։^[22]. Այնուամենայնիվ, անկյունագծայնացման պրոցեսը բականին դժվար է։
Կալտոֆենի և Լոբոյի աշխատության մեջ^[23] առաջարկվել էր Բեռլեկեմպի ալգորիթմի հավանական տարբերակ, որը թույլ է տալիս $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^[24] անմիջական հրամանով։

Ծանոթագրություններ

↑ Berlekamp, 1967, էջ 1854: «О циклических кодах»
↑ ^2,0 ^2,1 Berlekamp, 1967
↑ Berlekamp, 1967, էջ 1853
↑ Голомб, Соломон Вольф Shift Register Sequences. — Aegean Park Pr; Revised edition, 1981. — 274 с. — ISBN 978-0894120480
↑ Կաղապար:Հոդվածում
↑ Butler, M. C. R. On the reducibility of polynomials over a finite field. — The Quarterly Journal of Mathematics Oxford Second Series 5, 1954. — С. 102-107.
↑ Schwarz, St. On the reducibility of polynomials over a ﬁnite ﬁeld. — Quart. J. Math. Oxford Ser.(2) 7, 1956. — С. 110-124.
↑ Лидл, 1988, Исторические комментарии, էջ 223-224
↑ Cantor D.G., Zassenhaus H. A new algorithm for factoring polynomials over finite fields. — Math. Comp., 1981. — Vol. 36. — P. 587—592.
↑ von zur Gathen J., Shoup V. Computing Frobenius maps and factoring polynomials. — Comput. Complexity, 1992. — Т. 2. — С. 187–224.
↑ Василенко, 2003, էջ 185: «Сложность алгоритма Кантора—Цассенхауза»
↑ Лидл, 1988, Постановка задачи, էջ 187
↑ Василенко, 2003, Определения, էջ 172
↑ ^14,0 ^14,1 Василенко, 2003, Описание алгоритма, էջ 173
↑ ^15,0 ^15,1 ^15,2 ^15,3 Лидл, 1988, Описание алгоритма
↑ ^16,0 ^16,1 ^16,2 ^16,3 Лидл, 1988, Сведение к основному случаю, էջ 188
↑ ^17,0 ^17,1 ^17,2 ^17,3 ^17,4 Лидл, 1988, Обоснование корректности алгоритма, էջ 189-190
↑ ^18,0 ^18,1 Василенко, 2003, էջ 174
↑ Василенко, 2003, էջ 174: «Сложность алгоритма»
↑ Лидл, 1988, Подробнее о методе, էջ 201
↑ Ван дер Варден, 1976, О результанте, էջ 124
↑ Лидл, 1988, Подробнее о методе, էջ 206
↑ Kaltofen E, Lobo A. Factoring high-degree polynomials by the black box Berlekamp algorithm(անգլ.) // Proceedings of the international symposium on Symbolic and algebraic computation (ISSAC ’94). — N. Y.: ACM Press, 1994. — С. 90—98. — ISBN 0-89791-638-7. — doi:10.1145/190347.190371
↑ «Catalogue of GP/PARI Functions: Arithmetic functions». Արխիվացված է օրիգինալից 2007 թ․ մարտի 11-ին. Վերցված է 2017 թ․ հոկտեմբերի 31-ին.

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

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 с.

[Berlekamp—1967——1854О_циклических_кодах-1] Berlekamp, 1967, էջ 1854: «О циклических кодах»

[Berlekamp—1967——-2] 2,0 ^2,1 Berlekamp, 1967

[Berlekamp—1967——1853-3] Berlekamp, 1967, էջ 1853

[4] Голомб, Соломон Вольф Shift Register Sequences. — Aegean Park Pr; Revised edition, 1981. — 274 с. — ISBN 978-0894120480

[5] Կաղապար:Հոդվածում

[6] Butler, M. C. R. On the reducibility of polynomials over a finite field. — The Quarterly Journal of Mathematics Oxford Second Series 5, 1954. — С. 102-107.

[7] Schwarz, St. On the reducibility of polynomials over a ﬁnite ﬁeld. — Quart. J. Math. Oxford Ser.(2) 7, 1956. — С. 110-124.

[Лидл—1988—Исторические_комментарии—223-224-8] Лидл, 1988, Исторические комментарии, էջ 223-224

[9] Cantor D.G., Zassenhaus H. A new algorithm for factoring polynomials over finite fields. — Math. Comp., 1981. — Vol. 36. — P. 587—592.

[10] von zur Gathen J., Shoup V. Computing Frobenius maps and factoring polynomials. — Comput. Complexity, 1992. — Т. 2. — С. 187–224.

[Василенко—2003——185Сложность_алгоритма_Кантора—Цассенхауза-11] Василенко, 2003, էջ 185: «Сложность алгоритма Кантора—Цассенхауза»

[Лидл—1988—Постановка_задачи—187-12] Лидл, 1988, Постановка задачи, էջ 187

[Василенко—2003—Определения—172-13] Василенко, 2003, Определения, էջ 172

[Василенко—2003—Описание_алгоритма—173-14] 14,0 ^14,1 Василенко, 2003, Описание алгоритма, էջ 173

[Лидл—1988—Описание_алгоритма—-15] 15,0 ^15,1 ^15,2 ^15,3 Лидл, 1988, Описание алгоритма

[Лидл—1988—Сведение_к_основному_случаю—188-16] 16,0 ^16,1 ^16,2 ^16,3 Лидл, 1988, Сведение к основному случаю, էջ 188

[Лидл—1988—Обоснование_корректности_алгоритма—189-190-17] 17,0 ^17,1 ^17,2 ^17,3 ^17,4 Лидл, 1988, Обоснование корректности алгоритма, էջ 189-190

[Василенко—2003——174-18] 18,0 ^18,1 Василенко, 2003, էջ 174

[Василенко—2003——174Сложность_алгоритма-19] Василенко, 2003, էջ 174: «Сложность алгоритма»

[Лидл—1988—Подробнее_о_методе—201-20] Лидл, 1988, Подробнее о методе, էջ 201

[Ван_дер_Варден—1976—О_результанте—124-21] Ван дер Варден, 1976, О результанте, էջ 124

[Лидл—1988—Подробнее_о_методе—206-22] Лидл, 1988, Подробнее о методе, էջ 206

[23] Kaltofen E, Lobo A. Factoring high-degree polynomials by the black box Berlekamp algorithm(անգլ.) // Proceedings of the international symposium on Symbolic and algebraic computation (ISSAC ’94). — N. Y.: ACM Press, 1994. — С. 90—98. — ISBN 0-89791-638-7. — doi:10.1145/190347.190371

[24] «Catalogue of GP/PARI Functions: Arithmetic functions». Արխիվացված է օրիգինալից 2007 թ․ մարտի 11-ին. Վերցված է 2017 թ․ հոկտեմբերի 31-ին.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]