Аддитивные и мультипликативные группы остатков

Разбить на страницы

Показывать лекцию целиком

В этой лекции мы будем изучать сложение и умножение остатков с позиций теории групп.

Множество $$Z_m$$остатков после деления на m формирует группу с операцией сложения, а число 0 является тождественными элементом группы. Фактически эта группа является циклической с генератором 1, так как каждый остаток k в этой группе может быть выражен как сумма из k единиц: 1+1+. . . + 1. Порядок элемента 1 в $$Z_m$$ равен m, так как сумма из m единиц в $$Z_m$$ равна тождественному элементу 0.

Рассмотрим в качестве примера группу $$Z_{10}$$. В этой группе элемент 2 имеет порядок 5, так как 2 + 2 + 2 + 2 + 2 = 0 mоd 10, в то время как порядок 3 равен 10, поскольку 10- наименьший множитель для 3, который дает остаток 0 для произведения 30 = 10 х 3 = 3+3+3+3+3+3+3+3+3+3. Следующая таблица перечисляет порядки элементов в $$Z_{10}$$o

`x`	0	1	2	3	4	5	6	7	8	9
Порядок `x`	1	10	5	10	5	2	5	10	5	10

Заметьте, в согласии с теоремой Лагранжа порядок каждого элемента является делителем числа 10, которое задает порядок группы $$Z_{10}$$.

В общем случае порядок выражается через наименьшее общее кратное (НОК) и наибольший общий делитель (НОД).

Утверждение. Порядок элемента k в аддитивной группе $$Z_M$$задается формулами:

$$\frac{HOK(m,k)}{k}=\frac{m}{HOД(m,k)}$$

Доказательство. Пусть r - порядок k в $$Z_m$$. Это означает, что rk является наименьшим кратным k, которое делится на m. Отсюда следует, что rk является наименьшим общим кратным k и m - НОК(m, k), что и доказывает наше утверждение.

Далее мы рассмотрим мультипликативную структуру $$Z_m$$. Понятно, что $$Z_m$$ не является группой по отношению к операции умножения, хотя бы потому что 0 не имеет обратного элемента, но и другие остатки могут быть необратимы.

Определение. Остатки а и b в $$Z_m$$ мультипликативно взаимно обратимыми, если аb = 1 mod n.

Например, в $$Z_{10}$$элементы 3 и 7 мультипликативно взаимно обратимы, так как 3 х 7 = 1 тод 10, в то время как четные числа или число 5 в го необратимы, поскольку нет таких остатков b, чтобы 2b = 1 или 5b = 1 mod 10.

Определение. Мультипликативная группа $$Z_m^*$$- это множество обратимых остатков по модулю m.

Очевидно, что множество мультипликативно обратимых остатков образует группу, поскольку произведение обратимых остатков обратимо: $${ab}^{-1}=b^{-1}a^{-1}$$

Как же определить, какие остатки мультипликативно обратимы? Мы собираемся показать, что остаток k обратим в $$Z_m$$, если и только если НОД(m, k) =1.

Доказательство этого факта, также как и общий метод вычисления обратных элементов, основано на алгоритме вычисления наибольшего общего делителя, восходящего еще к Эвклиду Давайте обсудим алгоритм Эвклида.

Один из способов вычисления НОД(m, k) состоит в разложении чисел m и k на простые множители. Например, для вычисления НОД(96, 60) мы можем оба числа представить как произведение простых чисел:

96=2*2*2*2*2*3, 60=2*2*3*5.

Произведение общих простых делителей дает наибольший общий делитель, так что НОД(96, 60) = 22 * 3 = 12.

Этот метод, однако, становится неэффективным, когда числа имеют большие простые делители. Давайте, например, попытаемся вычислить НОД(4187, 2923). Разложение этих чисел на простые делители - их факторизация - потребует усилий, если делать это вручную. Для очень больших чисел при таком способе факторизации не поможет и компьютер. Фактически безопасность криптосистем RSA, которая ниже будет обсуждаться, основана в точности на том факте, что факторизация больших целых является сложной задачей.

