Մոդուլար հանրահաշիվ

Այս հոդվածը

(mod\ n)

գրառման մասին է․

mod(a,n)

գործողության համար տես՝ մոդուլո գործողություն։

Մաթեմատիկայում մոդուլար հանրահաշիվը ամբողջ թվերի բազմության հանրահաշվական համակարգ է։ Մոդուլար հանրահաշվում թվերը, որոշակի արժեքի՝ մոդուլուսի հասնելուց հետո, «պտտվում են» սկզբնակետի շուրջ։ Մոդուլար հանրահաշվի ժամանակակից մոտեցումը մշակել է Կառլ Գաուսն իր 1801 թվականին հրատարակված «Disquisitiones Arithmeticae» գրքում։

Մոդուլար հանրահաշվի ամենօրյա օգտագործման օրինակ է 12-ժամանոց ժամացույցը։ Ժամացույցում օրը բաժանված է երկու 12-ժամյա հատվածների։ Եթե հիմա ժամը 07:00 է, 8 ժամ անց կլինի ժամը 03:00։ Սովորական գումարումը՝ $7+8=15$ կհանգի 15:00-ի, բայց այն կարելի կարդալ որպես 03:00, քանի որ ժամացույցը 12 ժամը մեկ վերսկսում է, և ժամը ներկայացնող թվերը սկսում են զրոյից երբ ժամը հասնում է 12֊ին։ Սա նկարագրում ենք որպես «15-ը կոնգրուենտ է 3֊ին մոդուլո 12, և գրանցում որպես $15\cong 3(mod\ 12)$ ։ Այսպիսով. $7+8\cong 3(mod\ 12)$ ։ Նույն տրամաբանությամբ 8:00 ներկայացնում է 8-ժամյա ժամանակահտված, որի կրկնակին կլինի 16:00: 16:00-ն ժամացույցի վրա ընթերցում ենք որպես 4:00։ Նշանակում է․ $2\times 8\cong 4(mod\ 12)$ ։

Կոնգրուենցիա

Եթե տրված է $n>1$ ամբողջ թիվ, ապա $a$ և $b$ ամբողջ թվերը կոչվում են «մոդուլո $n$ կոնգրուենտ» եթե $n$ -ը դրանց տարբերության բաժանարարն է։ Ասել է թե․ գոյություն ունի այնպիսի $k\in \mathbb {Z}$ որի համար կարող ենք գրել․

a-b=kn

Մոդուլո $n$ կոնգրուենցիան գրանցվում է որպես․

a\cong b(mod\ n)

Փակագծերը նշանակում են, որ $(mod\ n)$ -ը վերաբերում է ամբողջ հավասարմանը, ո՛չ միայն աջ կողմին (օրինակում աջ կողմը $b$ -ն է)։

Այս գրառումը պետք չէ շփոթել $b\ mod\ n$ (առանց փակագծերի) գրանցման հետ, որը վերաբերում է մոդուլո գործողությանը ( $b$ -ն $n$ -ի բաժանման մնացորդին)։ $b\ mod\ n$ -ը արտահայտում է այն եզակի $r$ ամբողջ թիվը, որի համար ճիշտ են $0\leq r<n$ և $r\cong b(modn)$ պնդումները։

Կոնգրուենտ հարաբերությունը կարելի է ներկայացնել որպես.

a=kn+b

,

բացահայտ ցուցադրելով Էվկլիդեսյան բաժանման հետ զուգահեռները։ Մեզ անհրաժեշտ չէ, որպեսզի $b$ -ն լինի $n$ -ով $a$ -ի բաժանման մնացորդը։ Փոխարենը, $a\cong b(mod\ n)$ պնդում է, որ $n$ -ով բաժանելիս $a$ -ն ու $b$ -ն նույն մնացորդն ունեն․

a=pn+r

b=qn+r

,

որտեղ $0\leq r<n$ -ը ընդհանուր մնացորդն է։ Երկու հավասարումներն իրարից հանելուվ կարող են վերականգնել սկզբնական հարաբերությունը․ $a-b=kn$ , որտեղ $k=p-1$ ։

Մոդուլո $n$ կոնգրուենցիան կոնգրուենտ հարաբերություն է․ կոնգրուենցիան էկվիվալենտ հարաբերություն է և համադրելի է գումարման, հանման ու բազմապատկման գործողությունների հետ։

