Модульна арифметика: що це таке і де застосовується

В математиці модульна арифметика являє собою систему розрахунку для цілих чисел, за допомогою якої вони «перевертається» при досягненні певного значення - модуля (або множини них). Сучасний підхід до цього виду науки був розвинений Карлом Фрідріхом Гауссом у його книзі З арифметичним, опублікованій в 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 і, зокрема, на вирішальному властивості 10101. існують і інші приклади. Арифметика по модулю 7 використовується в алгоритмах, які визначають день тижня для конкретної дати. Зокрема, конгруентність Целлера і алгоритм "Судного дня" інтенсивно використовують арифметику по модулю 7.

Інші області застосування

Про модульної арифметики в криптографії вже було сказано. У цій сфері вона просто незамінна. В більш загальному сенсі, модульна арифметика також знаходить застосування в таких дисциплінах, як право, економіка (наприклад, теорія ігор) та інші галузі соціальних наук. Іншими словами, там, де пропорційний розподіл і розподіл ресурсів відіграє головну роль.
Оскільки модульна арифметика має такий широкий спектр застосувань, важливо знати, наскільки складно вирішити систему порівнянь. Лінійна система конгруэнций може бути вирішена за полиномиальное час у формі виключення Гауса. Детальніше це описує теорема про лінійної конгруенції. Алгоритми, такі як редукція Монтгомері, також існують, щоб дозволити ефективно виконувати прості арифметичні операції. Наприклад, множення і піднесення до степеня за модулем n, для великих чисел. Це дуже важливо для розуміння того, що таке криптографія. Адже в ній працюють з подібними операціями.

Конгруэнция

Деякі операції, такі як пошук дискретного логарифма або квадратичних конгруенції, здаються такими ж складними, як цілочисельна факторизація, і, таким чином, є відправною точкою для криптографічних алгоритмів шифрування. Ці проблеми можуть бути NP-проміжними.

Приклади

Нижче наведено три досить швидкі функції C - дві для виконання модульного множення і одна для зведення в модулярные числа для цілих чисел без знаку, що не перевищують 63 біта, без переповнення перехідних операцій.

Незабаром після виявлення цілих чисел (123 4 5 ) стає очевидним, що вони поділяються на дві групи:

Парний: ділиться на 2 (024 6 ).

Непарна: не ділиться на 2 (135 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 x 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 ранку. Це трохи складніше, ніж проста операція по модулю, але принцип той же.