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

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


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

Ми робимо це інтуїтивно, але приємно дати йому ім'я. У вас є рейс, який прибуває о третій годині дня. Він затримується на 14 годин. У скільки він приземлиться?

14 ≡ 2 мод 12. Так що, варто думати про це як 2 години, тому літак приземлитися 5 годин ранку. Рішення просте: 3 + 2 = 5 ранку. Це трохи складніше, ніж проста операція за модулем, але принцип той же.