Как найти порядок элемента в кольце

I think this is a matter of the rigor of definitions. Strictly speaking, $16$ is NOT an element of $mathbb{Z}_5$, which as a set is ${0,1,2,3,4}$. Strictly speaking, we have a surjective homomorphism of rings $pi:mathbb{Z}rightarrowmathbb{Z}_5$ sending a number to its remainder modulo $5$, i.e., when dividing by $5$: $pi(n):=r$ where $n=5q+r$.

So, strictly speaking we have $pi(2^4)=pi(16)=pi(5cdot 3+1)=1$ (in $mathbb{Z}_5$), and also $2^4=pi(2)^4=1$ in $mathbb{Z}_5$ (since $pi$ is a homomorphism such that $pi(2)=2$), which we can write also as $2^4equiv 16equiv 1pmod{5}$, where now $equivpmod{5}$ is an equivalence relation for $mathbb{Z}$. Nevertheless it is usual, but an abuse of notation, to write $16=1$ in $mathbb{Z}_5$.

3.1.5 Конечные кольца и поля

Определение 3.18 Множество с двумя алгебраическими операциями , называется ассоциативным кольцом, если в нём выполняются свойства:

1. является коммутативной группой по сложению с нейтральным элементом (эта группа называется аддитивной).
2. является полугруппой (обозначается ).
3. Дистрибутивность: и .

Определение 3.19 Кольца и называются изоморфными, если существует отображение , являющееся изоморфизмом аддитивных и мультипликативных групп этих колец.

Определение 3.20 Полем называется кольцо , в котором является коммутативной группой.

Определение 3.21 Характеристикой поля называется наименьшее такое натуральное число , что , или 0, если такого не существует. Характеристика поля может быть только простым числом или нулем.

Определение 3.22 Левым (правым) идеалом кольца называется любое его подкольцо, выдерживающее умножение слева (соответственно, справа) на любой элемент кольца. Подкольцо, являющееся левым и правым идеалом, называется двусторонним идеалом, или просто идеалом.

Подкольцо разбивает кольцо на классы эквивалентности: . Класс, содержащий элемент , можно записать в виде:

Если подкольцо является идеалом, то на множестве таких классов можно ввести операции сложения и умножения, относительно которых множество классов образует кольцо, называемое фактор-кольцом:

Из определения идеала следует, что результат операций не зависит от выбора представителей , , то есть операции заданы корректно.

Наиболее важными для нас будут следующие кольца и поля:

1. Кольцо целых чисел относительно обыкновенных операций сложения и умножения.
2. Поле рациональных чисел относительно операций сложения и умножения.
3. Фактор-кольцо кольца целых чисел по идеалу всех чисел, кратных . Также это кольцо можно себе представлять, как кольцо целых неотрицательных чисел, меньших , с операцией сложения и умножения по модулю . Такое кольцо является полем тогда и только тогда, когда – простое число.
4. Кольцо многочленов от переменных над произвольным полем .
5. Фактор-кольцо кольца многочленов над полем по идеалу, порожденному одним многочленом степени , то есть состоящему из всех многочленов, кратных . Это кольцо можно также рассматривать, как кольцо многочленов степени меньше с операцией сложения и умножения по модулю . Такое кольцо является полем тогда и только тогда, когда многочлен неприводим над .

В криптографии нас будут интересовать больше всего конечные поля, то есть поля с конечным множеством . Перечислим наиболее важные для нас свойства:

1. Каждое конечное поле имеет простую характеристику .
2. Поле простого порядка не имеет подполей, и называется простым.
3. Конечное поле характеристики содержит подполе порядка .
4. Конечное поле является линейным пространством над своим простым подполем, поэтому имеет порядок для некоторого натурального числа .
5. Мультипликативная группа конечного поля циклическая. Если поле имеет простой порядок , то порождающий его мультипликативную группу элемент называется примитивным корнем по модулю .
6. Конечные поля одного порядка изоморфны.

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

Пример 3.5 Найти мультипликативный порядок элемента по модулю , то есть порядок элемента мультипликативной группы .

Решение. Поскольку число 101 простое, порядок мультипликативной группы поля равен 100. По следствию из теоремы Лагранжа, мультипликативный порядок любого числа по модулю 101 является делителем 100, то есть одним из чисел: 1, 2, 4, 5, 10, 20, 25, 50, 100. Проверим каждое из чисел:

	1	2	4	5	10	20	25	50	100
	16	54	88	95	36	84	1	–	–

После того, как обнаружили, что , возводить в -ю и -ю степень излишне – видно, что наименьшая степень, в которой 16 даст единицу по модулю 101, это 25.

Пример 3.6 Найти случайный примитивный корень по модулю .

Решение. Порядок мультипликативной группы поля вычетов по модулю 883 равен . Будем выбирать случайное число и возводить его в степени , , . Если в какой-то степени даст единицу, то его порядок меньше 882, и, следовательно, он не является примитивным корнем по модулю 883. Наоборот, порядок порождающего элемента является делителем числа 882, и если он не является делителем ни одного из чисел , , , то равен 882. В первой колонке таблицы приводятся случайно выбранные элементы , а в следующих колонках – результаты возведения в степень.

Итак, 326 является примитивным корнем по модулю 883.

Понятие порядка элемента вводится не для колец, а для групп. Если дано кольцо с единицей, то с ним можно связать две группы: аддитивную (для которой в случае колец вычетов всё устроено очень просто), и мультипликативную, то есть группу обратимых элементов этого кольца. Последнюю принято обозначать в виде $%R^{ast}$%. В данной задаче речь идёт о наибольшем значении порядка элемента группы $%mathbb Z_n^{ast}$%. Если $%n=p$% простое, то группа циклична по теореме о первообразном корне, и искомое значение равно $%p-1$%.

Пусть $%n$% составное. Рассмотрим каноническое разложение $%n=p_1^{k_1}ldots p_r^{k_r}$%. Из теории известно, что группа $%mathbb Z_n^{ast}$% изоморфна прямому произведению мультипликативных групп сомножителей (это следствие китайской теоремы об остатках). То есть речь идёт о группе $%mathbb Z_{p_1^{k_1}}^{ast}timescdotstimesmathbb Z_{p_r^{k_r}}^{ast}$%.

Известно (см., например, учебник Кострикина), что для степени простого числа группа $%mathbb Z_{p^k}^{ast}$% также является циклической, и её порядок равен $%varphi(p^k)=p^{k-1}(p-1)$%. Для элементов прямого произведения, порядок равен НОК порядков компонент. Чтобы это значение было наибольшим, надо в каждой компоненте взять элемент наибольшего порядка. Это даст значение $%НОК(p_1^{k_1-1}(p_1-1),ldots,p_r^{k_r-1}(p_r-1))$%.

По данной формуле искомое значение порядка легко вычисляется. Например, при $%n=100=2^25^2$% получается $%НОК(2,20)=20$%. Можно привести список начальных значений для $%nge2$% (включая простой и составной случай): 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 2, 12, 6, 4, 8, … и так далее.