С вычислением НОД(m, k) все обстоит по-другому. Благодаря Эвклиду, можно эффективно вычислять НОД даже для очень больших чисел m и k.

Идея алгоритма Эвклида основана на том факте, что НОД(а, b) = НОД(а - b, b). Эвклид доказал, что если d - делитель а и b, то d - делитель а - b. Идею Эвклида можно обобщить, вычитая b из а произвольное число раз.

Утверждение. Разделим а на b с остатком: а = sb + r, где $$0 \le r < b$$. Тогда НОД(а, b) = НОД(b, r).

Применим утверждение к выше приведенному примеру:

НОД(4187, 2923) = НОД(2923,1264).

Повторяя этот процесс, получим:

4187 - 2923 = 1264                       НОД(4187, 2923) = НОД(2923,1264) 
2923 - 2 х 1264 = 395                   НОД(2923,1264) = НОД(1264, 395) 
1264 - 3 х 395 = 79                       НОД(1264, 395) = НОД(395, 79)
395 - 5 х 79 = 0                             НОД(395, 79) = 79.

Это говорит нам, что НОД(4187, 2923) = 79.

Если выполнять вычисления в алгоритме Эвклида в обратном порядке, то можно получить следующий важный результат:

Теорема. Пусть НОД(а, b) = d. Тогда существуют цельте u и v, такие что

$$d=au+bv$$

В применении к нашему примеру теорема говорит, что существуют целые u и v, такие что 4187u + 2923v = 79 (ясно, что одно из целых должно быть отрицательным). Не очевидно, каковы значения u и v. Для их получения можно запустить вычисления по алгоритму Эвклида в обратном порядке:

79= 1264-3 х 395
= 1264-3 х (2923-2 х 1264) = 7 х 1264-3 х 2923 
= 7 х (4187-2923) -3 х 2923 = 7 х 4187-10 х 2923,

Теперь мы можем доказать следующее:

Теорема. Остаток k имеет мультипликативный обратный элемент в $$Z_M$$, если и только если НОД(m, k) = 1.

Доказательство. Предположим, что НОД(m, k) = 1. По предыдущей теореме существуют целые u и v, такие что 1 = mu + kv. Так как mu = 0 тод т, то kv = 1 тод m, а это значит, что v является мультипликативным обращением k в $$Z_m$$

Для доказательства утверждения в другую сторону предположим, что v является мультипликативным обращением k в $$Z_m$$. Тогда kv = 1 mod m. Два целых имеют одинаковые остатки по модулю m, если их разность делится на m. Так что kv - 1 = ms для некоторого s и kv-ms= 1. Если d -общий делитель k и m, то он также является делителем kv-ms, откуда следует, что d -делитель единицы и равен 1. Но тогда единственным общим делителем k и m является 1. Это и означает, что НОД(m, k) = 1.

Существует важный специальный случай, когда модулем является простое число р. Можно видеть, что в $$Z_p$$ каждый ненулевой остаток имеет мультипликативный обратный элемент, так что содержит р - 1 элемент.

Теорема (Малая теорема Ферма). Пусть р - простое число. Если а целое, не делящееся на р, то

$$а^{р-1} = 1\; mod\; р.$$

Доказательство. Применим теорему Лагранжа к мультипликативной группе $$Z_p^*$$. Так как порядок этой группы равен р -1, то для каждого элемента а в $$Z_h^*$$ имеем $$а^{р-1}=е$$, что в точности совпадает с утверждением теоремы.

Рассмотрим в качестве примера р = 13. Давайте определим порядок элемента g = 2 в $$Z_{13}^*$$

$$2^1=2\; 2^4=3\; 2^7=11\; 2^{10}=10\\ 2^2=4\; 2^5=6\; 2^8=9\; 2^{11}=7\\ 2^3=8\; 2^6=12\; 2^9=5\; 2^{12}=1$$

