[Список тем] [Вступление к этой теме] Страницы темы: [1] [2]

Методика решения уравнений в алгебре вычетов

Нахождение обратного вычета - задача постоянно решаемая в системах шифрования с открытым ключем.

Непосредственная проверка

Для небольших n в системе обратимых вычетов количество элементов не значительно, и перемножая их попарно можно сравнительно легко для каждого вычета найти обратный.
Пример: n = 18. Система обратимых вычетов {1, 5, 7, 11, 13, 17}.
1*1=1 ≡ 1 (mod 18).
5*5=25 ≡ 7 (mod 18); 5*7=35 ≡ 17 (mod 18); 5*11=55 ≡ 1 (mod 18).
7*7=49 ≡ 13 (mod 18); 7*13=91 ≡ 1 (mod 18).
17*17=289 ≡ 1 (mod 18).
Обратны самим себе 1 и 17, взаимно обратны 5 и 11, 7 и 13.

Использование таблицы умножения

Найти b=a-1 можно легко, если для модуля n имеется таблица умножения. На пересечении строки и столбца будет 1 только для взаимно обратных вычетов, стоящих в заголовке таблицы /в верхней строке и крайнем левом столбце/. Пример: n = 5
Таблица умножения
* 01234
0 00000
1 01234
2 02413
3 03142
4 04321

1-1 = 1.     2-1 = 3,     3-1 = 2,     4-1 = 4 (mod 5).

Алгоритм Евклида

ax≡ 1 (mod n) означает, что существует y, такое, что ax = 1 + ny. Такое уравнение в целых числах называется Диафантовым, а метод его решения - алгоритмом Евклида.
На каждом шаге решения необходимо:

  • выражать предыдущую переменную через последующую;
  • исключать в выражении предыдущей переменной через последующую целую часть;
  • обозначать дробную часть в выражении переменной следующей целочисленной переменной;
  • продолжать процесс пошагового решения необходимо до получения решения в целых числах;
  • после этого надо последовательно выражая все переменные через последнюю получить остаток, который будет сравним с искомым обратным вычетом.

    Пример: a=5; n=18.
    5x ≡ 1 (mod 18) означает 5x = 1 + 18y. Где 18y=15y+3y
    x = 3y + ((3y+1)/5). Обозначим дробную часть выражения новой целой переменной z.    ((3y+1)/5)=z → x = 3y + z.
    Предыдущую переменную выражаем через последующую.
    3y+1 = 5z. Исключаем целую часть y = (5z - 1)/3 = z + ((2z-1)/3. Дробную часть обозначаем переменной t.    (2z-1)/3 = t → y = z + t.
    Выражаем z через t.
    2z-1 = 3t   →  z = (3t + 1)/2.
    Исключаем целую часть z = t+(t+1)/2. Дробную часть обозначаем переменной u.    (t+1)/2 = u  →  z = t+u.
    Выражаем t через u.
    (t+1) = 2u → t = 2u -1. Дробной части нет.
    Выражаем все переменные через последнюю:
    t = 2u -1
    z = t+u = 2u -1 + u = 3u -1
    y = z + t = 3u -1 + 2u -1 = 5u -2
    x = 3y + z = 3*(5u -2) + 3u -1 = 18u - 7
    Все переменные - целые. 18u кратно модулю и на результат не влияет.
    x ≡ -7 ≡ 11 (mod 18).
    Проверка 5*11= 55 = 54+1 ≡ 1 (mod 18).

    Использование функции Эйлера

    Определение
    Классы вычетов по модулю n, элементы которых взаимно просты с n, называется приведенными классами Z*n,
    любая система чисел, взятых по одному из каждого приведенного класса, называется приведенной системой вычетов.

    Приведенная система вычетов состоит из φ(n) элементов, где φ(n) = |Z*n| - функция Эйлера, указывающая количество чисел в множестве 1, ... , n-1, взаимно простых с n.
    Теорема Эйлера.
    Если а и n взаимно просты, то
    aφ(n) ≡ 1 (mod n).
    Т. о. для определения обратного вычета достаточно знать количество элементов в приведенной системе вычетов φ(n) = |Z*n|
    aφ(n) ≡ 1 (mod n).
    a * aφ(n)-1 ≡ 1 (mod n).
    a-1 = aφ(n)-1 (mod n).
    Пример: a=5; n=18.
    Z*n = {1, 5, 7, 11, 13, 17}.
    φ(n) = |Z*n| = 6
    a-1 = aφ(n)-1 = 55 = 5*5*5*5*5 = 25*25*5 ≡ 7*7*5 = 49*5 ≡ 13*5 = 65 ≡ 11 (mod n).

    Если n = p- простое число, то φ(p) = p-1
    Малая теорема Ферма
    aφ(p)-1 ≡ 1 (mod p).
    Тогда a-1 = ap-2 (mod n).
    Пример: a=7; n=19.
    7-1 = 717 = (7*7)8*7 = 498*7 ≡ 118*7 = 1214*7 ≡ 74*7 = 492*7 ≡ 112*7 = 121*7 ≡ 7*7 = 49 ≡ 11 (mod 19).
    Проверка: 7*11 = 77 = 76 +1 ≡ 1 (mod 19).

    [Список тем] [Вступление к этой теме] Страницы темы: [1] [2]