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

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

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

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

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

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

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

$𝔽_{q}$ վերջավոր դաշտի վրա

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

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

$B$ մատրիցի հաշվում Կաղապար:Sfn.
$(B - E_{n})^{T} 𝐱 = 𝟎$ գծային հավասարումների համակարգի լուծումների ենթատարարածության $\overline{e_{1}}, \dots, \overline{e_{k}}$ բազիսի որոնումԿաղապար:Sfn, դրա հետ մեկտեղ հաջողվում է ընտրել $\overline{e_{1}} = (1, 0, . . . ., 0)$ վեկտորը, քանի որայն միշտ ներկա կլինիԿաղապար:Sfn լուծումների տարածության բազիսում նկատի ունենալով, որ $x^{i q} \equiv 1 (\mod f (x))$ , $i = 0$ դեպքում։
Գտնված k թիվը հանդիսանում է Կաղապար:Sfn 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}, l = \overline{2, k}, h_{1} (x) = 1 .$ ։
Տրոհման որոնումԿաղապար:Sfn։
$f (x) = \prod_{c \in 𝔽_{q},} \gcd (f (x), h_{2} (x) - c)$

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

որտեղ $g_{m, s} (x), s = \overline{2, k}$ ընդհանուր դեպքում չեն հանդիսանում դուրս չբերվող։ $g_{m, s} (x)$ ֆունկցիաները ֆակտորիզացվում են նույն կերպով Կաղապար:Sfn, այսինքն,
$g_{m, s} (x) = \prod_{c \in 𝔽_{q},} \gcd (g_{m, s} (x), h_{s + 1} (x) - c), s = \overline{2, k - 1}$ .

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

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

d (x) = \gcd (f (x), f^{'} (x))

բազմանդամը,

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

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

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

Հիմնավորում

Թող։

f (x) = f_{1} (x)^{e_{1}} \dots f_{k} (x)^{e_{k}}

, որտեղ

e_{i} = 1, i = \overline{1, k}

.

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

h (x) \in 𝔽_{q} [x],

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

h (x) \equiv c_{i} (\mod f_{i} (x)), i = \overline{1, k}, \deg h (x) < \deg f (x)

.

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

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

,

և այդ պատճառով Կաղապար:Sfn։

h (x)^{q} \equiv h (x) (\mod f (x)), \deg h (x) < d e g f (x)

.

h (x)^{q} - h (x) = \prod_{c \in 𝔽_{q}} (h (x) - c) \equiv 0 (\mod f (x))

պայմանից,

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

f (x) = \prod_{c \in 𝔽_{q}} \gcd (f (x), h (x) - c) .

h (x) = a_{0} + a_{1} x^{1} + \dots + a_{n - 1} x^{n - 1} \in 𝔽_{q}

բազմանդամիը գտնելու համար դիտարկենք

h (x)^{q} \equiv h (x) (\mod f (x))

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

որը հավասարազոր է Կաղապար:Sfn պայմանին։

\sum_{i = 0}^{n - 1} a_{i} x^{i q} \equiv \sum_{i = 0}^{n - 1} a_{i} x^{i} (\mod f (x))

.

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

\sum_{i = 0}^{n - 1} a_{i} \sum_{j = 0}^{n - 1} b_{i j} x^{j} = \sum_{i = 0}^{n - 1} a_{i} x^{i}

, դրա համարԿաղապար:Sfn։

\sum_{i = 0}^{n - 1} a_{i} b_{i j} = a_{j}, j = \overline{0, n - 1}

.

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

(a_{0}, a_{1}, . . ., a_{n - 1}) B = (a_{0}, a_{1}, . . ., a_{n - 1})

կամ։

(a_{0}, a_{1}, . . ., a_{n - 1}) (B - E_{n}) = 𝟎

Կաղապար:Sfn տեսքերով։

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

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

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

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

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

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

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

Կաղապար:Ծանցանկ

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

Կաղապար:Արտաքին հղումներ

[1] Կաղապար:Ռուսերեն գիրք

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

[3] Կաղապար:Ռուսերեն հոդված

[4] Կաղապար:Ռուսերեն հոդված

[5] Կաղապար:Ռուսերեն գիրք

[6] Կաղապար:Ռուսերեն հոդված

[7] Կաղապար:Ռուսերեն հոդված

[8] Կաղապար:Cite web

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

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

Բովանդակություն

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

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

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

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

Հիմնավորում

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

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

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

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

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

Նավարկման ցանկ

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

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

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

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

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

Հիմնավորում

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

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

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

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

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

Նավարկման ցանկ

Որոնում