Մնացորդների մասին չինական թեորեմ

Վիքիպեդիայից՝ ազատ հանրագիտարանից

Մնացորդների մասին չինական թեորեմ, մի քանի գծային համակարգի կապակցված պնդումների համեմատում։

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

Այս թեորեմը իր թվաբանական ձևակերպմամբ նկարագրվել է չինական մաթեմատիկոս Սուն Ցզիի «Սուն Ցզի Սուան Ցզին» տրակտատում (չին.՝ 孙子算经), մոտավորապես թվագրվել է մ․թ․ա երրորդ դարում և այնուհետև ընդհանրացվել է Ցին Ցզյուշաոյի կողմից իր «Մաթեմատիկական դատողություններ 9 գլխով», տպագրված 1247 թվականին, որտեղ բերված էր ճշգրիտ լուծումը[1]։

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

Եթե բնական թվերը զույգ առ զույգ փոխադարձ պարզ են, ապա ցանկացած ամբողջ այնպիսին է, որ բոլոր համար կգտնվի , որը վրա բաժանելիս տալիս է մնացորդ բոլոր համար։ Ավելին, եթե գտնվեն այնպիսի երկու՝ և , ապա ։

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

Ինդդուկցիա հավասարումների քանակով[խմբագրել | խմբագրել կոդը]

Օգտվենք մաթեմատիկական ինդուկցիայի մեթոդից։ դեպքում թեորեմի պնդումը ակնհայտ է։ Թող թեորեմը ճշմարիտ լինի դեպքում, ապա գոյություն ունի թիվը, որը դեպքում թվի վրա բաժանելիս տալիս է մնացորդը։ Նշանակենք

։

Ընտրում ենք կամայական թիվը, որը փոխադաչձ պարզ է բոլոր հետ և դիտարկենք թվերը։Ցույց տանք, որ բոլոր հանդիսանում են մնացորդներ ֊ի ինչ֊որ էլեմենտների՝ վրա բաժանելիս։ Ենթադրենք, որ դա այդպես չէ, այսինքն գոյություն ունեն որոշակի , որոնք չեն պատկանում էլեմենտների՝ վրա բաժանելիս ստացված մնացորդների բազմությանը։Քանի որ այդ էլեմենտների թիվը հավասար է ,իսկ ֊ի ինչ֊որ էլեմենտների՝ վրա բաժանելիս հնարավոր մնացորդները հնարավոր է շատ չեն, քան (քանի որ ոչ մի թիվ չի տալիս մնացորդ), ապա նրանց մեջ կգտնվեն երկու թիվ, որոնք ունեն հավասար մնացորդներ (Դիրիխլեի արկղի սկզբունք). Թող այդ թվերը լինեն և , դեպքում. Այդ դեպքում իրենց տարբերությունը բաժանվում է վրա, ինչը հնարավոր է, քանի որ , , և հետ փոխադարձ պարզ են, այլապես թվերը զույգ առ զույգ փոխադարձ պարզ են (ըստ պայմանի). Հակասություն։ Այսպիսով, դիտարկվող թվերի մեջ կգտնվի math>N = m + t\cdot d</math> թիվ, որը վրա բաժանելիս տալիս է մնացորդ. Միևնույն ժամանակ վրա բաժանելիս թիվը համապատասխանաբար տալիս է մնացորդ,քանի որ ։ Այժմ ապացուցենք, որ . Իրականում , այսինքն . այսպիսով, թիվը բոլոր բաժանում է առանց մնացորդի, ինչպես նաև իրենց արտադրյալները։ Ինչն էլ պահանջվում էր ապացուցել։

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

Ներքևում նկարագրված թեորեմի ապացույցը օգնում է լուծել պրակտիկորեն կարևոր խնդիր՝ մոդուլով դծային հավասարումների համակարգի լուծման որոնում։[2]. Դիտարկենք

(1)

հավասարումների համակարգը։