Следовательно, порядок элемента g = 2 в $$Z_{13}^* = 12$$, это также говорит нам, что $$Z_{13}^*$$ - циклическая группа порядка 12 с генератором 2. Мы можем вычислить порядки всех элементов в $$Z_{13}^*$$. Так как $$3 = 2^4$$, а $$2^{12} = 1$$, то порядок 3 равен З.

Определение. Изоморфизм двух групп - это взаимно-однозначное соответствие между элементами, сохраняющее групповые операции.

Функция $$f (х) = 2^х$$ является изоморфизмом между аддитивной группой $$Z_{12}$$ и мультипликативной группой $$Z_{13}^*$$. Она сохраняет групповые операции, так как $$2^{х+у} = 2^х * 2^y$$.

Мы собираемся установить без доказательства следующий результат:

Теорема. Пусть р - простое число. Группа $$Z_p^*$$ имеет циклический генератор g, такой, что степени g исчерпывают $$Z_p^*$$. Функция f(х) =gх является изоморфизмом между $$Z_{p-1}$$ и $$Z_p^*$$.

Не существует общего правила, указывающего какой элемент $$Z_p^*$$ является циклическим генератором. Более того, когда g задано, то функция $$f (х) = g^x$$ является функцией ловушкой (trар-door function) в случае, когда р - большое простое число. Эту функцию просто вычислить, но трудно вычислить обращение f , которое дает остаток h в $$Z_p^*$$, то есть трудно найти такое целое х, для которого $$h = g^x\; mod\; р$$. Так как f - экспоненциальная функция, то ее обращение представляет дискретно логарифмическую функцию: $$х = \log_g(h)$$.

Конечно, можно попытаться организовать полный перебор, но для больших простых чисел эта задача вычислительно невыполнима.

Существует несколько широко используемых криптосистем, основанных на предположении, что дискретная логарифмическая функция трудно вычислима.

В заключение этой лекции:

Теорема (Китайская теорема об остатках). Если НОД(m, s) = 1, то для любой пары остатков а mod m, b mod s существует уникальный остаток х mod ms, такой что х = а mod т и х = b mod s.

Пример. Система

$$\left \{ \begin{aligned} x=2 \;mod\; 7\\ x=5 \;mod\; 8 \end{aligned} \right$$

имеет единственное решение в $$Z_{56}/ x = 37$$ (В данном примере: а = 2, b = 5, m = 7, s = 8, u = -1, v = 1. Откуда x =asv +bmu = 16-35 = -19 = 37 mod 56)

Доказательство. Так как НОД(m, s) = 1, то существуют u, v, такие что mu + sv = 1. Очевидно:

$$mu\; mod\; m=0,\; sv\; mod\; s=0$$

Тогда из равенства mu + з = 1 следует:

$$su\; mod\; m=1,\; mu\; mod\; s=1 $$

Сконструируем решение х следующего вида: х =asv +bmu mod ms. Проверим, что эта формула дает желаемый результат:

$$х\; mod\; m = а * 1 + b * 0\; mod\; m = а\; mod\; m,\\ х\; mod\; s= а * 0+ b * 1\; mod\; s= b\; mod\; s.$$

Так как число пар остатков (а mod m, b mod s) совпадает с числом остатков в $$Z_{ms}$$, то решение будет единственным.

Следствие. Предположим НОД(m, s) = 1. Остаток k обратим в $$Z_{ms$$, если и только если k mod m обратим в $$Z_m$$ и k mod s обратим в $$Z_s$$.

Следствие. Предположим, что р, q - два простых числа и $$р \ne q$$. Тогда порядок группы $$Z_{pq}^*$$ равен (р - 1) (q - 1).

Применяя теорему Лагранжа, получаем аналог малой теоремы Ферма, которая используется в РSА криптосистеме:

Теорема. Предположим, что р, q - два простых числа и $$р\ne q$$. Если g не делится ни на р, ни на q, то:

$$g^{(p-1)(q-1)}=1\; mod\; pq$$

Страницы: