В математиката модулната аритметика е изчислителна система за цели числа, с помощта на която те "преобръщат", когато достигнат определена стойност - модула (или множественото число от тях). Съвременният подход към този вид наука е разработен от Карл Фридрих Гаус в неговите 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 (ако са пуснати преди 1 януари 2007 г.) или по модул 10 (ако са пуснати преди или след 1 януари 2007 г.). По същия начин, например, в международните номера на банкови сметки (IBAN). Това използва аритметика по модул 97 за откриване на грешки при въвеждане на потребителя в номерата на банкови сметки.
В химията последната цифра от регистрационния номер по CAS (уникалният идентификационен номер за всяко химично съединение) е контролната цифра. Изчислява се, като се вземе последната цифра от първите две части на регистрационния номер на CAS, умножена по 1, предишната цифра 2 пъти, предишната цифра 3 пъти и т.н., като се събира всичко и се изчислява сумата по модул 10.
Какво е криптография? Факт е, чеима много силна връзка с обсъжданата тема. В криптографията законите на модулната аритметика са пряко в основата на системи с публичен ключ като RSA и Diffie-Hellman. Тук той предоставя крайните полета, които лежат в основата на елиптичните криви. Използва се в различни алгоритми за симетрични ключове, включително Advanced Encryption Standard (AES), Международен алгоритъм за криптиране на данни и RC4.
Заявление
Този метод се използва в области, където трябва да четете числа. Той е разработен от математици и всички го използват, особено компютърните учени. Това е добре документирано в книги като Модулна аритметика за манекени. Въпреки това, редица експерти препоръчват да не се приема сериозно тази литература.
В компютърните науки модулната аритметика често се използва в побитови и други операции, включващи кръгови структури от данни с фиксирана ширина. Анализаторите обичат да го използват. Операцията по модул е реализирана в много езици за програмиране и калкулатори. В този случай това е един пример за такова приложение. Сравнение по модули, деление с остатък и други трикове също се използват в програмирането.
В музиката аритметичният модул 12 се използва, когато се разглежда система от равен темперамент от дванадесет тона, в която октавата и енхармоника са еквивалентни. С други думи, ключовете в съотношение 1-2 или 2-1 са еквивалентни. В музиката и други хуманитарни науки аритметиката играе доста важна роля, но в учебницитекомпютърните учени обикновено не пишат за това.
Метод за намаляване на деветки
Методът за преобразуване 9s предлага бърза проверка на ръчни десетични аритметични изчисления. Базира се на модулна аритметика по модул 9 и по-специално на решаващото свойство 10 10 1.
има и други примери. Аритметиката по модул 7 се използва в алгоритми, които определят деня от седмицата за определена дата. По-специално, конгруентността на Zeller и алгоритъмът на Страшния съд използват силно аритметика по модул 7.
Други приложения
Вече беше казано за модулната аритметика в криптографията. В тази област тя е просто незаменима. По-общо казано, модулната аритметика намира приложение и в дисциплини като право, икономика (като теория на игрите) и други области на социалните науки. С други думи, където пропорционалното разделяне и разпределение на ресурсите играят основна роля.
Тъй като модулната аритметика има толкова широк спектър от приложения, е важно да се знае колко трудно е да се реши система от сравнения. Линейна система от конгруенции може да бъде решена за полиномно време под формата на елиминиране на Гаус. Това е описано по-подробно от теоремата за линейната конгруентност. Алгоритми като редукция на Монтгомъри също съществуват, за да позволят прости аритметични операции да се изпълняват ефективно. Например, умножение и степенуване по модул n, за големи числа. Това е много важно да се знае, за да се разбере каквокриптография. В крайна сметка, той просто работи с подобни операции.
Съгласие
Някои операции, като намиране на дискретния логаритъм или квадратичната конгруентност, изглеждат толкова сложни, колкото целочисленото разлагане на множители и по този начин са отправна точка за криптографски алгоритми и криптиране. Тези проблеми може да са NP-междинни.
Примери
Следват три доста бързи функции C - две за извършване на модулно умножение и една за повишаване до модулни числа за цели числа без знак до 63 бита, без преходно препълване.
Малко след откриването на цели числа (1, 2, 3, 4, 5…) става очевидно, че те са разделени на две групи:
- Четно: дели се на 2 (0, 2, 4, 6..).
- Нечетно: не се дели на 2 (1, 3, 5, 7…).
Защо това разграничение е важно? Това е началото на абстракцията. Забелязваме свойствата на числото (например четно или нечетно), а не само самото число („37“).
Това ни позволява да изследваме математиката на по-дълбоко ниво и да намерим връзки между типове числа, а не конкретни.
Свойства на число
Да бъдеш "тройка" е просто още едно свойство на число. Може би не е толкова полезно, колкото четно/нечетно, но е налице. Можем да създадем правила като "тринадесет х три вена=тринадесет" и така нататък. Но това е лудост. Не можем да създаваме нови думи през цялото време.
Модулната операция (съкратено 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 сутринта (am/pm - няма значение). Къде ще бъде часовата стрелка след 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 mod 12. Така че, мислете за това като за 2 часа, така че самолетът ще кацне в 5 часа сутринта. Решението е просто: 3 + 2=5 сутринта. Това е малко по-сложно от простата модулна операция, но принципът е същият.
