Մաթեմատիկայում մոդուլային թվաբանությունը ամբողջ թվերի հաշվարկման համակարգ է, որի օգնությամբ նրանք «շրջվում են», երբ հասնում են որոշակի արժեքի՝ մոդուլին (կամ դրանց հոգնակիին)։ Այս տեսակի գիտության ժամանակակից մոտեցումը մշակվել է Կարլ Ֆրիդրիխ Գաուսի կողմից իր Disquisitiones Arithmeticae-ում, որը հրապարակվել է 1801 թվականին: Համակարգչային գիտնականները շատ են սիրում օգտագործել այս մեթոդը, քանի որ այն շատ հետաքրքիր է և որոշակի նոր հնարավորություններ է բացում թվերի հետ գործառնություններում։
Էություն
Քանի որ ժամերի թիվը նորից սկսվում է 12-ի հասնելուց հետո, դա թվաբանական մոդուլ է 12: Ստորև բերված սահմանման համաձայն՝ 12-ը համապատասխանում է ոչ միայն 12-ին, այլև 0-ին, այնպես որ կարելի է անվանել նաև այն ժամանակը, որը կոչվում է « 12։00»։ «0:00». Ի վերջո, 12-ը նույնն է, ինչ 0 մոդուլը 12:
Մոդուլային թվաբանությունը կարելի է մաթեմատիկորեն մշակել՝ ներմուծելով համահունչ հարաբերություն ամբողջ թվերի հետ, որը համատեղելի է ամբողջ թվերի վրա կատարվող գործողությունների հետ։թվեր՝ գումարում, հանում և բազմապատկում: Դրական ամբողջ թվի համար n-ի համար երկու a և b թվերը համարվում են համահունչ մոդուլ n, եթե նրանց տարբերությունը a - b n-ի բազմապատիկն է (այսինքն, եթե գոյություն ունի k ամբողջ թիվ այնպես, որ a - b=kn):
պահումներ
Տեսական մաթեմատիկայի մեջ մոդուլային թվաբանությունը թվերի տեսության հիմքերից մեկն է, որն ազդում է դրա ուսումնասիրության գրեթե բոլոր ասպեկտների վրա և լայնորեն կիրառվում է նաև խմբերի, օղակների, հանգույցների և վերացական հանրահաշվի տեսության մեջ: Կիրառական մաթեմատիկայի բնագավառում այն կիրառվում է համակարգչային հանրահաշիվում, ծածկագրության, համակարգչային գիտության, քիմիայի, վիզուալ արվեստների և երաժշտության մեջ։
Պրակտիկա
Շատ գործնական կիրառություն է սերիական համարների իդենտիֆիկատորներում ստուգող գումարների հաշվարկը: Օրինակ, գրքերի որոշ սովորական ստանդարտներ օգտագործում են թվաբանական մոդուլ 11 (եթե թողարկվել է մինչև 2007թ. հունվարի 1-ը) կամ մոդուլ 10 (եթե թողարկվել է 2007թ. հունվարի 1-ից առաջ կամ հետո): Նմանապես, օրինակ, Միջազգային բանկային հաշիվների համարներում (IBAN): Սա օգտագործում է մոդուլ 97 թվաբանություն՝ բանկային հաշիվների համարներում օգտվողի մուտքագրման սխալները հայտնաբերելու համար:
Քիմիայում CAS գրանցման համարի վերջին նիշը (յուրաքանչյուր քիմիական միացության եզակի նույնականացման համարը) ստուգիչ նիշն է: Այն հաշվարկվում է CAS գրանցման համարի առաջին երկու մասերի վերջին թվանշանը բազմապատկելով 1-ով, նախորդ թվանշանը՝ 2 անգամ, նախորդ թվանշանը՝ 3 անգամ և այլն, գումարելով այդ ամենը և հաշվարկելով գումարի մոդուլը 10։։
Ի՞նչ է ծածկագրությունը: Փաստն այն է, որայն շատ ամուր կապ ունի քննարկվող թեմայի հետ։ Կրիպտոգրաֆիայում մոդուլային թվաբանության օրենքներն ուղղակիորեն ընկած են հանրային բանալի համակարգերի հիմքում, ինչպիսիք են RSA-ն և Diffie-Hellman-ը: Այստեղ այն ապահովում է վերջավոր դաշտերը, որոնք ընկած են էլիպսային կորերի հիմքում: Օգտագործվում է տարբեր սիմետրիկ բանալիների ալգորիթմներում, ներառյալ Ընդլայնված գաղտնագրման ստանդարտը (AES), տվյալների կոդավորման միջազգային ալգորիթմը և RC4:
Դիմում
Այս մեթոդն օգտագործվում է այն տարածքներում, որտեղ դուք պետք է կարդալ թվեր: Այն մշակվել է մաթեմատիկոսների կողմից, և դրանից օգտվում են բոլորը, հատկապես համակարգչային գիտնականները: Սա լավ փաստագրված է այնպիսի գրքերում, ինչպիսին է «Դիմերի համար մոդուլային թվաբանությունը»: Այնուամենայնիվ, մի շարք փորձագետներ խորհուրդ են տալիս լուրջ չվերաբերվել նման գրականությանը։
Համակարգչային գիտության մեջ մոդուլային թվաբանությունը հաճախ օգտագործվում է բիթային և այլ գործողություններում, որոնք ներառում են ֆիքսված լայնության շրջանաձև տվյալների կառուցվածքներ: Վերլուծաբանները սիրում են օգտագործել այն: Մոդուլային գործողությունն իրականացվում է բազմաթիվ ծրագրավորման լեզուներով և հաշվիչներով: Այս դեպքում դա նման կիրառման օրինակներից մեկն է։ Մոդուլների համեմատությունը, մնացորդով բաժանումը և այլ հնարքներ օգտագործվում են նաև ծրագրավորման մեջ։
Երաժշտության մեջ թվաբանական մոդուլ 12 օգտագործվում է, երբ դիտարկվում է տասներկու հնչերանգների հավասար խառնվածքի համակարգը, որում օկտավանն ու էնհարմոնիկը համարժեք են։ Այսինքն՝ 1-2 կամ 2-1 հարաբերակցությամբ ստեղները համարժեք են։ Երաժշտության և այլ հումանիտար գիտությունների մեջ թվաբանությունը բավականին նշանակալի դեր է խաղում, բայց դասագրքերումհամակարգչային գիտնականները սովորաբար չեն գրում այդ մասին։
Ինը կրճատելու մեթոդ
9-ականների փոխակերպման մեթոդն առաջարկում է ձեռքով տասնորդական թվաբանական հաշվարկների արագ ստուգում: Այն հիմնված է մոդուլային թվաբանական մոդուլի 9-ի և, մասնավորապես, որոշիչ հատկության վրա՝ 10 10 1.
կան այլ օրինակներ: Թվաբանական մոդուլ 7 օգտագործվում է ալգորիթմներում, որոնք որոշում են շաբաթվա օրը որոշակի ամսաթվի համար: Մասնավորապես, Զելլերի համընկնումն ու դատաստանի օրվա ալգորիթմը մեծապես օգտագործում են թվաբանական մոդուլ 7։
Այլ հավելվածներ
Գաղտնագրության մեջ մոդուլային թվաբանության մասին արդեն ասվել է։ Այս ոլորտում նա ուղղակի անփոխարինելի է։ Ավելի ընդհանուր առմամբ, մոդուլային թվաբանությունը նաև կիրառություն է գտնում այնպիսի առարկաներում, ինչպիսիք են իրավունքը, տնտեսագիտությունը (օրինակ՝ խաղերի տեսությունը) և սոցիալական գիտությունների այլ ոլորտներում: Այլ կերպ ասած, որտեղ մեծ դեր է խաղում ռեսուրսների համամասնական բաժանումն ու բաշխումը։
Քանի որ մոդուլային թվաբանությունն ունի կիրառման այդքան լայն շրջանակ, կարևոր է իմանալ, թե որքան դժվար է լուծել համեմատությունների համակարգը: Համապատասխանությունների գծային համակարգը կարող է լուծվել բազմանդամ ժամանակում՝ Գաուսի վերացման տեսքով: Սա ավելի մանրամասն նկարագրված է գծային համադրման թեորեմով։ Կան նաև այնպիսի ալգորիթմներ, ինչպիսին է Մոնտգոմերիի կրճատումը, որպեսզի թույլ տան պարզ թվաբանական գործողություններ արդյունավետորեն կատարել: Օրինակ՝ բազմապատկման և հզորացման մոդուլ n, մեծ թվերի համար: Սա շատ կարևոր է իմանալ՝ հասկանալու համար, թե ինչծածկագրություն. Ի վերջո, այն պարզապես աշխատում է նմանատիպ գործողություններով:
համապատասխանություն
Որոշ գործողություններ, ինչպիսիք են դիսկրետ լոգարիթմը կամ քառակուսի համընկնում գտնելը, թվում է, թե նույնքան բարդ են, որքան ամբողջ թվերի ֆակտորացումը և, հետևաբար, գաղտնագրման ալգորիթմների և գաղտնագրման մեկնարկային կետն են: Այս խնդիրները կարող են լինել NP-միջանկյալ:
Օրինակներ
Ստորև բերված են երեք բավականին արագ C ֆունկցիաներ՝ երկուսը մոդուլային բազմապատկման համար, և մեկը՝ մինչև 63 բիթ աննշան ամբողջ թվերի մոդուլային թվերի բարձրացման համար՝ առանց անցողիկ հորդառատության:
Ամբողջ թվերի հայտնաբերումից անմիջապես հետո (1, 2, 3, 4, 5…) պարզ է դառնում, որ դրանք բաժանվում են երկու խմբի՝
- Զույգ. բաժանվում է 2-ի (0, 2, 4, 6..).
- Կենտ. չի բաժանվում 2-ի (1, 3, 5, 7…).
Ինչու է այս տարբերակումը կարևոր: Սա աբստրակցիայի սկիզբն է։ Մենք նկատում ենք թվի հատկությունները (օրինակ՝ զույգ կամ կենտ), և ոչ միայն ինքնին թիվը («37»):
Սա մեզ թույլ է տալիս ուսումնասիրել մաթեմատիկան ավելի խորը մակարդակով և գտնել հարաբերություններ թվերի տեսակների միջև, այլ ոչ թե կոնկրետների:
Թվի հատկություններ
«Երեք» լինելը թվի ևս մեկ հատկություն է: Միգուցե ոչ այնքան անմիջապես օգտակար, որքան զույգ/կենտ, բայց դա կա: Մենք կարող ենք ստեղծել այնպիսի կանոններ, ինչպիսիք են «տասներեք x երեք երակ=տասներեք» և այլն: Բայց դա խելագարություն է: Մենք չենք կարող անընդհատ նոր բառեր ստեղծել։
Մոդուլային գործողությունը (կրճատ ձև կամ «%» շատ ծրագրավորման լեզուներում) մնում է, երբբաժանում. Օրինակ՝ «5 mod 3=2», ինչը նշանակում է, որ 2-ը մնացորդն է, երբ 5-ը բաժանում ես 3-ի:
Առօրյա տերմինները մաթեմատիկայի վերածելիս «զույգ թիվն» այն է, որտեղ այն «0 mod 2» է, այսինքն՝ մնացորդը 0 է, երբ բաժանվում է 2-ի: Կենտ թիվն է «1 mod 2» (ունի մնացորդ: 1-ից).
Զույգ և կենտ թվեր
Ի՞նչ է զույգ x զույգ x կենտ x կենտ: Դե, դա 0 x 0 x 1 x 1=0 է: Իրականում, դուք կարող եք տեսնել, թե արդյոք զույգ թիվը բազմապատկվում է ցանկացած վայրում, որտեղ ամբողջ արդյունքը կլինի զրո:
Մոդուլային մաթեմատիկայի հնարքն այն է, որ մենք արդեն օգտագործել ենք այն ժամանակը պահելու համար, որը երբեմն կոչվում է «ժամացույցի թվաբանություն»:
Օրինակ՝ առավոտյան ժամը 7:00 (առավոտյան/երեկո - նշանակություն չունի): Որտե՞ղ կլինի ժամացույցը 7 ժամից:
Մոդուլյացիա
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2-ը մնացորդն է, երբ 14-ը բաժանվում է 12-ի: 14 Mod 12=2 mod 12 հավասարումը նշանակում է 14 ժամ և 2 ժամ նույնը 12-ժամյա ժամացույցի վրա: Դրանք համահունչ են՝ նշված եռակի հավասար նշանով. 14 ≡ 2 mod 12.
Եվս մեկ օրինակ. ժամը 8:00-ն է: Որտե՞ղ կլինի մեծ ձեռքը 25 ժամից:
25-ը 8-ին ավելացնելու փոխարեն կարող եք հասկանալ, որ 25 ժամը ընդամենը «1 օր + 1 ժամ» է: Պատասխանը պարզ է. Այսպիսով, ժամացույցը կավարտվի 1 ժամ առաջ՝ 9:00-ին։
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12: Դուք ինտուիտիվ կերպով փոխակերպեցիք 25-ը 1-ի և ավելացրեցիք սա մինչև 8.
Օգտագործելով ժամացույցը որպես անալոգիա՝ մենք կարող ենք պարզել, թե արդյոքմոդուլային թվաբանության կանոնները, և դրանք գործում են։
Ավելացում/հանում
Ենթադրենք, մեր ժամացույցի վրա երկու անգամ նույն տեսքն ունի («2:00» և «14:00»): Եթե երկուսին էլ ավելացնենք նույն x ժամը, ի՞նչ կլինի: Դե, նրանք փոխվում են նույն գումարով ժամացույցի վրա: 2։00 + 5 ժամ ≡ 14։00 + 5 ժամ. երկուսն էլ ցույց կտան 7։00։
Ինչու? Մենք կարող ենք ուղղակի 5-ը ավելացնել 2 մնացորդներին, որոնք երկուսն էլ ունեն, և նրանք առաջ են գնում նույն ձևով: Բոլոր համընկնող թվերի համար (2 և 14) գումարումն ու հանումը ունեն նույն արդյունքը։
Ավելի դժվար է իմանալ, թե արդյոք բազմապատկումը մնում է նույնը: Եթե 14 ≡ 2 (mod 12), կարո՞ղ ենք բազմապատկել երկու թվերն էլ և ստանալ նույն արդյունքը: Տեսնենք, թե ինչ կլինի, երբ բազմապատկենք 3-ով։
Դե, 2:003 × 6:00: Բայց ինչ է 14:003?
Հիշեք, 14=12 + 2: Այսպիսով, մենք կարող ենք ասել
143=(12 + 2)3=(123) + (23)
Առաջին մասը (123) կարելի է անտեսել: 12 ժամվա հոսքը, որը կրում է 14-ը, պարզապես կրկնվում է մի քանի անգամ։ Բայց ո՞ւմ է դա հետաքրքրում։ Մենք, այնուամենայնիվ, անտեսում ենք գերհոսքը։
Բազմապատկում
Բազմապատկելիս նշանակություն ունի միայն մնացորդը, այսինքն՝ նույն 2 ժամը 14։00-ի և 2։00-ի համար։ Ինտուիտիվ կերպով ես տեսնում եմ, որ բազմապատկումը չի փոխում հարաբերությունները մոդուլային մաթեմատիկայի հետ (կարող եք բազմապատկել մոդուլային հարաբերությունների երկու կողմերը և ստանալ նույն արդյունքը):
Մենք դա անում ենք ինտուիտիվ կերպով, բայց հաճելի է դրան անուն տալ: Դուք թռիչք ունեք, որը ժամանում է ժամը 15:00-ին: Նահետաձգվել է 14 ժամով։ Ո՞ր ժամին այն վայրէջք կկատարի:
14 ≡ 2 ռեժիմ 12. Այսպիսով, մտածեք որպես ժամը 2, այնպես որ ինքնաթիռը վայրէջք կկատարի առավոտյան ժամը 5-ին: Լուծումը պարզ է՝ 3 + 2=առավոտյան 5։ Սա մի փոքր ավելի բարդ է, քան պարզ մոդուլային գործողությունը, բայց սկզբունքը նույնն է:
