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

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

Պատմություն

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

Ձևակերպում

Եթե $a_{1}, a_{2}, \dots, a_{n}$ բնական թվերը զույգ առ զույգ փոխադարձաբար պարզ են, ապա ցանկացած ամբողջ $r_{1}, r_{2}, \dots, r_{n}$ այնպիսին է, որ $0 ⩽ r_{i} < a_{i}$ բոլոր $i \in {1, 2, \dots, n}$ համար կգտնվի $N$ , որը $a_{i}$ վրա բաժանելիս տալիս է $r_{i}$ մնացորդ։ Ավելին, եթե գտնվեն այնպիսի երկու՝ $N_{1}$ և $N_{2}$ , ապա $N_{1} \equiv N_{2} (\mod a_{1} \cdot a_{2} \cdot \dots \cdot a_{n})$ ։

Ապացույցներ

Ինդդուկցիա հավասարումների քանակով

Օգտվենք մաթեմատիկական ինդուկցիայի մեթոդից։ $n = 1$ դեպքում թեորեմի պնդումը ակնհայտ է։ Թող թեորեմը ճշմարիտ լինի $n = k - 1$ դեպքում, ապա գոյություն ունի $m$ թիվը, որը $a_{i}$ $i \in {1, 2, \dots, k - 1}$ դեպքում թվի վրա բաժանելիս տալիս է $r_{i}$ մնացորդը։ Նշանակենք

d = a_{1} \cdot a_{2} \cdot \dots \cdot a_{k - 1}

։

Ընտրում ենք $a_{k}$ կամայական թիվը, որը փոխադաչձ պարզ է բոլոր $a_{1} \dots a_{k - 1}$ հետ և դիտարկենք $M = {m, m + d, m + 2 d, \dots, m + (a_{k} - 1) \cdot d} = {m + t \cdot d}_{0 ⩽ t < a_{k}}$ թվերը։Ցույց տանք, որ բոլոր $t \in {0, \dots, a_{k} - 1}$ հանդիսանում են մնացորդներ $M$ ֊ի ինչ֊որ էլեմենտների՝ $a_{k}$ վրա բաժանելիս։ Ենթադրենք, որ դա այդպես չէ, այսինքն գոյություն ունեն որոշակի $r_{k} < a_{k}$ , որոնք չեն պատկանում $M$ էլեմենտների՝ $a_{k}$ վրա բաժանելիս ստացված մնացորդների բազմությանը։Քանի որ այդ էլեմենտների թիվը հավասար է $| M | = a_{k}$ ,իսկ $M$ ֊ի ինչ֊որ էլեմենտների՝ $a_{k}$ վրա բաժանելիս հնարավոր մնացորդները հնարավոր է շատ չեն, քան $a_{k} - 1$ (քանի որ ոչ մի թիվ չի տալիս $r_{k}$ մնացորդ), ապա նրանց մեջ կգտնվեն երկու թիվ, որոնք ունեն հավասար մնացորդներ (Դիրիխլեի արկղի սկզբունք). Թող այդ թվերը լինեն $m + t_{1} d$ և $m + t_{2} d$ , $t_{1} \neq t_{2}$ դեպքում. Այդ դեպքում իրենց $(m + t_{1} d) - (m + t_{2} d) = (t_{1} - t_{2}) d$ տարբերությունը բաժանվում է $a_{k}$ վրա, ինչը հնարավոր է, քանի որ $t_{1} < a_{k}$ , $t_{2} < a_{k}$ , $0 < | t_{1} - t_{2} | < a_{k}$ և $d = a_{1} \cdot a_{2} \cdot \dots \cdot a_{k - 1}$ $a_{k}$ հետ փոխադարձ պարզ են, այլապես $a_{1}, a_{2}, \dots, a_{k}$ թվերը զույգ առ զույգ փոխադարձ պարզ են (ըստ պայմանի). Հակասություն։ Այսպիսով, դիտարկվող թվերի մեջ կգտնվի math>N = m + t\cdot d</math> թիվ, որը $a_{k}$ վրա բաժանելիս տալիս է $r_{k}$ մնացորդ. Միևնույն ժամանակ $a_{1}, a_{2}, \dots, a_{k - 1}$ վրա բաժանելիս $N$ թիվը համապատասխանաբար տալիս է $r_{1}, r_{2}, \dots, r_{k - 1}$ մնացորդ,քանի որ $m + t \cdot d \equiv m (\mod a_{i})$ ։ Այժմ ապացուցենք, որ $N_{1} \equiv N_{2} (\mod a_{1} \cdot a_{2} \cdot \dots \cdot a_{n})$ . Իրականում $N_{1} \equiv N_{2} \equiv r_{i} (\mod a_{i})$ , այսինքն $N_{1} - N_{2} \equiv 0 (\mod a_{i})$ . այսպիսով, $N_{1} - N_{2}$ թիվը բոլոր $a_{i}$ բաժանում է առանց մնացորդի, ինչպես նաև իրենց արտադրյալները։ Ինչն էլ պահանջվում էր ապացուցել։

