НОУ ІНТУЇТ | лекція | Порівняння і матриці

1. 3.2. лінійне рівняння Криптографія часто включає в себе рішення рівняння або безлічі рівнянь однієї...
2. Система лінійних рівнянь, що містять порівняння

3.2. лінійне рівняння

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

Лінійні рівняння з одним невідомим, що містять порівняння

Давайте подивимося, як вирішуються рівняння з одним невідомим, що містять порівняння, тобто рівняння ax = b (mod n). Рівняння цього типу може не мати жодного рішення або мати обмежене число рішень. Припустимо, що НОД (a, n) = d. Якщо d † b, рішення не існує. Якщо d | b, то є d рішень.

Якщо d | b, то для того, щоб знайти рішення, ми використовуємо таку стратегію.

1. Скоротити рівняння, розділивши обидві сторони рівняння (включаючи модуль) на d.
2. Помножити обидві сторони скороченого рівняння на мультипликативную інверсію, щоб знайти конкретне рішення x0.
3. Загальні рішення будуть x = x0 + k (n / d) для k = 0, 1 ..., (d - 1).

приклад 3.8

Вирішити рівняння .

Спочатку ми знайдемо НСД (10,15) = 5. Отримане число 5 не ділиться на 2, рішення відсутнє.

приклад 3.9

Вирішити рівняння .

Рішення

Зауважимо, що НОД (14, 18) = 2. Оскільки 2 ділить 12, ми маємо точно два рішення, але спочатку скоротимо рівняння:

Обидва рішення, 6 і 15, задовольняють рівняння порівняння, тому що , а також .

приклад 3.10

Вирішити рівняння .

Рішення

Спочатку ми наводимо рівняння до форми . Ми додаємо (-4) до обох сторін (4 аддитивная інверсія). отримаємо . Оскільки НОД (3, 13) = 1, рівняння має тільки одне рішення, . Ми можемо бачити, що відповідь задовольняє початковим рівняння: .

Система лінійних рівнянь, що містять порівняння

Ми можемо вирішити систему лінійних рівнянь з одним і тим же модулем, якщо матриця, сформована з коефіцієнтів системи рівнянь, має зворотну матрицю. Для вирішення рівняння складаються три матриці. Перша - квадратна матриця - формується з коефіцієнтів рівняння. Друга - матриця-стовпець - складається з змінних. Третя - матриця-стовпець в правій стороні оператора порівняння - складається з значення bn. Ми можемо це рівняння представити як добуток матриць. Якщо обидві сторони порівняння помножити на мультипликативную інверсію першої матриці, в результаті ми отримаємо рішення системи рівнянь, як це показано на Мал. 3.9 .

Мал.3.9.

Система лінійних рівнянь

приклад 3.11

Вирішити систему наступних трьох рівнянь:

3x + 5y + 7z = 3 (mod 16) x + 4y + 13z = 5 (mod 16) 2x + 7y + 3z = 4 (mod 16)

Рішення

Тут x, y і z грають ролі x1, x2, і x3. Матриця, сформована з коефіцієнтів рівнянь, - оборотна. Ми знаходимо мультипликативную інверсію матриці і множимо її на матрицю стовпчика, сформовану з 3, 5 і 4. результат - , і . Ми можемо перевірити відповідь, підставляючи ці значення в рівняння.