НОУ ІНТУЇТ | лекція | Модульна арифметика

1. інверсії Коли ми працюємо в модульної арифметики, нам часто потрібно знайти операцію, яка дозволяє...
2. мультиплікативна інверсія
3. Додавання і множення таблиць
4. Різні безлічі для додавання і множення
5. Ще два безлічі

інверсії

Коли ми працюємо в модульної арифметики, нам часто потрібно знайти операцію, яка дозволяє обчислити величину, зворотну заданому числу. Ми зазвичай шукаємо аддитивную інверсію (оператор, зворотний додаванню) або мультипликативную інверсію (оператор, зворотний множенню).

аддитивна інверсія

В Zn два числа a і b адитивно інверсний один одному, якщо b = n - a. наприклад,

В Zn аддитивная інверсія числа a може бути обчислена як b = n - a. Наприклад, аддитивная інверсія 4 в Z10 дорівнює 10 - 4 = 6.

В модульної арифметики кожне ціле число має адитивну інверсію. Сума цілого числа і його адитивної інверсії порівнянна з 0 по модулю n.

Зверніть увагу, що в модульної арифметики кожне число має адитивну інверсію, і ця інверсія унікальна; кожне число має одну і тільки одну аддитивную інверсію. Однак інверсія числа може бути безпосередньо тим же самим числом.

приклад 2.21

Знайдіть всі взаємно зворотні пари по додаванню в 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 взаємно прості.

приклад 2.22

Знайти мультипликативную інверсію 8 в Z10.

Рішення

Мультиплікативна інверсія не існує, тому що . Іншими словами, ми не можемо знайти число між 0 і 9, таке, що при множенні на 8 результат можна порівняти з 1 по mod 10.

приклад 2.23

Знайти всі мультиплікативні інверсії в Z10.

Рішення

Є тільки три пари, що задовольняють умовам існування мультипликативной інверсії: (1, 1), (3, 7) і (9, 9). Числа 0, 2, 4, 5, 6 і 8 не мають мультипликативной інверсії.

Ми можемо перевірити, що

(1 x 1) mod 10 = 1 (3 x 7) mod 10 = 1 (9 x 9) mod 10 = 1

приклад 2.24

Знайти всі мультиплікативні зворотні пари в Z11.

Рішення

Ми маємо такі пари: (1, 1), (2, 6), (3, 4), (5, 9), (7, 8) і (10, 10). При переході від Z10 до Z11 число пар збільшується. При Z11 НСД (11, a) = 1 (взаємно прості) для всіх значень a, крім 0. Це означає, що всі цілі числа від 1 до 10 мають мультиплікативний інверсії.

Ціле число a в Zn має мультипликативную інверсію тоді і тільки тоді, якщо НСД (n, a) = 1 (mod n)

Розширений алгоритм Евкліда, який ми обговорювали раніше в цій лекції, може знайти мультипликативную інверсію b в Zn, коли дані n і b і інверсія існує. Для цього нам треба замінити перший ціле число a на n (модуль). Далі ми можемо стверджувати, що алгоритм може знайти s і t, такі, що . Однак якщо мультипликативная інверсія b існує, НОД (n, b) повинен бути 1. Так що рівняння буде мати вигляд

(sxn) + (bxt) = 1

Тепер ми застосовуємо операції по модулю до обох сторін рівняння. Іншими словами, ми відображаємо кожну сторону до Zn. Тоді ми будемо мати

(Sxn + bxt) mod n = 1 mod n [(sxn) mod n] + [(bxt) mod n] = 1 mod n 0 + [(bxt) mod n] = 1 (bxt) mod n = 1 -> це означає, що t - це мультиплікативна інверсія b в Zn

Зверніть увагу, що на третьому рядку - 0, тому що, якщо ми ділимо , Приватне - s, а залишок - 0.

Розширений алгоритм Евкліда знаходить мультиплікативні інверсії b в Zn, коли дані n і b і НОД (n, b) = 1. Мультиплікативна інверсія b - це значення t, відображене в Zn.

малюнок 2.15 показує, як ми знаходимо мультипликативную інверсію числа, використовуючи розширений алгоритм Евкліда.

Застосування розширеного алгоритму Евкліда для пошуку мультипликативной інверсії

приклад 2.25

Знайти мультипликативную інверсію 11 в Z26.

Рішення

Ми використовуємо таблицю, аналогічну однією з тих, які ми вже застосовували перш за даних r1 = 26 і r2 = 11. Нас цікавить тільки значення t.

q r1 r2 r t1 t2 t 2 26 11 4 0 1 -2 2 11 4 3 1 -2 5 1 4 3 1 -2 5 -7 3 3 1 0 5 -7 26 1 0 -7 26

НСД (26, 11) = 1, що означає, що мультиплікативна інверсія 11 існує. Розширений алгоритм Евкліда дає t1 = (-7).

Мультиплікативна інверсія дорівнює (-7) mod 26 = 19. Іншими словами, 11 і 19 - мультиплікативна інверсія в Z26. Ми можемо бачити, що .

приклад 2.26

Знайти мультипликативную інверсію 23 в Z100.

Рішення

Ми використовуємо таблицю, подібну до тієї, яку застосовували до цього при r1 = 100 і r2 = 23. Нас цікавить тільки значення t.

q r1 r2 r t1 t2 t 4 100 23 8 0 1 -4 2 23 8 7 1 -4 19 1 8 7 1 -4 9 -13 7 7 1 0 9 -13 100 1 0 -13 100

НСД (100, 23) = 1, що означає, що інверсія 23 існує. Розширений Евкліда алгоритм дає t1 = -13. Інверсія - (-13) mod 100 = 87. Іншими словами, 13 і 87 - мультиплікативні інверсії в Z100. Ми можемо бачити, що .

приклад 2.27

Знайти мультипликативную інверсію 12 в Z26.

Рішення

Ми використовуємо таблицю, подібну до тієї, яку ми застосовували раніше при r1 = 26 і r2 = 12.

q r1 r2 r t1 t2 t 2 26 12 2 0 1 6 12 2 0 1 -2 2 0 -2 13

, Що означає отсутвствіе для числа 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.

Z13 = {0,1,2,3,4,5,6,7,8,9,10,11,12}, Z13 * = {1,2,3,4,5,6,7,8, 9,10,11,12},