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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search
Բեռլեկեմպի ալգորիթմ
Տեսակ ալգորիթմ
Հայտնաբերող Էլվին Բեռլեկեմպ
Անվանված է Էլվին Բեռլեկեմպ

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

Ստեղծման պատմություն[խմբագրել | խմբագրել կոդը]

Ամերիկացի մաթեմատիկոս, Կալիֆոռնիայի համալսարանի պրոֆեսոր Բեռլեկեմպը զբաղվել է սխալների հայտնաբերման և ճշգրտման ցիկլիկ կոդի, այդ թվում նաև Չոուդխուր֊Խոկվինգեմի կոդի ուսումնասիրությամբ, որոնց հատկությունները կախված են վերածնող բազմանդամի բաժանարարներից։ Այդ կոդերի ապակոդավորման շրջանում Բեռլեկեմպի տեխնիկական հաջողությունները պրակտիկայի տեսանկյունից իրենց դարձրեցին առավել կարևոր[1]։ Ալգորիթմը առաջին անգամ շարադրվել է «Factoring Polynomials Over Finite Fields»[2] հոդվածում և ավելի ուշ հրատարակվել է «Algebraic Coding Theory»[2] գրքում։ 1967 թվականի այդ աշխատության մեջ [3] Բեռլեկեմպը գրում է, որ ֆակտորիզացիայի խնդիրը առաջանում է Գոլոմբի աշխատություններում[4]։ Այնուամենայնիվ, բազմանդամի նորմավորված բազմապատկիչների թվի որոշման մատրիցի օգտագործումը առաջին անգամ նշվել[5]. Բաթլերի հոդվածում [6] որոշվել է, որ մատրիցայի ռանգը հավասար է , այդ փաստի մեկ այլ ապացույց տրվել է Շվարցի կողմից[7]։ Բեռլեկեմպի ալգորիթմը հիշատակվել է մի շարք աշխատություններում[8] և մինչև 1981 թվականին[9].հայտնվելը հանդիսանում է ֆակտորիզացիայի խնդրի լուծման հիմնական ալգորիթմ։ Մշակվել էր տեխնիկա[10], որը հնարավորություն էր տալիս բազմանդամը տրոհել բազմապատկիչների, որտեղ ֊ն՝ քառակուսի մատրիցի վերաբազմապատկման բարդության գործակիցն է[11]։

Տրում և որոշում[խմբագրել | խմբագրել կոդը]

Ուսումնասիրվում է վերջավոր դաշտի վրա տրված կարգի բազմանդամի ֆակտորիզացիայի խնդիրը () (, պարզ թիվ է)[12] տարբեր ունիտար բազմանդամների ։ Ալգորիթմում օգտագործման համար մատրիցան կառուցվում է համաձայն հետևյալ պայմանների. ։ բազմանդամն այնպիսին է, որ ,կոչվում է -տրոհվող բազմանդամ[13]։

Մասնավոր դեպք[խմբագրել | խմբագրել կոդը]

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

վերջավոր դաշտի վրա

տեսքի բազմանդամի ֆակտորիզացիայի ալգորիթմը կազմված է հետևյալ քայլերից.
  1. մատրիցի հաշվում [14].
  2. գծային հավասարումների համակարգի լուծումների ենթատարարածության բազիսի որոնում[15], դրա հետ մեկտեղ հաջողվում է ընտրել վեկտորը, քանի որայն միշտ ներկա կլինի[15] լուծումների տարածության բազիսում նկատի ունենալով, որ , դեպքում։
  3. Գտնված թիվը հանդիսանում է [14] դուրս չբերվող բաժանարարների թիվը։
    • Եթե , ապա բազմանդամը հանդիսանում է դուրս չբերվող։
    • Եթե , ապա վեկտորները ունեն տեսքը։ Այդ թվերով կառուցում են -տրոհվող բազմանդամները:
      ։
  4. Տրոհման որոնում[15]:
    տեսքով,
    որտեղ ընդհանուր դեպքում չեն հանդիսանում դուրս չբերվող։ ֆունկցիաները ֆակտորիզացվում են նույն կերպով [15], այսինքն,
    .

Ընդհանուր դեպք[խմբագրել | խմբագրել կոդը]

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

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

բազմանդամը,

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

  • Եթե ապա բազմանդամը չի պարունակում կրկնվող արմատներ,քանի որ կրկնվող արմատը միաժամանակ հանդիասանում է ածանցյալի արմատը[16].
  • Եթե ապա , և նշանակում է, որ Եթե ապա համար անհրաժեշտ է նշված գործընթացը կրկնել այքան ժամանակ, մինչև չենք ստանա տրոհումը։ բազմանդամը բավարարում է մասնավոր դեպքի պայմաններին [16].
  • Այլապես, բազմանդամը հանդիսանում է բազմանդամի ոչ տրիվյալ բաժանարար.Իր հերթին, բազմանդամը չունի կրճատ չտրոհվող բազմապատիկներ[16]. Եթե ներառում է կրճատ բազմապատիկներ, ապա նրա համար նույնպես կիրառվում է նկարագրված պրոցեդուրան։ Իմանալով այդ տրոհումները, հեշտ է ստանալ տրոհումը։

