Коли ми працюємо в модульної арифметики, нам часто потрібно знайти операцію, яка дозволяє обчислити величину, зворотну заданому числу. Ми зазвичай шукаємо аддитивную інверсію (оператор, зворотний додаванню) або мультипликативную інверсію (оператор, зворотний множенню).
аддитивна інверсія
В Zn два числа a і b адитивно інверсний один одному, якщо b = n - a. наприклад,
В Zn аддитивная інверсія числа a може бути обчислена як b = n - a. Наприклад, аддитивная інверсія 4 в Z10 дорівнює 10 - 4 = 6.
В модульної арифметики кожне ціле число має адитивну інверсію. Сума цілого числа і його адитивної інверсії порівнянна з 0 по модулю n.
Зверніть увагу, що в модульної арифметики кожне число має адитивну інверсію, і ця інверсія унікальна; кожне число має одну і тільки одну аддитивную інверсію. Однак інверсія числа може бути безпосередньо тим же самим числом.
Знайдіть всі взаємно зворотні пари по додаванню в Z10.
Дано шість пар адитивних інверсій - (0, 0). (1, 9). (2, 8). (3, 7). (4, 6) і (5, 5). У цьому списку 0 - інверсія самому собі; так само і 5. Зверніть увагу: адитивні інверсії назад один одному; якщо 4 - адитивна інверсія 6. тоді 6 - також аддитивная інверсія числа 4.
мультиплікативна інверсія
В Zn два числа a і b мультиплікативно інверсний один одному, якщо
Наприклад, якщо модуль дорівнює 10. то мультипликативная інверсія 3 є 7. Іншими словами, ми маємо.
В модульної арифметики ціле число може або не може мати мультипликативную інверсію. Ціле число і його мультипликативная інверсія порівнянні з 1 по модулю n.
Може бути доведено, що a має мультипликативную інверсію в Zn. якщо тільки НОД (n, a) = 1. У цьому випадку говорять, що a і n взаємно прості.
Знайти мультипликативную інверсію 8 в Z10.
, що означає отсутвствіе для числа 12 мультипликативной інверсії в Z26
Додавання і множення таблиць
Малюнок 2.16 показує дві таблиці для додавання і множення. При додаванні таблиць кожне ціле число має адитивну інверсію. Зворотні пари можуть бути знайдені, якщо результат їх складання - нуль. Ми маємо (0, 0). (1, 9). (2, 8). (3, 7). (4, 6) і (5, 5). При множенні таблиць ми отримуємо тільки три мультиплікативний пари (1, 1). (3, 7) і (9, 9). Пари можуть бути знайдені, коли результат множення дорівнює 1. Обидві таблиці симетричні по діагоналі, від лівої вершини до нижньої вершині справа. При цьому можна виявити властивості коммутативности для додавання і множення (a + b = b + a і). Таблиця додавання також показує, що кожен ряд або колонка може помінятися з іншим поруч або колонкою. Для таблиці множення це невірно.
Мал. 2.16. Таблиці додавання і множення для Z10
Різні безлічі для додавання і множення
У криптографії ми часто працюємо з інверсіями. Якщо відправник посилає ціле число (наприклад, ключ для шифрування слова), приймач застосовує інверсію цього цілого числа (наприклад, ключ декодування). Якщо ця дія (алгоритм шифрування / декодування) є складанням, безліч Zn може бути використано як безліч можливих ключів, тому що кожне ціле число в цій множині має адитивну інверсію. З іншого боку, якщо дія (алгоритм шифрування / декодування) - множення, Zn не може бути великою кількістю можливих ключів, тому що тільки деякі члени цієї множини мають мультипликативную інверсію. Нам потрібно інше безліч, яке є підмножиною Zn і включає в себе тільки цілі числа, і при цьому в Zn вони мають унікальну мультипликативную інверсію. Це безліч позначається Zn *. Малюнок 2.17 показує деякі випадки двох множин. Зверніть увагу, що безліч Zn * може бути отримано з таблиці множення типу показаної на рис. 2.16.
Кожен член Zn має адитивну інверсію, але тільки деякі члени мають мультипликативную інверсію. Кожен член Zn * має мультипликативную інверсію, але тільки деякі члени безлічі мають адитивну інверсію.
Ми повинні використовувати Zn, коли необхідні адитивні інверсії; ми повинні використовувати Zn *, коли необхідні мультиплікативні інверсії.
Мал. 2.17. Деякі безлічі Zn і Zn *
Ще два безлічі
Криптографія часто використовує ще два безлічі: Zp. і Zp *. Модулі в цих двох множинах - прості числа. Прості числа будуть обговорюватися в наступних лекціях; поки можна сказати, що просте число має тільки два дільника: ціле число 1 і саме себе.
Безліч Zp - те ж саме, що і Zn. за винятком того, що n - просте число. Zp містить всі цілі числа від 0 до p - 1. Кожен елемент в Zp має адитивну інверсію; кожен елемент окрім 0 має мультипликативную інверсію.
Безліч Zp * - те ж саме, що Zn *. за винятком того, що Zp * містить всі цілі числа від 1 до p - 1. Кожен елемент в Zp має адитивну і мультипликативную інверсії. Zp * дуже хороший кандидат, коли ми потребуємо в безлічі, яке підтримує аддитивную і мультипликативную інверсії.
Нижче показані два безлічі, коли p = 13.
Вітаю! Хотілося б прояснити наступне питання: у МТІ припинена державна акредитація та коли буде восстановлена- невідомо, а в диплом про профперепідготовка видається на базі МТІ (як я зрозумів). Як закінчиться справа з отриманням диплома?
Питання важливе й актуальне, тому що необхідно терміново пройти навчання і отримати диплом і не хотілося б витрачати час і платити гроші даремно (якщо диплом виявиться недійсним і т.п.). Роз'ясніть, будь ласка, докладніше ситуацію.
Добрий день, Хотілося б прояснити ви в майбутньому плануєте узгоджувати цю програму, з регуляторами і чи пройде сам диплом зараз, коли вводяться проф стандарти?