Օրինակներ

Մոդուլուս 12 համակարգում կարող ենք պնդել, որ $38\cong 14(mod\ 12)$ , քանի որ $38-14$ տարբերությունը հավասար է $24=2\times 12$ . $12$ -ի բազմապատիկ է։ Համապատասխանաբար, $12$ -ով բաժանելիս $38$ -ն ու $14$ -ը նույն մնացորդն ունեն։

Կոնգրուենցիայի սահմանումն աշխատում է նաև բացասական արժեքների համար։ Օրինակ․

{\begin{aligned}2\cong -3{\pmod {5}}\\-8\cong 7{\pmod {5}}\\-3\cong -8{\pmod {5}}\end{aligned}}

Հատկություններ

Հիմնարար հատկություններ

Կոնգրուենտ հարաբերությունը պետք է բավարարի էկվիվալենտ հարաբերության բոլոր պայմանները․

Ռեֆլեքսիվություն․ $a\cong a(mod\ n)$
Համաչափություն $a\cong b(mod\ n)$ եթե $b\cong a(mod\ n)$
Անցողականություն․ եթե $a\cong b(mod\ n)$ և $b\cong c(mod\ n)$ , ապա $a\cong c(mod\ b)$

Եթե $a_{1}\cong b_{1}(mod\ n)$ և $a_{2}\cong b_{2}(mod\ n)$ , կամ եթե $a\cong b(mod\ n)$ , ապա^[1].

$a+k\cong b+k(mod\ n)$ , ցանկացած $k\in \mathbb {Z}$ -ի համար (տռանսլյացիայի հետ համադրելիություն)
$ka\cong kb(mod\ n)$ ցանկացած $k\in \mathbb {Z}$ -ի համար (մասշտաբի հետ համադրելիություն)
$ka\cong kb(mod\ kn)$ ցանկացած $k\neq 0\in \mathbb {Z}$ -ի համար
$a_{1}+a_{2}\cong b_{1}+b_{2}(mod\ n)$ (գումարման հետ համադրելիություն)
$a_{1}-a_{2}\cong b_{1}-b_{2}(mod\ n)$ (հանման հետ համադրելիություն)
$a_{1}\times a_{2}\cong b_{1}\times b_{2}(mod\ n)$ (բազմապատկման հետ համադրելիություն)
$a^{k}\cong b^{k}(mod\ n)$ ցանկացած ոչ-բացասական $k\in \mathbb {Z}$ -ի համար (ցուցիչի հետ համադրելիություն)
$p(a)=p(b)\ (mod\ n)$ ցանկացած ամբողջ թվերով գործակիցներով $p(k)$ բազմանդամի համար (համադրելիություն բազմանդամի գնահատման հետ)։

Եթե $a\cong b(mod\ n)$ , $k^{a}\cong k^{b}(mod\ n)$ պնդումն ընդհանուր դեպքի համար ճիշտ չէ։ Սակայն հետևյալ պնդումը ճիշտ է․

