В математиці модульна арифметика являє собою систему розрахунку для цілих чисел, за допомогою якої вони «перевертається» при досягненні певного значення – модуля (або множини них). Сучасний підхід до цього виду науки був розвинений Карлом Фрідріхом Гауссом у його книзі З арифметичним, опублікованій в 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 і Діффі-Хелльман. Тут вона надає кінцеві поля, які лежать в основі еліптичних кривих. Використовується в різних алгоритмах симетричного ключа, включаючи Advanced Encryption Standard (AES), Міжнародний алгоритм шифрування даних і RC4.
Застосування
Цей спосіб застосовується в тих областях, де потрібно читати цифри. Його розробили математики, а користуються ним всі, особливо фахівці з інформатики. Це добре описано в книгах на кшталт “Модульна арифметика для чайників”. Втім, ряд фахівців рекомендує не сприймати таку літературу всерйоз.
В інформатиці модульна арифметика часто застосовується двійковими та інших операціях, що включають циклічні структури даних фіксованої ширини. Її дуже люблять використовувати аналітики. Операція по модулю реалізована в багатьох мовах програмування і калькуляторах. В даному випадку вона є одним з прикладів такого застосування. Порівняння за модулем, ділення з залишком та інші прийоми також застосовуються в програмуванні.
В музиці арифметика по модулю 12 використовується при розгляді системи рівного темпераменту з дванадцяти тонів, у якій відбувається еквівалентність октави і энгармоники. Іншими словами, тональності у співвідношенні 1-2 або 2-1 еквівалентні. У музиці та інших гуманітарних дисциплінах арифметика відіграє досить важливу роль, але в підручниках інформатики про це зазвичай не пишуть.
Метод приведення дев’яток
Метод приведення дев’яток пропонує швидку перевірку десяткових арифметичних обчислень, виконаних вручну. Він заснований на модульної арифметики по модулю 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»).
Це дозволяє нам досліджувати математику на більш глибокому рівні і знаходити відносини між типами чисел, а не конкретними.
Властивості числа
Бути «трійкою» – це просто ще одна властивість числа. Можливо, не так відразу корисно, як парне/непарне, але воно є. Ми можемо створити правила типу «тринадцять х три відень = тринадцять» і так далі. Але це зводить з розуму. Ми не можемо робити нові слова весь час.
Операція по модулю (скорочено mod або «%» у багатьох мовах програмування) є залишком при діленні. Наприклад, «5 mod 3 = 2», що означає 2 – залишок, коли ви ділите 5 на 3.
При перетворенні повсякденних термінів в математику «парне число» – це те, де воно дорівнює «0 mod 2», тобто залишок дорівнює 0 при діленні на 2. Непарне число дорівнює «1 mod 2» (залишок 1).
Парні і непарні числа
Що таке парний х х парний непарний х непарний? Ну, це 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) мод 12 ≡ (8) мод 12 + (25) мод 12 ≡ (8) мод 12 + (1) мод 12 ≡ 9 мод 12. Ви інтуїтивно конвертували 25 в 1 і додали це до 8.
Використовуючи годинник в якості аналогії, ми можемо з’ясувати, чи працюють правила модульної арифметики, а вони працюють.
Додавання/Віднімання
Припустимо, два рази виглядають однаково на наших годинниках («2:00» та «14:00»). Якщо ми додамо однакові х годин до обом, що станеться? Ну, вони змінюються на ту ж суму на годиннику! 2:00 + 5 годин ≡ 14:00 + 5 годин – обидва покажуть 7:00.
Навіщо? Ми можемо просто додати 5 до 2 залишках, які обидва мають, і вони просуваються однаково. Для всіх конгруентних чисел (2 та 14) додавання і віднімання мають однаковий результат.
Важче зрозуміти, залишається множення таким же. Якщо 14 ≡ 2 (мод 12), ми можемо помножити обидва числа і отримати однаковий результат? Давайте подивимося, що станеться, коли ми помножимо на 3.
Ну, 2:00 * 3 × 6:00. Але що таке 14:00 * 3?
Пам’ятайте, 14 = 12 + 2. Отже, ми можемо сказати,
14 * 3 = (12 + 2) * 3 = (12 * 3) + (2 * 3)
Першу частину (12 * 3) можна ігнорувати! Переповнення 12 годин, яке несе 14, просто повторюється кілька разів. Але кого це хвилює? У будь-якому випадку ми ігноруємо переповнення.
Множення
При множенні має значення тільки залишок, тобто ті ж 2 години для 14:00 і 2:00. Інтуїтивно зрозуміло, що саме так я бачу, що множення не змінює відносини з модульної математикою (ви можете помножити обидві сторони модульного відносини і отримати той самий результат).
Ми робимо це інтуїтивно, але приємно дати йому ім’я. У вас є рейс, який прибуває в 3 години дня. Він затримується на 14 годин. У скільки він приземлиться?
14 ≡ 2 мод 12. Так що, варто думати про це як 2 години, тому літак приземлитися 5 годин ранку. Рішення просте: 3 + 2 = 5 ранку. Це трохи складніше, ніж проста операція по модулю, але принцип той же.