Ապացույցի կոնստրուկտիվ մեթոդ

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

{\begin{matrix} x & \equiv r_{1} (\mod a_{1}) \\ x & \equiv r_{2} (\mod a_{2}) \\ ⋮ \\ x & \equiv r_{n} (\mod a_{n}) \end{matrix}

(1)

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

Եթե $(r_{1}, r_{2}, \dots, r_{n})$ և $(a_{1}, a_{2}, \dots, a_{n})$ բավարարում են թեորեմի պայմաններին, ապա (1)համակարգի լուծումը գոյություն ունի և $M$ մոդուլով ճշտությամբ միակն է, որտեղ $M = \prod_{i = 1}^{n} a_{i}$ , ընդ որում ճշմարիտ է բանաձևըԿաղապար:Sfn Կաղապար:Sfn Կաղապար:Sfn

$x = \sum_{i = 1}^{n} r_{i} M_{i} M_{i}^{- 1}$ , որտեղ $M_{i} = \frac{M}{a_{i}}$ , իսկ $M_{i}^{- 1}$ — հակադարձ մուլտիպլիկատիվ $M_{i} mod a_{i}$ $ℤ_{a_{i}}$ օղակի էլեմենտ է։

(2)

Ցույց տանք, որ այդ եղանակով որոշված $x$ ֊ը հանդիսանում է լուծում։ Ստուգենք, որ նրա համար համակարգումգործում է i-е հավասարությունըԿաղապար:Sfn։ $x \equiv \sum_{j = 1}^{n} r_{j} M_{j} M_{j}^{- 1} \equiv r_{i} M_{i} M_{i}^{- 1} \equiv r_{i} (\mod a_{i})$ Երկրորդ հավասարությունը ճշմարիտ է, քանի որ $M_{j} \equiv \prod_{k \neq j}^{n} a_{k} \equiv 0 (\mod a_{i})$ , բոլոր $i \neq j$ դեպքում, երրորդը, քանի որ $M_{i}^{- 1}$ հանդիսանում է հակադարձ $a_{i}$ մոդուլով $M_{i}$ համար։ Բոլոր $i$ համար կրկնելով դատողությունը, համոզվենք, որ (2) բանաձևով որոշված $x$ ֊ը հանդիսանում է լուծում (1) համար։

Բոլոր $x^{'} \equiv x (\mod M)$ թվերը, ընտրված $M$ թվի համաձայն,կբավարարեն համակարգին։ Այժմ ցույց տանք, որ $0, 1, \dots, M - 1$ (բազմություն $A$ ) թվերի մեջ մեր գտած լուծումից բացի ուրիշ լուծում չի գտնվի։ Այդ փաստի հակառակ ապացույցը։ Ենթադրենք, որ հաջողվել է մնացորդների որոշակի $r$ հավաքածուի համար գտնել գոնե երկու՝ $x_{1}, x_{2} \in A$ լուծում։ Քանի որ բոլոր թույլատրելի $(r_{1}, r_{2}, \dots, r_{n})$ հավաքածուների բազմությունը հանդիսանում է հավասարահզոր $A$ բազմությանը, ապա ${\overline{A}}_{x} : = A ∖ {x_{1}, x_{2}}$ և ${\overline{B}}_{r} : = B ∖ {r}$ համար գործում է $| {\overline{A}}_{x} | < | {\overline{B}}_{r} |$ ։ Սակայն, վերը ապացուցվածի համաձայն, ${\overline{B}}_{r}$ ֊ի ցանկացաց հավաքածուի համար գոյություն ունի ${\overline{A}}_{x}$ ֊ից լուծում, հետևաբար Դիրիխլեի սկզբունքի համաձայն կգտնվեն ամենաքիչը երկու մնացորդների հավաքածուներ, որոնց համապատասխանում է նույն $x \in A$ ֊ն։ Այդպիսի $x$ ֊ի համար կգտնվի այնպիսի $a_{i}$ , որ $x \equiv r_{1}, x \equiv r_{2} (\mod a_{i})$ և $r_{1} \neq r_{2}$ . ՀակասությունԿաղապար:Sfn. Ինչն էլ պահանջվում էր ապացուցել։

Դիտողություն

Վերը ապացուցվածից հետևում է, որ $(a_{1}, a_{2}, \dots, a_{n})$ ցանկացած հավաքածուի $B$ մնացորդների վեկտորի և $A$ բազմության թվի միջև գոյություն ունի միարժեք փոխադարձ համապատասխանություն, ինչը նշանակում է, որ (2) ֊ով տրված $B$ ֊ի արտապատկերումը $A$ մեջ հանդիսանում է բիեկտիվ Կաղապար:Sfn. Նկատենք, որ

$(x (\mod M)) \leftrightarrow (r_{1} (\mod a_{1}), r_{2} (\mod a_{2}), \dots, r_{n} (\mod a_{n}))$ ; համապատասխանությունից բացի

ճշմարիտ են նաև Կաղապար:Sfn Կաղապար:Sfn

$(x_{1} \pm x_{2} (\mod M)) \leftrightarrow (r_{11} \pm r_{21} (\mod a_{1}), r_{12} \pm r_{22} (\mod a_{2}), \dots, r_{1 n} \pm r_{2 n} (\mod a_{n}))$ ;

$(x_{1} x_{2} (\mod M)) \leftrightarrow (r_{11} r_{21} (\mod a_{1}), r_{12} r_{22} (\mod a_{2}), \dots, r_{1 n} r_{2 n} (\mod a_{n}))$ .

Մնացորդների վեկտորի անցումը թվի ժամանակավոր բարդությունը գնահատվում է $O (k^{2})$ , որտեղ k ֊ն վերականգնվող թիվն է բիթերոԿաղապար:Sfn։

Լուծումների որոշման ալգորիթմ

Բերենք ներքևում խնդիրների լուծման ալգորիթմ, որը դրվում է $x$ թվի, որոշակի տրված փոխադարձ պարզ $a_{1}, a_{2}, \dots, a_{n}$ թվերի բաժանումով իր մնացորդների հավաքածուով, վերականգնման թեորեմում։

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

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

{\begin{matrix} x \equiv 1 (\mod 2) \\ x \equiv 2 (\mod 3) \\ x \equiv 6 (\mod 7) \end{matrix}

համակարգը։

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

x_{1} \in {1, 3, 5, 7, 9, 11, \dots, 39, 𝟒 𝟏, 43, \dots}

x_{2} \in {2, 5, 8, 11, 14, \dots, 38, 𝟒 𝟏, 44, \dots}

x_{3} \in {6, 13, 20, 27, 34, 𝟒 𝟏, 48, \dots}

Ակնհայտ է, որ համակարգի լուծումների բազմությունը կլինի վերը ներկայացված բազմությունների հատումը։ Թեորեմի պնդման համաձայն լուծումը գոյություն ունի և միակն է մինչև 42 մոդուլի վերցնելը ճշտությամբ։ Մեր դեպքում $x \in {41, 83, 125, \dots}$ կամ $x \equiv 41 (\mod 42) .$

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

{\begin{matrix} x = 1 + 2 u \\ x = 2 + 3 v \\ x = 6 + 7 w \end{matrix}

x ֊ը առաջին հավասարումից երկրորդի մեջ տեղափոխելով կստանանք $1 + 2 u \equiv 2 (\mod 3)$ , այդ դեպքում $2 u \equiv 1 (\mod 3)$ , կամ $4 u \equiv 2 (\mod 3)$ , կամ $u \equiv 2 (\mod 3)$ , կամ $u = 2 + 3 s$ ;

հետո x ֊ը տեղափոխելով առաջին հավասարումից երրորդի մեջ $u$ տեսքի արտահայտության հաշվարկի համար, կստանանք $1 + 2 (2 + 3 s) \equiv 6 (\mod 7)$ կամ $6 s \equiv 1 (\mod 7)$ , $36 s \equiv 6 (\mod 7)$ և հետևաբար $s \equiv 6 (\mod 7)$ ;

այդ դեպքում $x = 1 + 2 (2 + 3 \cdot 6) = 41$ .

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

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

Քայլ 1. Հաշվում ենք $M = \prod_{i = 1}^{n} a_{i}$ ։

Քայլ 2. Բոլոր $i \in {1, 2, \dots, n}$ համար գտնում ենք $M_{i} = \frac{M}{a_{i}}$ ։

Քայլ 3. Գտնում ենք $M_{i}^{- 1} = \frac{1}{M_{i}} mod a_{i}$ (օրինակ, օգտագործելով Էվկլիդեսի ընդլայնված ալգորիթմ)։

Քայլ 4. Հաշվում ենք հիմնական արժեքը $x = \sum_{i = 1}^{n} r_{i} M_{i} M_{i}^{- 1} mod M$ բանաձևով։

Գեռների ալգորիթմ

Դիտարկենք մոդուլների $(a_{1}, a_{2}, \dots, a_{n})$ խումբը, բավարարող թեորեմի պայմաններին։ Թվերի տեսության մեկ այլ թեորեմով հիմնավորվում է,որ ցանկացած $0 ⩽ x < M = a_{1} \cdot a_{2} \cdot \dots \cdot a_{n}$ թիվ միանշանակ ներկայացնելի էԿաղապար:Sfn

$x = x_{1} + x_{2} \cdot a_{1} + x_{3} \cdot a_{1} \cdot a_{2} + \dots + x_{n} \cdot a_{1} \cdot a_{2} \cdot \dots \cdot a_{n - 1}$ տեսքով։

Հերթականությամբ հաշվելով բոլոր $x_{i}$ для $i \in {1, 2, \dots, n}$ գործակիցները, մենք կկարողանանք տեղադրել դրանք բանաձևում և գտնել հիմնական լուծումըԿաղապար:Sfn։

Նշանակենք $r_{i j} = a_{i}^{- 1} mod a_{j}$ և դիտարկենք $a_{i}$ մոդուլով արտահայտություն $x$ համար։

$x_{1} = r_{1}$ ;

$r_{2} = (x_{1} + x_{2} a_{1}) mod a_{2}$ ;

$x_{2} = (r_{2} - x_{1}) r_{12} mod a_{2}$ ;

$r_{3} = (x_{1} + x_{2} a_{1} + x_{3} a_{1} a_{2}) mod a_{3}$ ;

$x_{3} = ((r_{3} - x_{1}) r_{13} - x_{2}) r_{23} mod a_{3}$

և այլն։

$x_{i}$ գործակիցների որոնման ալգորիթմը ակնառուության համար կիրառենք կոդով, ենթադրությամբ, որ 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];
	}
}

Տրված ալգորիթմի համար $x_{i}$ գործակիցների որոշման բարդությունը $O (n^{2})$ է։ Բարդությունը նույնպիսին է նաև գտնված գործակիցներով իրական արժեքի վերականգման դեպքում։

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

Բանաձևայնացում օղակների համար

Թող $A, B_{1}, \dots, B_{n}$ —ն լինի միավորով կոմուտատիվ օղակներ, $φ_{i} : A \to B_{i}$ ֊ն՝ սյուրեկտիվ հոմոմորֆիզմներ, $\ker φ_{i} + \ker φ_{j} = A$ հատկանիշներով օժտված, բոլոր $i, j \in {1, \dots, n}, i \neq j$ համար։ Այդ դեպքում

Φ : A \to \prod_{i = 1}^{n} B_{i}

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

տրված

Φ (a) = (φ_{1} (a), \dots, φ_{n} (a))

բանաձևով,

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

A / (⋂_{i = 1}^{n} \ker φ_{i}) ≅ \prod_{i = 1}^{n} B_{i}

։

Եթե տեղադրել $A = ℤ / (a_{1} \cdot \dots \cdot a_{n} ℤ), B_{i} = ℤ / a_{i} ℤ (i = 1, 2, \dots, n; a_{i} \in ℤ)$ և հոմոմորֆիզմը որոշել հետևյալ կերպ․

φ_{i} (x) = x mod a_{i}

,

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

Այդպես հաճախ հանդիպում է օղակների էկվիվալենտ ձևակերպումը, որտեղ $B_{i}$ ունեն $A / I_{i}$ տեսքը, իդեալների որոշակի $I_{1}, \dots, I_{n}$ խմբի, $φ_{i}$ հոմոմորֆիզները հանդիսանում են իրական պրոյեկցիաներ $A / I_{i}$ վրաև պահանջվում է, որ $I_{i} + I_{j} = A$ ցանկացած $i, j \in {1, \dots, n}, i \neq j$ համար։ Ուրիշ բառերով, եթե $I_{1}, \dots, I_{n}$ իդեալները զույգ առ զույգ փոխադարձ պարզ են (այսինքն երկու իդեալների գումարը հավասար է հենց օղակին), ապա նրանց արտադրյալը համընկնում է իրենց հատման հետ և ֆակտոր օղակը այդ արտադրյալով իզոմորֆ է ֆակտորների արտադրյալին․

A / (I_{1} I_{2} \dots I_{n}) ≅ A / I_{1} \times A / I_{2} \times \dots \times A / I_{n}

։

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

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

$R /_{(m n)} ≅ R /_{(m)} \times R /_{(n)}$

 $[x]_{m n} ⟶ ([x]_{m}, [x]_{n})$  ուղիղ արտապատկերումն ակնհայտ է։

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

$([1]_{m}, [0]_{n}) ⟶ [u]_{m n}$

$([0]_{m}, [1]_{n}) ⟶ [v]_{m n}$

$[u]_{m n}$ կգտնենք լուծելով հավասարումների հետևյալ համակարգը․

${\begin{matrix} u \equiv 1 (\mod m) \\ u \equiv 0 (\mod n) \end{matrix}$

$\exists y \in ℤ : u = n y, n y \equiv 1 (\mod m)$

Անալոգ ձևով գտնենք $[v]_{m n}$ :

$\exists x \in ℤ : u = m x, m x \equiv 1 (\mod m)$

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

$([a]_{m}, [b]_{n}) ⟶ [a u + b v]_{m n}$

$a u + b v \equiv a (\mod m)$ , քանի որ $v \equiv 0 (\mod m)$ և $u \equiv 1 (\mod m)$

$a u + b v \equiv b (\mod n)$ , քանի որ $u \equiv 0 (\mod n)$ և $v \equiv 1 (\mod n)$

Ստուգենք արտապատկերման կոռեկտությունը, այսինքն, որ $[a]_{m}, [b]_{n}$ դասի տարբեր էլէմենտներ վերցնելու դեպքում արդյունքը չի փոխվում։

${\begin{matrix} a \equiv a^{'} (\mod m) \\ b \equiv b^{'} (\mod n) \end{matrix}$

Նշանակում է $a u + b v \equiv a^{'} u + b^{'} v (\mod m n)$ , արտապատկերումը կոռեկտ է։

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

Կիրառում

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

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

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

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

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

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

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

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

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

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

Կաղապար:Արտաքին հղումներ Կաղապար:Թվերի տեսություն

↑ Կաղապար:Cite web
↑ R. Tolimieri FFT Algorithms
↑ Otmar Venjakob p-adic Numbers and the Hasse Principle
↑ М. П. Минеев, В. Н. Чубариков об одном применении китайской теоремы об остатках к шифру Виженера Կաղապար:Չաշխատող արտաքին հղում (2010)

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

[2] R. Tolimieri FFT Algorithms

[3] Otmar Venjakob p-adic Numbers and the Hasse Principle

[4] М. П. Минеев, В. Н. Чубариков об одном применении китайской теоремы об остатках к шифру Виженера Կաղապար:Չաշխատող արտաքին հղում (2010)

[1]

[2]

[3]

[4]

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

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

Պատմություն

Ձևակերպում

Ապացույցներ

Ինդդուկցիա հավասարումների քանակով

Ապացույցի կոնստրուկտիվ մեթոդ

Դիտողություն

Լուծումների որոշման ալգորիթմ

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

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

Գեռների ալգորիթմ

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

Բանաձևայնացում օղակների համար

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

Կիրառում

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

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

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

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

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

Պատմություն

Ձևակերպում

Ապացույցներ

Ինդդուկցիա հավասարումների քանակով

Ապացույցի կոնստրուկտիվ մեթոդ

Դիտողություն

Լուծումների որոշման ալգորիթմ

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

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

Գեռների ալգորիթմ

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

Բանաձևայնացում օղակների համար

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

Կիրառում

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

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

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

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

Որոնում