Այդ ձևով, վերջավոր դաշտի վրա կամայական ունիտար բազմանդամի տրոհման խնդիրը տարվում է բազմանդամների վերջավոր թվով բազմապատիկների տրոհման, որոնք չունեն կրճատ չբերվող ժազմապատիկներ, այսինքն մասնավոր դեպքի[16]։

Հիմնավորում[խմբագրել | խմբագրել կոդը]

Թող:

, որտեղ .

Համաձայն մնացորդների մասին չինական թեորեմի [17] դաշտի էլեմենտների ցանկացած հավաքածուի համար գոյություն ունի միակ բազմանդամ։

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

.

բազմանդամը բավարարում է պայմանը [17]:

,

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

.
պայմանից,

և աջ մասի բազմապատիկների փոխադարձ պարզկությունից հետևում է, որ բազմանդամի յուրաքանչյուր չտրոհվող բաժանարար բաժանում է բազմանդամներից միայն ու միայն մեկը. Այսպիսով,ապացուցվեց [18] տրոհման ճշմարտությունն ու միակությունը:

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

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

.

մատրիցի որոշման համար ստանում ենք:

, դրա համար[17]:
.

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

կամ:

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

Ալգորիթմի բարդություն[խմբագրել | խմբագրել կոդը]

Ալգորիթմի բարդությունը կազմում է մաթեմատիկական գործողություն[19]. Ալգորիթմը էֆեկտիվ կլինի միայն ոչ մեծ դաշտերի համար։ Դա կախված է բոլոր շատության անհրաժեշտության հետ։

Կատարելագործում[խմբագրել | խմբագրել կոդը]

  • Պարզ դաշտի դեպքում, եթե արժեքը մեծ է, ապա արժեքների շատությունը շատ ժամանակ կկազմի։ Սակայն,հնարավոր է որոշել բազմությունը,կազմված ֊ից, որոնց համար ոչ տրիվյալ են[20]. Դրա համար անհրաժեշտ է գտնել [21] ռեզուլտանտնի արմատները, որոնք և կկազմեն բազմությունը։
  • ունիտար բազմանդամի տրոհման ևս մեկ մեթոդ,կրճատ չտրոհվող բազմապատիկներ չունեցող, հիմնված է Բեռլեկեմպի ալգորիթմով անկյունագծային տեսքի A մատրիցի որոշակի էֆեկտիվ հաշվարկների բերմանը։[22]. Այնուամենայնիվ, անկյունագծայնացման պրոցեսը բականին դժվար է։
  • Կալտոֆենի և Լոբոյի աշխատության մեջ[23] առաջարկվել էր Բեռլեկեմպի ալգորիթմի հավանական տարբերակ, որը թույլ է տալիս կարգի բազմանդամը տրոհել բազմապատիկների թվաբանական գործողություններով։ Կալտոֆեն֊Լոբոյի ալգորիթմը ռեալիզացվել է համակարգչով, և բարձր կարգի բազմանդամի համար դարձավ էֆեկտիվ , օրինակ, դաշտի վրա 10001 կարգի բազմանդամի համար այն համակարգչով աշխատում է մոտավորապես 102.5 ժամ Sun-4։

Համակարգչային հանրահաշվի համակարգում ռեալիզացում[խմբագրել | խմբագրել կոդը]

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

Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]

  1. Berlekamp, 1967, էջ 1854: «О циклических кодах»
  2. 2,0 2,1 Berlekamp, 1967
  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 finite field. — Quart. J. Math. Oxford Ser.(2) 7, 1956. — С. 110-124.
  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.
  11. Василенко, 2003, էջ 185: «Сложность алгоритма Кантора—Цассенхауза»
  12. Лидл, 1988, մեկնաբանություն՝ Постановка задачи, էջ 187
  13. Василенко, 2003, մեկնաբանություն՝ Определения, էջ 172
  14. 14,0 14,1 Василенко, 2003, մեկնաբանություն՝ Описание алгоритма, էջ 173
  15. 15,0 15,1 15,2 15,3 Лидл, 1988, մեկնաբանություն՝ Описание алгоритма
  16. 16,0 16,1 16,2 16,3 Лидл, 1988, մեկնաբանություն՝ Сведение к основному случаю, էջ 188
  17. 17,0 17,1 17,2 17,3 17,4 Лидл, 1988, մեկնաբանություն՝ Обоснование корректности алгоритма, էջ 189-190
  18. 18,0 18,1 Василенко, 2003, էջ 174
  19. Василенко, 2003, էջ 174: «Сложность алгоритма»
  20. Лидл, 1988, մեկնաբանություն՝ Подробнее о методе, էջ 201
  21. Ван дер Варден, 1976, մեկնաբանություն՝ О результанте, էջ 124
  22. Лидл, 1988, մեկնաբանություն՝ Подробнее о методе, էջ 206
  23. Kaltofen E, Lobo A. Factoring high-degree polynomials by the black box Berlekamp algorithm (en) // 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

Գրականություն[խմբագրել | խմբագրել կոդը]

  • Лидл Р., Нидеррайтер Г. Конечные поля = Finite Fields / Под ред. В. И. Нечаева. — 1-е изд. — М.: Мир, 1988. — Т. 1. — 430 с. — ISBN 5-03-000065-8
  • Ван дер Варден Б.Л. Алгебра. — M.: Наука, 1976. — 646 с.