եթե $c\cong d(mod\ \phi (n))$ , որտեղ $\phi$ -ն Էյլերի ֆունկցիան է, ապա $a^{c}\cong a^{d}(mod\ n)$ ` ենթադրելով, որ $a$ -ն փոխադարձ պարզ է $n$ -ին։

Ընդհանուր անդամների չեղարկման համար ունենք հետևյալ կանոնները․

եթե $a+k\cong b+k(mod\ b)$ , որտեղ $k$ -ը կամայական ամբողջ թիվ է, ապա $a\cong b(mod\ n)$
եթե $ka\cong kb(mod\ n)$ և $k$ -ը փոխադարձ պարզ է $n$ -ին, ապա $a\cong b(mod\ n)$
եթե $ka\cong kb(mod\ kn)$ և $k\neq 0$ , ապա $a\cong b(mod\ n)$ ։

Վերջին կանոնը կարելի է օգտագործել մոդուլար հանրահաշիվը բաժանման տիրույթ տեղափոխելու համար։ Եթե $b$ -ն բաժանում է $a$ ֊ն, ապա $(a/b)\ mod\ n=(a\ mod\ bn)/b$ ։

Մոդուլար բազմապատիկ հակադարձը սահմանվում է հետևյալ կանոններով․

Գոյություն․ $a^{-1}$ գրառմամբ նշանակվող ամբողջ թիվը, որի համար ճիշտ է $aa^{-1}\cong 1(mod\ n)$ պնդումը, գոյություն ունի միայն և միայն այն դեպքում, եթե $a$ -ը փոխադարձ պարզ է $n$ -ին։ Այդ $a^{-1}$ ամբողջ թիվը կոչվում է $a$ -ի մոդուլո $n$ մոդուլար բազապատիկ հակադարձ։
Եթե $a\cong b(mod\ n)$ և $a^{-1}$ -ը գոյություն ունի, ապա $a^{-1}=b^{-1}(mod\ n)$ (համադրելիություն բազմապատիկ հակադարձի հետ, և, եթե $a=b$ , մոդուլո $n$ եզակիություն)։
Եթե $ax\cong b(mod\ n)$ և $a$ -ն փոխադարձ պարզ է $n$ -ին, ապա այս գծային կոնգրուենցիայի լուծումը տրված է $x\cong a^{-1}b(mod\ n)$ հավասարմամբ։

$x\cong a^{-1}(mod\ n)$ բազմապատիկ համադարձը գտնելու արդյունավետ տարբերակ է Բեզուի հավասարումը՝ $ax+ny=1$ , $x$ -ի և $y$ -ի համար լուծելը։ Այն կարելի է լուծել Էվկլիդեսի ընդարձակված ալգորիթմով։

Մասնավորապես․ եթե $p$ -ն պարզ թիվ է, ապա $a$ -ն $p$ -ի հետ փոխադարձ պարզ է ցանկացած $0<a<p$ -ի համար։ Այսպիսով բազապատիկ հակադարձ գոյություն ունի բոլոր այն $a$ -երի համար, որոնք $p$ մոդուլոյով զրոյին կոնգրուենտ չեն։

Այլ հատկություններ

Ստորև ներկայացված են կոնգրուենտ հարաբերության այլ հատկություններ․

Ֆերմայի փոքրիկ թեորեմը․ եթե $p$ -ն պարզ թիվ է և չի բաժանում $a$ -ին, ապա $a^{p-1}\cong 1(mod\ p)$
Էյլերի թեորեմը․ եթե $a$ $a$ -ն և $n$ $n$ -ը փոխադարձ պարզ են, ապա $a^{\phi (n)}\cong 1(mod\ n)$ $a^{\phi (n)}\cong 1(mod\ n)$ , որտեղ $\phi$ $\phi$ -ն Էյլերի ֆունկցիան է։
- Ֆերմայի փոքրիկ թեորեմի հետևանքներից է, որ, եթե $p$ $p$ -ն պարզ թիվ է, ապա $a^{-1}\cong a^{p-2}(mod\ p)$ $a^{-1}\cong a^{p-2}(mod\ p)$ -ն $0<a<p$ $0<a<p$ թվի բազմապատիկ հակադարձն է։
  - Ավելի ընդհանուր՝ Էյլերի թեորեմից, եթե $a$ -ն և $n$ -ը փոխադարձ պարզ թվեր են, ապա $a^{-1}\cong a^{\phi (n)-1}(mod\ n)$ ։
- Մեկ այլ պարզ հետևանք է, որ, եթե $a\cong b(mod\ \phi (n))$ , որտեղ $\phi$ -ն Էյլերի ֆունկցիան է, և $k$ -ը փոխադարձ պարզ է $n$ -ին, ապա $k^{a}\cong k^{b}(mod\ n)$
Ուիլսոնի թեորեմը. $p$ -ն պարզ թիվ է միայն և միայն եթե $(p-1)!\cong -1(mod\ p)$ ։
Մնացորդների մասին չինական թեորեմը. ցանկացած $a$ $a$ , $b$ $b$ և փոխադարձ պարզ $m$ $m$ , $n$ $n$ թվերի համար գոյություն ունի այնպիսի եզակի $x(mod\ mn)$ $x(mod\ mn)$ , որի համար ճիշտ են $x\cong a(mod\ m)$ $x\cong a(mod\ m)$ և $x\cong b(mod\ n)$ $x\cong b(mod\ n)$ պնդումները։
- Ավելին․ $x\cong bm_{n}^{-1}m+an_{m}^{-1}n(mod\ mn)$ , որտեղ $m_{n}^{-1}$ -ը $m$ -ի մոդուլո $n$ -ի հակադարձն է, իսկ $n_{m}^{-1}$ -ը՝ $n$ -ի մոդուլո $m$ -ի։
Լագրանժի թեորեմը․ $f(x)\cong 0(mod\ p)$ կոնգրուենցիան, որտեղ $p$ -ն պարզ թիվ է և $f(x)=a_{0}x^{n}+\dots +a_{n}$ -ն ամբողջ թվերի գործակիցներով բազմանդամ է որտեղ $a_{0}\neq 0(mod\ p)$ , առավելագույնն $n$ արմատ ունի։
Մոդուլո $n$ պարզունակ արմատ. $g$ $g$ թիվը մոդուլո $n$ $n$ պարզունակ արմատ է, եթե $n$ $n$ -ին փոխադարձ պարզ յուրաքանչյուր $a$ $a$ ամբողջ թվի համար գոյություն ունի այնպիսի $k$ $k$ ամբողջ թիվ, որի համար ճիշտ է $g^{k}\cong a(mod\ n)$ $g^{k}\cong a(mod\ n)$ հավասարումը։
- Մոդուլո $n$ պարզունակ արմատ գոյություն ունի միայն ու միայն եթե $n$ -ը հավասար է $2$ -ի, $4$ -ի, $p^{k}$ -ի կամ $2p^{k}$ -ի, որտեղ $p$ -ն կենտ պարզ թիվ է և $k$ -ը դրական ամբողջ թիվ է։
- Եթե մոդուլո $n$ պարզունակ արմատ գոյություն ունի, ապա գոյություն ունեն ճիշտ $\phi (\phi (n))$ նման պարզունակ արմատներ, որտեղ $\phi$ -ն Էյլերի ֆունկցիան է։
Քառակուսային մնացորդ․ $a$ $a$ ամբողջ թիվը մոդուլո $n$ $n$ քառակուսային մնացորդ է, եթե գոյություն ունի այնպիսի $x$ $x$ ամբողջ թիվ, որի համար ճիշտ է $x^{2}\cong a(mod\ n)$ $x^{2}\cong a(mod\ n)$ հավասարումը։
- Էյլերի չափանիշը փաստում է, որ, եթե $p$ -ն կենտ պարզ թիվ է և $a$ -ն $p$ -ի բազմապատիկը չէ, ապա $a$ -ն մոդուլո $p$ քառակուսային մնացորդ է միայն ու միայն եթե $a^{(p-1)/2}\cong 1(mod\ p)$

Մնացորդային համակարգեր

Յուրաքանչյուն մոդուլո $n$ մնացորդային դասակարգ կարելի է ներկայացնել իր կամայական անդամով։ Սովորաբար այն ներկայացնում ենք այն փոքրագույն ոչ-բացասական ամբողջ թվով, որը դասակարգի անդամ է^[2] (սա կլինի բաժանման արդյունքում ստացված մնացորդը)։ Տարբեր դասակարգերի կամայական անդամներ իրար մոդուլո $n$ ինկոնգրուենտ են։ Ավելին․ յուրաքանչյուր ամբողջ թիվ պատկանում է միայն մի մոդուլո $n$ մնացորդային դասակարգի^[3]։

Ամբողջ թվերի $\{0,1,2\dots n-1\}$ բազմությունը կոչվում է մոդուլո $n$ նվազագույն մնացորդների համակարգ։ $n$ ամբողջ թվերի կամայական բազմություն, որում կամայական երկու անդամ իրար մոդուլո $n$ կոնգրուենտ չեն կոչվում է մոդուլո $n$ մնացորդների ամբողջ համակարգ։

Նվազագույն մնացորդների համակարգը մնացորդների ամբողջ համակարգ է, և մնացորդների ամբողջ համակարգը պարզապես մոդուլո $n$ մնացորդային յուրաքանչյուր դասակարգից մեկ ներկայացուցիչ պարունակող բազմություն է^[4]։

Օրինակ մոդուլո $4$ նվազագույն մնացորդների համակարգը $\{0,1,2,3\}$ բազմությունն է։ Այլ մնացորդների ամբողջ համակարգերից են․ $\{1,2,3,4\}$ , $\{13,14,15,16\}$ , $\{-2,-1,0,1\}$ , $\{-5,0,6,21\}$ կամ $\{27,32,37,42\}$

Մոդուլո $4$ մնացորդների ամբողջ համակարգ չհանդիսացող բազմության օրինակներ են․ $\{-5,0,6,22\}$ , քանի որ $6$ -ը $22$ -ին մոդուլո $4$ կոնգրուենտ է, կամ $\{5,15\}$ , քանի որ մոդուլո $4$ մնացորդների ամբողջ համակարգը պետք է $4$ ոչ֊կոնգրուենտ անդամ ունենա։

Նվազեցրած մնացորդերի համակարգեր

Տրված ունենալով Էյլերի ֆունկցիա $\phi (n)$ -ը, $\phi (n)$ ամբողջ թվերի կամայական բազմություն, որի անդամները փոխադարձ պարզ են $n$ -ին և իրար մոդուլո $n$ ինկոնգրուենտ են, կոչվում է մոդուլո $n$ նվազեցրած մնացորդերի համակարգ^[5]։ Վերին օրինակի $\{5,15\}$ բազմությունը նվազեցրած մնացորդների համակարգի օրինակ է։

Մոդուլո m ամբողջ թվեր

Նշում․ այս պարբերությունների կոնտեքստում $m$ մոդուլուսը գրեթե միշտ որպես դրական է վերցված։

Մոդուլո $m$ բոլոր կոնգրուենտ դասակարգերի բազմությունը կոչվում է մոդուլո $m$ ամբողջ թվերի օղակ^[6], և նշանակվում է որպես ${\textstyle \mathbb {Z} /m\mathbb {Z} }$ , $\mathbb {Z} /m$ կամ $\mathbb {Z} _{m}$ ^[7]։ $\mathbb {Z} _{m}$ գրառումը, սակայն, խորհուրդ չի տրվում, քանի որ այն կարելի է շփոթել $m$ -ադիկ ամբողջ թվերի բազմության հետ։ $\mathbb {Z} /m\mathbb {Z}$ օղակը մաթեմատիկայի տարբեր ճյուղերի հիմքում է։

Տրված ունենալով $m>0$ , ունենք

\mathbb {Z} /m\mathbb {Z} =\left\{{\overline {a}}_{m}\mid a\in \mathbb {Z} \right\}=\left\{{\overline {0}}_{m},{\overline {1}}_{m},{\overline {2}}_{m},\ldots ,{\overline {m{-}1}}_{m}\right\}

։

Երբ $m=1$ , $\mathbb {Z} /m\mathbb {Z}$ ֊ն զրո օղակն է։ Երբ $m=0$ , $\mathbb {Z} /m\mathbb {Z}$ ֊ն դատարկ բազմությունը չէ․ այն փոխարենն իզոմորֆիկ է $\mathbb {Z}$ -ին, քանի որ ${\overline {a_{0}}}=\{a\}$ ։

$\mathbb {Z} /m\mathbb {Z}$ օղակում գումարումը, հանումը և բաժանումը տրված են հետևյալ կանոններով․

${\overline {a}}_{m}+{\overline {b}}_{m}={\overline {(a+b)}}_{m}$
${\overline {a}}_{m}-{\overline {b}}_{m}={\overline {(a-b)}}_{m}$
${\overline {a}}_{m}{\overline {b}}_{m}={\overline {(ab)}}_{m}$ ։

Վերում նշված հատկություններից կարող ենք եզրակացնել, որ այս գործողությունների ներքո $\mathbb {Z} /m\mathbb {Z}$ -ն տեղափոխական (կոմուտատիվ) օղակ է։ Օրինակ $\mathbb {Z} /24\mathbb {Z}$ օղակում ունենք․

{\overline {12}}_{24}+{\overline {21}}_{24}={\overline {33}}_{24}={\overline {9}}_{24}

,

ինչև համարժեք է 24-ժամյա ժամացույցի հանրահաշվին։

$\mathbb {Z} /m\mathbb {Z}$ գրառումն օգտագործում ենք, քանի որ այս օղակը $\mathbb {Z}$ բազմության քանորդ օղակն է՝ $m\mathbb {Z}$ իդեալով. բոլոր $k\ m$ -ով (որտեղ $k\in \mathbb {Z}$ ) ձևավորված բազմությամբ։

Գումարման տակ խումբ համարվելով՝ $\mathbb {Z} /m\mathbb {Z}$ -ն ցիկլիկ խումբ է։ Բոլոր ցիկլիկ խմբերն ինչ֊որ $m$ ֊ի համար $\mathbb {Z} /m\mathbb {Z}$ -ին իզոմորֆիկ են^[8]։

Մոդուլո $m$ ամբողջ թվերի օղակը դաշտ է միայն և միայն այն դեպքում, եթե $m$ -ը պարզ թիվ է․ սա երաշխավորում է, որ յուրաքանչյուր ոչ-զրոյական անդամ բազմապատիկ հակադարձ ունի։ Եթե $m$ -ը հավասար է $p^{k}$ -ին որևէ $k>1$ -ի համար, (եթե այն պարզ թվի աստիճան է), ապա գոյություն ունի իզոմորֆությամբ եզակի $\mathrm {GF} (m)=\mathbb {F} _{m}$ դաշտ` $m$ անդամներով, որը իզոմորֆիկ չէ $\mathbb {Z} /m\mathbb {Z}$ -ին։ Այն դաշտ չէ, քանի որ ունի զրոյական բաժանարարներ։

Եթե $m>1$ , ապա $(\mathbb {Z} /m\mathbb {Z} )^{\times }$ արտահայտությամբ գրառում ենք մոդուլո $m$ հակադարձ ունեցող ամբողջ թվերի բազմապատիկ խումբը։ Այն բաղկացած է $a m$ կոնգրուենտ դասակարգերից, որտեղ $a$ -ն փոխադարձաբար պարզ է $m$ -ին; սրանք հենց այն դասակարգեր են, որոնք բազմապատիկ հակադարձ ունեն։ Նրանք բազմապատկման ներքո աբելյան խումբ են կազմում; կարգը $\phi (m)$ է, որտեղ $\phi$ -ն Էյլերի ֆունկցիան է։

Կիրառումներ

Մաքուր մաթեմատիկայում մոդուլար հանրահաշիվը թվերի տեսության հիմունքներից է, և կիրառվում է թվերի տեսության ուսումնասիրման գրեթե բոլոր ոլորտներում։ Մուդուլար հանրահաշիվը նաև լայն կիրառում ունի խմբերի տեսության, օղակների տեսության, կապերի տեսության մեջ և աբստրակտ հանրահաշվում։

Կիրառական մաթեմատիկայում մոդուլար հանարահաշիվը կիրառություն ունի համակարգչային հանրահաշվում, կրիպտոգրաֆիայում, ինֆորմատիկայում, քիմիայում, կերպարվեստում և երաժշտության մեջ։