Եթե և բավարարում են թեորեմի պայմաններին, ապա (1)համակարգի լուծումը գոյություն ունի և մոդուլով ճշտությամբ միակն է, որտեղ , ընդ որում ճշմարիտ է բանաձևը[2][3][4]

, որտեղ , իսկ — հակադարձ մուլտիպլիկատիվ օղակի էլեմենտ է։

(2)

Ցույց տանք, որ այդ եղանակով որոշված ֊ը հանդիսանում է լուծում։ Ստուգենք, որ նրա համար համակարգումգործում է i-е հավասարությունը[3]: Երկրորդ հավասարությունը ճշմարիտ է, քանի որ , բոլոր դեպքում, երրորդը, քանի որ հանդիսանում է հակադարձ մոդուլով համար։ Բոլոր համար կրկնելով դատողությունը, համոզվենք, որ (2) բանաձևով որոշված ֊ը հանդիսանում է լուծում (1) համար։

Բոլոր թվերը, ընտրված թվի համաձայն,կբավարարեն համակարգին։ Այժմ ցույց տանք, որ (բազմություն ) թվերի մեջ մեր գտած լուծումից բացի ուրիշ լուծում չի գտնվի։ Այդ փաստի հակառակ ապացույցը։ Ենթադրենք, որ հաջողվել է մնացորդների որոշակի հավաքածուի համար գտնել գոնե երկու՝ լուծում։ Քանի որ բոլոր թույլատրելի հավաքածուների բազմությունը հանդիսանում է հավասարահզոր բազմությանը, ապա և համար գործում է ։ Սակայն, վերը ապացուցվածի համաձայն, ֊ի ցանկացաց հավաքածուի համար գոյություն ունի ֊ից լուծում, հետևաբար Դիրիխլեի սկզբունքի համաձայն կգտնվեն ամենաքիչը երկու մնացորդների հավաքածուներ, որոնց համապատասխանում է նույն ֊ն։ Այդպիսի ֊ի համար կգտնվի այնպիսի , որ և . Հակասություն[5]. Ինչն էլ պահանջվում էր ապացուցել։

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

Վերը ապացուցվածից հետևում է, որ ցանկացած հավաքածուի մնացորդների վեկտորի և բազմության թվի միջև գոյություն ունի միարժեք փոխադարձ համապատասխանություն, ինչը նշանակում է, որ (2) ֊ով տրված ֊ի արտապատկերումը մեջ հանդիսանում է բիեկտիվ[5]. Նկատենք, որ

; համապատասխանությունից բացի

ճշմարիտ են նաև [6][7]

;

.

Մնացորդների վեկտորի անցումը թվի ժամանակավոր բարդությունը գնահատվում է , որտեղ k ֊ն վերականգնվող թիվն է բիթերո[3]։

Լուծումների որոշման ալգորիթմ[խմբագրել | խմբագրել կոդը]

Բերենք ներքևում խնդիրների լուծման ալգորիթմ, որը դրվում է թվի, որոշակի տրված փոխադարձ պարզ թվերի բաժանումով իր մնացորդների հավաքածուով, վերականգնման թեորեմում։

Էլեմենտար հանրահաշիվ[խմբագրել | խմբագրել կոդը]

Որպես օրինակ դիտարկենք

համակարգը։

Համակարգի լուծման համար առանձին արտագրենք առաջին, երկրորդ և երրորդ հավասարումների լուծումները 2 × 3 × 7 = 42):

Ակնհայտ է, որ համակարգի լուծումների բազմությունը կլինի վերը ներկայացված բազմությունների հատումը։ Թեորեմի պնդման համաձայն լուծումը գոյություն ունի և միակն է մինչև 42 մոդուլի վերցնելը ճշտությամբ։ Մեր դեպքում կամ

Ուրիշ ճանապար ցույց տալու համար խնդիրը վերաձևակերպենք։ Գտնենք թվերի (u, v, w) այնպիսի եռյակ, որ:

