Файл: Теорія чисел в криптографії.pdf

2. "i, j, k = 1, m : ri × rj × rk º ri × (rj × rk )º (ri × rj )× rk (mod m) - асоціативність;

3."i, j, k = 1, m : ri × (rj + rk )º ri × rj + ri × rk (mod m) - дистрибутивність для лівого множника;

4."i, j, k = 1, m : (rj + rk )× ri º ri × rj + ri × rk (mod m) - дистрибутивність для правого множника.

Висновок:

Повна система лишків створює комутативну напівгрупу за множенням Ніяких обмежень на значення модуля m при цьому не накладалося.

Отже повна система лишків за будь-яким модулем m з операціями додавання та множення створює кільце.

Для визначення повної системи лишків, як поля не вистачає доведення існування єдиного нейтрального елементу з множення – одиниці, та єдиного оберненого елементу з множення до будь-якого елементу з повної системи лишків, тобто елементу, для якого виконується рівність:

ri × x º 1(mod m)

У випадку, коли модуль – просте число p існування одиничного елементу відносно множення для повної системи лишків доводить мала теорема Ферма.

Мала теорема Ферма.

Розглядаються цілі додатні числа: довільне ціле a та просте число p . Якщо (a, p) = 1 , то завжди вірно:

p | a p - a

Якщо записати у термінах модульної арифметики, то теорема Ферма набуває вигляду:

a p - a º 0(mod p) ,

або, використовуючи властивості конгруенцій,

a p−1 º 1(mod p)

Якщо модуль m є складеним числом для повної системи лишків одиничний елемент визначити не можна, але теорема Ейлера доводить існування єдиної одиниці за множенням для зведеної системи лишків для довільного цілого модуля.

Теорема Ейлера (узагальнення малої теореми Ферма):

Для двох довільних цілих додатних чисел a та m > 1 , таких, що (a, m) = 1, вірно: aϕ(m ) º 1(mod m),

де j(m) - функція Ейлера, кількість чисел, менших за m і взаємно простих з ним.

Якщо m = p - просте число, функція Ейлера буде j(p) = p -1 , а теорема Ейлера набуває вигляду a p−1 º 1(mod p), що відповідає малій теоремі Ферма. Тобто теорема Ейлера розповсюджує результат теореми Ферма на будь-який складний цілий модуль.

Висновки:

1. Одиниця з множення існує і єдина для повної системи лишків за простим модулем p .

31

2. За складеним модулем m одиниця з множення існує тільки на класах зведеної системи лишків.

Приклади

1. Показати, що 120 + 220 + 320 + 520 + 620 + 720 + 920 +1020 º -3(mod 11) .

Розв’язання.

Модуль 11 – просте число. Всі числа, що входять до суми – 1, 2, 3, 5, 6, 7, 9, 10 – належать до повної системи найменших додатних лишків за модулем 11. Всі ці числа взаємно прості з модулем. Отже, використовуючи малу теорему Ферма для кожного з

цих чисел можна записати: a10 º 1(mod 11), aÎ[1,2,3,5,7,9,10]

За властивостями конгруенцій можна піднести до квадрату обидві частини останньої конгруенції, тобто a 20 º 1(mod 11) і замінити числа в вихідній сумі на

еквівалентні:

1 +1 +1 +1+1 +1 +1 +1 º 8(mod 11)

Далі, використовуючи той факт, що 11t є нейтральним елементом по додаванню (виконує роль 0), віднімемо від 8 цей нейтральний елемент:

8 -11 = -3 º -3(mod 11) - що і необхідно було показати.

2. Показати, що 117 + 317 + 517 + 917 +1117 +1317 º 0(mod 14).

Розв’язання.

Всі числа, що входять до суми є взаємно простими з модулем 14 і належать до повної системи найменших лишків. Степінь, до якого треба піднести всі числа, непарний – 17. Отже, можна використати той факт, що від’ ємна величина в цьому степені зберігає знак.

Змінимо елементи повної системи найменших додатних лишків на елементи

отже для кожного модуля можна застосувати малу теорему Ферма: якщо (a , p) = 1 a p−1 º 1(mod p)

Отже, 732 º 1(mod 3); 734 º 1(mod 5); 736 º 1(mod 7)

Піднесемо першу отриману конгруенцію до 6-го степеня (за властивостями), другу – до 3-го степеня, третю – до 2-го степеня. Отримаємо:

7312 º 1(mod 3); 7312 º 1(mod 5); 7312 º 1(mod 7)

Використовуючи властивість, за якою конгруенцію, що виконується за різними модулями можна розглядати як конгруенцію за модулем, що складає НСК цих модулів,

запишемо: 7312 º 1(mod 3 ×5 × 7), або 7312 º 1(mod 105), що і потрібно було показати.

4. Довести, що за умови (a ,12) = 1, (b,12) =1 число a96 - b96 завжди ділиться на 144.

Розв’язання

32

Якщо число взаємно просте з числом 12, то воно буде взаємно простим і з числом 144 = 122 . Отже для такого числа виконується теорема Ейлера: aj(m) º 1(mod m)

Функція Ейлера для числа 144 дає результат: j(144) = j(32 × 24 )= (24 - 23 )(32 - 3)= 8 ×6 = 48

Отже a 48 º 1(mod 144) і b48 º 1(mod 144)

Використовуючи властивості конгруенцій, піднесемо обидві конгруенції до квадрату: a96 º 1(mod 144); b96 º 1(mod 144).

За властивостями конгруенцій ми можемо відняти від першої конгруенції другу:

a96 - b96 º 0(mod 144)

Остання конгруенція і означає, що за умови (a ,12) = 1, (b,12) =1 число a96 - b96 завжди ділиться на 144.

5. Знайти останню цифру числа 232323 .

Розв’язання.

Знаходження останньої цифри числа еквівалентно знаходженню залишка від ділення числа на 10. Позначимо невідому останню цифру через

x : 232323 º x(mod 10)

23 = 2 ×10 + 3 - підставимо до конгруенції:

(2 ×10 + 3)2323 º x(mod 10)

Якщо 2 ×10 + 3 піднести до степеня 2323 за біномом Ньютона, то у кожному з доданків крім останнього будемо мати за множник 10 в степенях від 2323 до 1. Всі такі доданки конгруентні 0 за модулем 10. Отже, після піднесення до степеня лівої частини конгруенції, будемо мати :

32323 º x(mod 10);

(3,10) = 1 , причому 10 – складене число. Для цієї пари виконується теорема Ейлера: 3j(10) º 1(mod 10)

j(10) = j(2 × 5) = 1× 4 = 4 34 º 1(mod 10)

Знайдемо найменший залишок для степені 2323 за модулем 4:

2323 = 580 3 ; 2323 = 580 × 4 + 3 4 4

34×580+3 º x(mod 10); (34 )580 × 33 º x(mod 10)

Оскільки 34 º 1(mod 10) 1580 ×33 = 27 = 20 + 7 º 7(mod 10) x = 7

Отже Останньою цифрою у числа 232323 буде цифра 7.

6. Знайти число, складене з цифр трьох найменших розрядів числа 3798 .

Розв’язання.

Необхідно знайти цифри трьох найменших розрядів даного числа, тобто необхідно знайти залишок від ділення даного числа на 1000.

(3,1000) = 1 3j(1000) º 1(mod 1000); j(1000) = j(23 ×53 )= (8 - 4)(125 - 25) = 400

3400 º 1(mod 1000)

Піднесемо конгруенцію до квадрату:

3800 º 1(mod 1000) 3798 ×9 º 1(mod 1000);

За властивостями конгруенцій ми до будь-якого боку конгруенції можемо додавати ціле число, кратне модулю. Додамо праворуч -1000:

3798 ×9 º 1 -1000(mod 1000) 3798 ×9 º -999(mod 1000)

33

За властивостями конгруенцій можна ділити обидва боки конгруенції на число, взаємно просте з модулем. Поділимо на 9 (9,1000)=1:

3798 º -111(mod 1000) 3798 º -111 +1000(mod 1000) 3798 º 889(mod 1000)

Відповідь: три останні цифри числа 3798 будуть 8, 8, 9. Отже число, що складається з них – 889.

Для ствердження про існування та єдиності оберненого елементу з множення необхідно спочатку дослідити питання існування та єдиність розв’язку конгруенції з одним невідомим a × x º 1(mod m) . Саме цьому питанню і присвячений наступний розділ.

Висновки Після вивчення теми 2 ви повинні знати такі факти:

1числа, які від ділення на модуль m дають рівні залишки r називаються рівно залишковими, або конгруентними (порівнянними) за модулем m ;

2конгруенція розглядається на множині цілих чисел Z = 0,±1, ± 2, ± 3,... ;

3якщо a конгруентне b за модулем m , такі записи еквівалентні:

1. a º b(mod m),

2. a = b + m ×t , t Î Z , 3. m | (a - b);

4конгруенція рефлективна, транзитивна і симетрична;

5конгруенція двох цілих чисел за модулем m має 8 властивостей, що не змінюють модуль і 5 властивостей з урахуванням модуля. Використовуючи ці властивості конгруенції можна значно спрощувати.

6всі числа, які мають однаковий залишок за модулем m створюють безкінечний клас рівно залишкових чисел. Множина цілих чисел за модулем m розбивається рівно залишковими числами на m класів. Найменшими додатними представниками

цих класів є числа 0, 1, 2, ..., m -1. Кожний представник класу відносно інших представників цього класу носить назву ЛИШОК.

34