Մոդուլար հանրահաշվի շատ պրակտիկ կիրառումներից է թվային սերիալ նույնականացման ցուցիչների ստուգիչ գումարի հաշվարկը։ Օրինակ գրքի միջազգային ստանդարտ համարի (ԳՄԱՀ) համակարգը սխալների բացահայտման համար oգտագործում է մոդուլո 11 (10-նշային ԳՄԱՀ-ի համար) կամ մոդուլո 10 (13-նշային ԳՄԱՀ-ի համար) հանրահաշիվ։ Նմանապես, միջազգային բանկային հաշվեհամարների համակարգը մոդուլո 97 հանրահաշիվ է օգտագործում հաշվեհամարի մուտքագրման սխալները նկատելու համար։ Քիմիայում CAS գրանցման համարի վերջին նիշը ստուգիչ նիշ է, որը հաշվում են մոդուլո 10 հանրահաշվով․ այն հավասար է գրանցման համարի առաջին երկու մասի վերջին նշի ու 1-ի արտադրայլի, նախորդ նշի ու 2-ի, դրա նախորդ նշի ու 3-ի, և այլն, գումարին մոդուլո 10։

Գաղտնագրության մեջ մոդուլար հանրահաշիվը հանրային բանալիների գաղտնագրության համակարգերի (ինչպիսիք են, օրինակ, RSA ալգորիթմն ու Դիֆֆի֊Հելմանի բանալու փոխանակման արձանագրությունը) հիմնաքարն է։ RSA ալգորիթմն ու Դիֆֆի֊Հելմանի բանալու փոխանակման արձանագրությունն օգտագործում են մոդուլար աստիճան (էքսպոնենտ)։ Մոդուլար հանրահաշիվը նաև առաջարկում է վերջավոր դաշտեր, որոնցով կարելի է էլիպտիկ կորեր կառուցել և օգտագործել համաչափ բանալու տարատեսակ ալգորիթմներում, ներառյալ՝ Ծածկագրման Առաջադեմ Ստանդարտ(AES), Տվյալների Ծածկագրման Միջազգային Ալգորիթմը (IDEA) և RC4։

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