x ֊ը առաջին հավասարումից երկրորդի մեջ տեղափոխելով կստանանք , այդ դեպքում , կամ , կամ , կամ ;

հետո x ֊ը տեղափոխելով առաջին հավասարումից երրորդի մեջ տեսքի արտահայտության հաշվարկի համար, կստանանք կամ , և հետևաբար ;

այդ դեպքում .

Մնացորդների մասին չինական թեորեմի հիմքի վրա ալգորիթմ[խմբագրել | խմբագրել կոդը]

Ալգորիթմը տարվում է դեպի թեորեմում տրված բանաձևով լուծումների որոնում[8]։

Քայլ 1. Հաշվում ենք ։

Քայլ 2. Բոլոր համար գտնում ենք ։

Քայլ 3. Գտնում ենք (օրինակ, օգտագործելով Էվկլիդեսի ընդլայնված ալգորիթմ)։

Քայլ 4. Հաշվում ենք հիմնական արժեքը բանաձևով։

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

Դիտարկենք մոդուլների խումբը, բավարարող թեորեմի պայմաններին։ Թվերի տեսության մեկ այլ թեորեմով հիմնավորվում է,որ ցանկացած թիվ միանշանակ ներկայացնելի է[9]

տեսքով։

Հերթականությամբ հաշվելով բոլոր для գործակիցները, մենք կկարողանանք տեղադրել դրանք բանաձևում և գտնել հիմնական լուծումը[10]:

Նշանակենք և դիտարկենք մոդուլով արտահայտություն համար։

;

;

;

;

և այլն։

գործակիցների որոնման ալգորիթմը ակնառուության համար կիրառենք կոդով, ենթադրությամբ, որ a, remainders զանգվածները և հակադարձ էլեմենտների inverses երկչափ զանգվածը արդեն ստացել են անհրաժեշտ արժեքները։

for (int i = 0; i < n; i++) {
	x[i] = remainders[i];
	for (int j = 0; j < i; j++) {
		x[i] = inverses[j][i] * (x[i] - x[j]);
		x[i] = x[i] % a[i];
		if (x[i] < 0)
			x[i] += a[i];
	}
}

Տրված ալգորիթմի համար գործակիցների որոշման բարդությունը է։ Բարդությունը նույնպիսին է նաև գտնված գործակիցներով իրական արժեքի վերականգման դեպքում։

Վարիացիաներ և ընդհանրացումներ[խմբագրել | խմբագրել կոդը]

Բանաձևայնացում օղակների համար[խմբագրել | խմբագրել կոդը]

Թող —ն լինի միավորով կոմուտատիվ օղակներ, ֊ն՝ սյուրեկտիվ հոմոմորֆիզմներ, հատկանիշներով օժտված, բոլոր համար։ Այդ դեպքում

հոմոմորֆիզմը,

տրված

բանաձևով,

հանդիսանում է սյուրեկտիվ։ Առավել ևս, որոշում է իզոմորֆիզմ

։

Եթե տեղադրել և հոմոմորֆիզմը որոշել հետևյալ կերպ․

,

ապա մենք կստանանք թեորեմի թվաբանական տարբերակը։

Այդպես հաճախ հանդիպում է օղակների էկվիվալենտ ձևակերպումը, որտեղ ունեն տեսքը, իդեալների որոշակի խմբի, հոմոմորֆիզները հանդիսանում են իրական պրոյեկցիաներ վրաև պահանջվում է, որպիսի ցանկացած համար։ Ուրիշ բառերով, եթե իդեալները զույգ առ զույգ փոխադարձ պարզ են (այսինքն երկու իդեալների գումարը հավասար է հենց օղակին), ապա նրանց արտադրյալը համընկնում է իրենց հատման հետ և ֆակտոր օղակը այդ արտադրյալով իզոմորֆ է ֆակտորների արտադրյալին․

։

Ապացույց էվկլիդյան օղակների համար[խմբագրել | խմբագրել կոդը]

