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

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

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

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

Ապացույցներ

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

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

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

Ցույց տանք, որ այդ եղանակով որոշված  ֊ը հանդիսանում է լուծում։ Ստուգենք, որ նրա համար համակարգումգործում է i-е հավասարությունը։

Երկրորդ հավասարությունը ճշմարիտ է, քանի որ  , բոլոր  դեպքում, երրորդը, քանի որ  հանդիսանում է հակադարձ  մոդուլով  համար։ Բոլոր  համար կրկնելով դատողությունը, համոզվենք, որ (2) բանաձևով որոշված  ֊ը հանդիսանում է լուծում (1) համար։

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

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

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

ճշմարիտ են նաև 

;

.

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

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

Էլեմենտար հանրահաշիվ 

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

համակարգը։

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

 
 
 

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

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

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

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

այդ դեպքում .

Մնացորդների մասին չինական թեորեմի հիմքի վրա ալգորիթմ 

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

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

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

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

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

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

 տեսքով։

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

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

;

;

;

;

և այլն։

 գործակիցների որոնման ալգորիթմը ակնառուության համար կիրառենք կոդով, ենթադրությամբ, որ 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];
	}
}
Տրված ալգորիթմի համար  գործակիցների որոշման բարդությունը  է։ Բարդությունը նույնպիսին է նաև գտնված գործակիցներով իրական արժեքի վերականգման դեպքում։

Վարիացիաներ և ընդհանրացումներ

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

Եթե տեղադրել  և հոմոմորֆիզմը որոշել հետևյալ կերպ․ 
 ,
ապա մենք կստանանք թեորեմի թվաբանական տարբերակը։

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

Ապացույց էվկլիդյան օղակների համար 

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

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

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

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

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

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

, քանի որ  և 

, քանի որ  և 

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

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

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

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

 Օրինակ, RSA ալգորիթմում հաշվումը կատարվում է n շատ մեծ թվի մոդուլով, ներկայացված երկու մեծ պարզ թվերի արտադրյալի տեսքով։ Թեորեմը թույլ է տալիս անցում կատարել այդ պարզ բաժանարարների մոդուլով հաշվմանը, որոնք մեծությամբ արդեն n արմատների կարգի են, նշանակում է ունեն երկու անգամ փոքր բիթային երկարություն։

 Նշենք նաև, որ հաշվարկների օգտագործումը, համաձայն մնացորդների մասին չինական թեորեմի, RSA ալգորիթմը ժամանակային հարձակումները դարձնում է ընկալելի։.

 Թեորեմում հիմնավորված են Ասմուտ — բլումի սխեմա և Մինյոտտայի սխեմա — մասնակիցների խմբում գաղտնիքի բաժանարարի մուտքային սխեմաները։ Գաղտիքը կարող են իմանալ n մասնակիցներից միայն k ֊ն, միավորելով իրենց բանալիները.
 Կիրառումներից մեկը հանդիսանում է պարզ թվերի հիման վրա Ֆուրյեի արագ փոխակերպումը։
 Թեորեմն ընկած է հավասարման ամբողջաթվային արմատների որոնման Խասսեի սկզբունքի հիմքում.
 Թեորեմից հետևում է Էյլերի ֆունկցիայի մուլտիպլիկատիվությունը։ 
 Թեորեմում հիմնավորվում է հատուկ տեսք ունեցող թվերի համար պոլիմինալ ժամանակից դիսկրետ ալգորիթմի որոնումը՝ Պոլիգ — Խելլմանի ալգորիթմ։
 Թեորեմը բազմակի կիրառում ունի գաղտնագրման համակարգերում վերծանման և ապավերծանման մեջ, օրինակ, Ռաբինի կրիպտոհամակարգում կամ Վիժեների ծածկագրման մեջ։

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

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

Արտաքին հղումներ 
 Шенец Н. Н. Модульное разделение секрета и системы электронного голосования (2011)
 Ишухаметов Ш. Т. Методы факторизации натуральных чисел(2011)
 Нестеренко А. Введение в современную криптографию Теоретико-числовые алгоритмы (2011)
 Минеев М. П., Чубариков В. Н. Об одном применении китайской теоремы об остатках к шифру Виженера (2010)

Թվերի տեսության մասին թեորեմներ
Կոմուտատիվ հանրահաշիվ
Հանրահաշվի թեորեմներ