მათემატიკაში მოდულური არითმეტიკა არის მთელი რიცხვების გამოთვლითი სისტემა, რომლის დახმარებით ისინი "აბრუნებენ", როდესაც მიაღწევენ გარკვეულ მნიშვნელობას - მოდულს (ან მათ მრავლობითს). ამ სახის მეცნიერებისადმი თანამედროვე მიდგომა შეიმუშავა კარლ ფრიდრიხ გაუსმა თავის 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-ჯერ და ა.შ.
რა არის კრიპტოგრაფია? ფაქტია რომმას აქვს ძალიან ძლიერი კავშირი განსახილველ თემასთან. კრიპტოგრაფიაში, მოდულარული არითმეტიკის კანონები პირდაპირ ემყარება საჯარო გასაღების სისტემებს, როგორიცაა RSA და Diffie-Hellman. აქ ის უზრუნველყოფს სასრულ ველებს, რომლებიც ეფუძნება ელიფსურ მრუდებს. გამოიყენება სხვადასხვა სიმეტრიული გასაღების ალგორითმებში, მათ შორის Advanced Encryption Standard (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 სამი ვენა=ცამეტი" და ა.შ. მაგრამ ეს გიჟია. მუდმივად ახალ სიტყვებს ვერ ვქმნით.
მოდულის ოპერაცია (შემოკლებით mod ან "%" ბევრ პროგრამირების ენაში) არის დარჩენილი, როდესაცდაყოფა. მაგალითად, "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 საათისთვის. ინტუიციურად, ასე ვხედავ გამრავლებას, რომელიც არ ცვლის ურთიერთობას მოდულურ მათემატიკასთან (შეგიძლიათ გაამრავლოთ მოდულური ურთიერთობის ორივე მხარე და მიიღოთ იგივე შედეგი).
ჩვენ ამას ვაკეთებთ ინტუიციურად, მაგრამ სასიამოვნოა სახელის მიცემა. თქვენ გაქვთ რეისი, რომელიც ჩამოდის საღამოს 3 საათზე. ისდაგვიანებულია 14 საათით. რომელ საათზე დაეშვება?
14 ≡ 2 მოდიფიკაცია 12. ასე რომ, იფიქრეთ როგორც 2 საათზე, ასე რომ თვითმფრინავი დაეშვება დილის 5 საათზე. გამოსავალი მარტივია: 3 + 2=დილის 5 საათი. ეს ცოტა უფრო რთულია, ვიდრე მარტივი მოდულის ოპერაცია, მაგრამ პრინციპი იგივეა.