Թող լինի էվլկիդյան օղակ և ֊ն՝ փոխադարձ պարզ թվեր։ Այդ դեպքում կապացուցենք, որ գոյություն ունի կոռեկտ տրված իզոմորֆիզմ․

 ուղիղ արտապատկերումն ակնհայտ է։

Հակառակ արտապատկերման գոյության ապացուցման համար դիտարկենք և էկվիվալենտության դասերը։

կգտնենք լուծելով հավասարումների հետևյալ համակարգը․

Անալոգ ձևով գտնենք :

Ցույց տանք, որ ընդհանուր տեսքով գործում է․

, քանի որ և

, քանի որ և

Ստուգենք արտապատկերման կոռեկտությունը, այսինքն, որ դասի տարբեր էլէմենտներ վերցնելու դեպքում արդյունքը չի փոխվում։

Նշանակում է , արտապատկերումը կոռեկտ է։

Կարելի է ստուգել, որ կառուցված արտապատկերումը ճիշտ հակառակն է։

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

Մնացորդների մասին չինական թեորեմը լայն կիրառում ունի թվերի տեսության, ծածկագրության մեջ և այլ տեղերում։

  • Փոխադարձ միարժեք համապատասխանությունը կամայական թվի և իր մնացորդների միչև,փոխադարձ պարզ թվերի խմբով վորոշվող, որի գոյությունը հաստատվում է թեորեմում, պրակտիկայում օգնում է աշխատել ոչ երկար թվերի հետ, այլ իր մնացորդների կարճ երկարությամբ խմբերի հետ։ Բացի դրանից, մոդուլներից յուրաքանչյուրի հաշվումը կարելի է կատարել զուգահեռ[11]։ Եթե, որպես բազիս վերցնենք, օրինակ, առաջին 500 պարզ թվերը, որոնցից յուրաքանչյուրի երկարությունը չի գերազանցում 12 բիթ, ապա դա բավարար է տասական թվերի ներկայացմանը մինչև 1519 նշան երկարությամբ։ (Թե,որտեղից է վերցրված 1519 թիվը, շատ հեշտ է հասկանալ․ առաջին 500 պարզ թվերի տասական լոգարիթմների գումարը հավասար է 1519,746…)։
Օրինակ, RSA ալգորիթմում հաշվումը կատարվում է n շատ մեծ թվի մոդուլով, ներկայացված երկու մեծ պարզ թվերի արտադրյալի տեսքով։ Թեորեմը թույլ է տալիս անցում կատարել այդ պարզ բաժանարարների մոդուլով հաշվմանը, որոնք մեծությամբ արդեն n արմատների կարգի են, նշանակում է ունեն երկու անգամ փոքր բիթային երկարություն[12]։
Նշենք նաև, որ հաշվարկների օգտագործումը, համաձայն մնացորդների մասին չինական թեորեմի, RSA ալգորիթմը ժամանակային հարձակումները դարձնում է ընկալելի։[13].

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

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

  • С. Ленг Алгебра. — М.: Мир, 1968. — С. 82—83.
  • Гольденберг А. Задача остатков (ru) // В.О.Ф.Э.М.. — 1887. — № 35. — С. 247—253.
  • Н. Смарт Криптография. — 2005. — 528 с.
  • Нестеренко А. Введение в современную криптографию.Теоретико-числовые алгоритмы. — 2011. — 190 с.
  • Переславцева О. Н. Распараллеливание алгоритмов с применением китайской теоремы об остатках. — Вестник ТГУ, 2009. — № 4. — ISSN 1810-0198.
  • Фергюсон, Нильс, Шнаер, Брюс Практическая криптография. — М.: Вильямс, 2004. — 432 с. — ISBN 5-8459-0733-0
  • Ян Сонг Й Криптоанализ RSA. — 2011. — 312 с. — ISBN 978-5-93972-873-7
  • Шенец Н. Н. Модульное разделение секрета и системы электронного голосования. — Вестник БГУ, 2011. — № 1.

Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]