1980-ականներին «FidoNet»-ում հրապարակվել է (հետագայում՝ արխիվացվել «Rosetta Code»-ում) Էյլերի աստիճանների գումարի վարկածի հերքում՝ օգտագործելով մոդուլար հանրահաշիվը։ Հերքումն աշխատել է Sinclair QL միկրոհամակարգչում, համեմատած CDC 6600 գերհամակարգչի՝ որը երկու տասնամյակ առաջ հերքել էր վարկածը կոպիտ ուժի փնտրտուքով, ամբողջ թվի ճշգրտության միայն մեկ չորրորդն օգտագորելով^[9]։

Համակարգչային գիտության մեջ մոդուլար հանրահաշիվը հաճախ է օգտագործվում բիթային, ինչպես նաև այլ ֆիքսված լայնության կամ ցիկլիկ տվյալների կառույցներ ներառող գործողություններում։ Մոդուլո գործողությունը, որը բազմաթիվ ծրագրավորման լեզուներում ու հաշվիչներում արդեն ներդրված է, մոդուլար հանրահաշվի կիրառումներից է, հաճախ է օգտագործվում այս ենթատեքստում։ Օրինակ․ տրամաբանական XOR գործողությունը մոդուլո 2-ում երկու բիթ է գումարում։

Կամայական $b$ հիմքում կոտորակը կրկնվող տասնորդականի փոխարկելու համար սյունակով բաժանման օգտագործումը համարժեք է հայտարարը մոդուլո $b$ մոդուլար բազմապատկման։ Օրինակ, տասական համակարգում $b=10$ ։

Երաժշտության մեջ $modulo\ 12$ հանրահաշիվն օգտագործվում է տասներկու տոնով հավասար խառնվածքի համակարգի դիտարկումներում։ Նման համակարգում կարելի է նկատել օկտավաներ և էնհարմոնիկ հավասարություն․ ասել է թե 1:2 կամ 2:1 կամ համարժեք երաժշտական բարձրությունների հարաբերություն, որտեղ C-դիեզը համարվում է D-բեմոլին նույնական։

Իների հեռացման մեթոդը ձեռքով արված տասնորդական թվաբանական գործողություններն արագ ստուգելու հնարավորություն է տալիս։ Այն հիմնված է $modulo\ 9$ հանրահաշվի, մասնավորապես՝ $10\cong 1(mod\ 9)$ փաստի վրա։

$modulo\ 7$ հանրահաշիվն օգտագործվում է տրված օրվա համար շաբաթվա օրը հաշվող ալգորիթմներում Մասնավորապես՝ Ցելլերի կոնգրուենցիան ու Դատաստանի օրվա ալգորիթմը հիմնված են $modulo\ 7$ հանրահաշվի վրա։

Ավելի ընդհանրացված՝ մոդուլար հանրահաշիվը կիրառումներ ունի նաև իրավունքի, տնտեսագիտության (օրինակ՝ խաղերի տեսության) ու հասարակական գիտությունների այն ոլորտներում, որտեղ ռեսուրսների համաչափ բաժանման ու տեղակայման խնդիրը վերլուծություններում կենտրոնական դեր է ստանձնում։

Հաշվողական բարդություն

Քանի որ մոդուլար հանրահաշիվը կիրառումների լայն շրջանակ ունի, կարևոր է իմանալ կոնգրուենցիաների համակարգի լուծման բարդությունը։ Կոնգրուենցիաների գծային համակարգը կարելի է լուծել բազմանդամային ժամանակում Գաուսի մեթոդի տարատեսակ օգտագործելով (մանրամասների համար տես գծային կոնգրուենցիաների թեորեմ)։ Մեծ թվերի համար պարզ հանրահաշվական գործողությունների (օրինակ՝ բազմապատկման կամ մոդուլար աստիճանի) հաշվարկը արդյունավետ կերպով իրականացնող ալգորիթմներ գոյություն ունեն․ օրինակ՝ Մոնտգոմերիի կրճատումը։

Որոշ գործողություններ, ինչպիսիք են օրինակ, դիսկրետ լոգարիթմի հաշվարկը կամ քառակուսային կոնգրուենցիան, կարծես թե ամբողջ թվերի ֆակտորիզացիայի խնդրին հավասար բարդություն ունեն։ Ըստ այդմ, դրանք կարելի է օգտագործել գաղտնագրային ալգորիթմների համար։ Ամբողջ թվերի ֆակտորիզացիայի խնդիրը, հնարավոր է, NP-միջանկյալ բարդություն ունի։

Մոդուլար հանրահաշվի ոչ-գծային հավասարումների համակարգի լուծումը NP-ամբողջական բարդություն ունի^[10]։

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

↑ Սանդոր Լեհոսկի; Ռիչարդ Ռուսկի (2006). Դեյվիդ Պատրիկ (ed.). Խնդիրներ լուծելու արվեստը (անգլերեն). Vol. 1 (7 ed.). AoPS Incorporated. էջ 44. ISBN 0977304566.
↑ Վեյսշտայն, Էրիկ. «Մոդուլար հանրահաշիվ». mathworld.wolfram.com (անգլերեն). Վերցված է 2020 թվականի օգոստոսի 12-ին.
↑ Pettofrezzo & Byrkit (1970, էջ. 90)
↑ Long (1972, էջ. 78)
↑ Long (1972, էջ. 85)
↑ Ստորև ցույց կտանք որ այն օղակ է։
↑ «Մոդուլո $n$ ամբողջ թվեր». Mathematics LibreTexts (անգլերեն). 2013, նոյեմբերի 16. Վերցված է 2020, օգոստոսի 12-ին.
↑ Սենգադիր Թ., Դիսկրետ Մաթեմատիկա և Կոմբինատորիկա, p. 293, at Google Books
↑ «Էյլերի աստիճանների գումարի վարկած». rosettacode.org (անգլերեն). Վերցված է 2020 նոյեմբերի 11-ին.
↑ Գերի, Մ․ Ռ․; Ջոնսոն, Դ․ Ս․ (1979). Համակարգիչներ և Անլուծելիություն․ NP-ամբոջականության տեսության ուղեցույց. Ու․ Հ․ Ֆրիման. ISBN 0716710447.

[1] Սանդոր Լեհոսկի; Ռիչարդ Ռուսկի (2006). Դեյվիդ Պատրիկ (ed.). Խնդիրներ լուծելու արվեստը (անգլերեն). Vol. 1 (7 ed.). AoPS Incorporated. էջ 44. ISBN 0977304566.

[2] Վեյսշտայն, Էրիկ. «Մոդուլար հանրահաշիվ». mathworld.wolfram.com (անգլերեն). Վերցված է 2020 թվականի օգոստոսի 12-ին.

[3] Pettofrezzo & Byrkit (1970, էջ. 90)

[4] Long (1972, էջ. 78)

[5] Long (1972, էջ. 85)

[6] Ստորև ցույց կտանք որ այն օղակ է։

[7] «Մոդուլո $n$ ամբողջ թվեր». Mathematics LibreTexts (անգլերեն). 2013, նոյեմբերի 16. Վերցված է 2020, օգոստոսի 12-ին.

[8] Սենգադիր Թ., Դիսկրետ Մաթեմատիկա և Կոմբինատորիկա, p. 293, at Google Books

[9] «Էյլերի աստիճանների գումարի վարկած». rosettacode.org (անգլերեն). Վերցված է 2020 նոյեմբերի 11-ին.

[10] Գերի, Մ․ Ռ․; Ջոնսոն, Դ․ Ս․ (1979). Համակարգիչներ և Անլուծելիություն․ NP-ամբոջականության տեսության ուղեցույց. Ու․ Հ․ Ֆրիման. ISBN 0716710447.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]