Галуа Ч.1: Классы вычетов и группы / Хабр

Мотивация

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

Далее в нескольких статьях я опишу путь от основ абстрактной алгебры до изоморфизма конечных полей:

Галуа Ч.1: Классы вычетов и группы.
Галуа Ч.2: Кольца и поля. Конечные поля вида .
Галуа Ч.3: Конечные поля вида . Изоморфизм конечных полей.

Почему мы сразу не рассматриваем конечные поля?

Основу современной криптографии составляют различные алгебраические стуктуры и методы, и каждая следующая структура строится на основе предыдущей. Поэтому довольно тяжело будет рассмотреть структуру конечных полей, предварительно не изучив свойства групп. Базовое понимание этих структур необходимо для освоения даже самых популярных протоколов таких, как RSA и обмен ключами Диффи-Хеллмана. В своем изложении я ограничусь только формулировкой необходимых определений и теорем, а также постараюсь пояснить сложные моменты и привести характерные для криптографии примеры.

Скрытый текст

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

Сагалович Ю.Л. Введение в алгебраические коды: учебное пособие / Ю. Л. Сагалович. М-во обра- зования и науки Российской Федерации, Учреждение Российской акад. наук Ин-т проблем передачи информ. им. А. А. Харкевича РАН. - 3-е изд., перераб. и доп. - Москва: ИППИ РАН, 2014. - 310 с.
Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы. - М.: КомКнига, 2006. - 328с.

Структура статьи

Классы вычетов.
Группы. Вероятностный алгоритм поиска образующего элемента циклической группы.
Автоматизация вычисления с помощью SageMath.

Классы вычетов

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

Скрытый текст

Отношение эквивалентности на множестве- это бинарное отношение , которое удовлетворяет следующим условиям для любых элементов :

рефлексивность:
симметричность: если , то и
транзитивность: если и , то

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

На множестве целых чисел $\mathbb{Z}$ можно определить отношение эквивалентности

$x \equiv y \pmod{m}$

, где - натуральное число. Это отношение называется отношением сравнимости ("равенства") по модулю , а классы эквивалентности по этому отношению - классами вычетов по модулю .

Скрытый текст

Говорят, что два целых числа и сравнимы по модулю , если их разность делится на (иначе говоря, и дают при делении на одинаковые остатки).

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

Скрытый текст

Класс вычетов можно представить как множество $[x]_m = \{ x + km, \: k \in \mathbb{Z} \}$ .

Пример. Рассмотрим класс вычетов по модулю 6 (). Так как $4 \equiv 10 \equiv -2 \: (\textrm{mod} \: 6)$ (4, 10 и -2 дают одинаковый остаток при делении по модулю 6 равный 4), то они принадлежат одному и тому же классу вычетов. Мы этот класс вычетов можем обозначить как , , , но для удобства будем всегда в качестве представителя брать наименьшее неотрицательное число из данного класса, т.е. для нашего примера.

Совокупность всех классов вычетов на множестве целых чисел $\mathbb{Z}$ по модулю обозначают $\mathbb{Z}_m$ . Множество $\mathbb{Z}_m$ содержит элементов: классов вычетов, так как при делении с остатком на число , остаток может принимать значения из множества $\{0, 1, . . . , m − 1\}$ .

Пример. Рассмотрим множество $\mathbb{Z}_6$ классов вычетов по модулю 6. Тогда $\mathbb{Z}_6 = \{ [0]_6, [1]_6, [2]_6, [3]_6, [4]_6, [5]_6 \}$ .

На множестве $\mathbb{Z}_m$ можно определить арифметическим операции. Сумму классов вычетов определяют следующим образом:

Если в качестве представителей классов брать наименьшие неотрицательные числа $x \: \textrm{mod} \: m$ , принадлежащие соответствующему классу, то формула принимает более удобный вид:

$[x]_m + [y]_m = [(x + y) \: \textrm{mod} \: m]_m$

Скрытый текст

Тогда - нейтральный элемент по сложению, а - противоположный.

Аналогично вводится и операция умножения:

$[x]_m \cdot [y]_m = [x \cdot y]_m = [(x \cdot y) \: \textrm{mod} \: m]_m$

Скрытый текст

Тогда - нейтральный элемент по умножению, а $[x^{-1}]_m : x \cdot x^{-1} \: \textrm{mod} \: m = 1$ - обратный. Обратите внимание, $[x^{-1}]_m$ также является классом вычетов и, соответственно, его представители - целые числа.

Пример. Рассмотрим . Тогда $[4^{-1}]_7 = [2]_7$ , так как $4 \cdot 2 \: \textrm{mod} \: 7 = 1$ .

В случае, когда по контексту понятно, о каких классах вычетов идет речь, я буду указывать класс как , без указания числа . Также, в арифметических операциях удобно использовать представителей классов вычетов, операции над которыми осуществляются по модулю , без указания самих классов. Я буду в основном придерживаться последнего подхода.

Пример. Рассмотрим множество $\mathbb{Z}_6 = \{ [0]_6, [1]_6, [2]_6, [3]_6, [4]_6, [5]_6 \}$ классов вычетов по модулю 6.

$[4]_6 + [5]_6 = [9]_6 = [9 \: \textrm{mod} \: 6]_6 = [3]_6$ $[4]_6 \cdot [5]_6 = [20]_6 = [20 \: \textrm{mod} \: 6] = [2]_6$

Используя наименьших неотрицательных представителей классов, можно представить множество $\mathbb{Z}_6$ как $\{ 0, 1, 2, 3, 4, 5 \}$ . Тогда

$4 + 5 = 9 \equiv 3 \: (\textrm{mod} \: 6)$ $4 \cdot 5 = 20 \equiv 2 \: (\textrm{mod} \: 6)$

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

Группы

Группа - это непустое множество элементов, на котором задана операция , результат которой также принадлежит этой группе. Элементы группы обладают большинством свойств, к которым мы привыкли при работе с "обычными" (вещественными) числами, за одним важным исключением: без дополнительных оговорок порядок элементов в операции важен, от перемены мест слагаемых результат может измениться. Если результат операции в группе не зависит от порядка элементов, такая группа называется коммутативной (или абелевой).

Скрытый текст

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

Скрытый текст

Пусть - непустое множество, на котором задана бинарная операция $(x, y) \rightarrow x*y$ , результат которой также принадлежит группе ( $*: G \times G \rightarrow G$ , говорят, что группа замкнута относительно данной операции).

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

Для любых трех элементов $x, y, z \in G$ выполняется равенство: . В этом случае говорят, что операция обладает свойством ассоциативности.
Существует нейтральный элемент (единица группы) $e \in G$ такой, что для любого элемента $x \in G$ выполняется равенство:
Для любого элемента $x \in G$ существует единственный элемент $y \in G$ такой, что: . Элемент называется обратным к элементу .
Если, кроме того, множество обладает 4 свойством: для любых $x, y \in G$ , тогда группа называется коммутативной (или абелевой).

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

Обычно, в качестве операции используются привычные операции умножения и суммирования. В случае суммы операция обозначается привычным знаком , обратный элемент к элементу обозначается как и называется противоположным, а нейтральным элементом является 0. Тогда требования к группе можно записать в следующем виде:

для любых $x, y, z \in G$ (можем раскрывать, менять и добавлять скобки по привычным нам правилам)
существует элемент $0 \in G$ такой, что (прибавление нейтрального элемента - нуля - не изменяет элемент )
для любого $x \in G$ существует элемент такой, что (существует противоположный элемент, аналог отрицательного числа)

В этом случае группа называется аддитивной или группой по сложению.

Определим еще одну важную операцию - скалярное умножение элемента аддитивной группы на натуральное число :

$n \cdot x = \underbrace{x + x + \dots + x}_{n}$

Тогда

$-n \cdot x = \underbrace{(-x) + (-x) + \dots + (-x)}_{n} = -1 \cdot (n \cdot x) = n \cdot (-x)$ $0 \cdot x = 0 = x \cdot 0$

И, соответственно, для любых целых чисел

$m \cdot x + n \cdot x = (m + n) \cdot x$

Скрытый текст

Если вам пока не совсем понятно, зачем вообще формализовывать такие привычные операции, как сложение и умножение, - не спешите. Позже мы перейдём к конечным полям, где работать придётся уже не только с числами, но и с многочленами, векторами и даже векторами векторов. Без строгих правил удержать всё это в голове и не допускать ошибок будет очень сложно.

В случае произведения операцию обозначают через $\cdot$ , или знак операции не пишут вовсе, обратный элемент обозначается как $x^{-1}$ , а нейтральным элементом является 1. Требования к группе можно записать в следующем виде:

для любых $x, y, z \in G$ $x \cdot (y \cdot z) = (x \cdot y) \cdot z$
существует элемент $1 \in G$ такой, что $x \cdot 1 = x = 1 \cdot x$
для любого $x \in G$ существует элемент $x^{-1}$ такой, что $x \cdot x^{-1} = 1 = x^{-1} \cdot x$

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

Определим возведение в натуральную степень элемента мультипликативной группы следующим образом:

$x^n = \underbrace{x \cdot x \cdot \, \dots \, \cdot x}_{n}$

Тогда

$x^{-n} = \underbrace{x^{-1} \cdot x^{-1} \cdot \, \dots \, \cdot x^{-1}}_{n} = (x^n)^{-1} = (x^{-1})^n$

И, соответственно, для любых целых чисел :

$x^m \cdot x^n = x^{m + n}$

Скрытый текст

Пример. Различные примеры групп всем знакомы со школы:

Множество целых чисел $\mathbb{Z}$ является группой по сложению. Это легко проверить, все привыкли пользоваться свойствами группы, для целых чисел они кажутся естественными. Более того, целые числа являются абелевой группой. Однако это множество не является группой по умножению, так как только два элемента среди целых чисел имеют обратные: $\pm 1$ . Чтобы различать группы по сложению и умножению относительно одного и того же множества, мы будем указывать рассматриваемую операцию справа сверху от символа множества, например, $\mathbb{Z}^+$ - группа целых чисел по сложению, $\mathbb{Z}^*$ - группа целых чисел по умножению. Тогда $\mathbb{Z}^+ = \mathbb{Z}$ , $\mathbb{Z}^* = \{ \pm 1 \}$ .
Множество натуральных чисел $\mathbb{N}$ не является группой по сложению, так как для элементов не существует противоположных.
Все ненулевые элементы множества рациональных чисел образуют группу по умножению $\mathbb{Q}^* = \mathbb{Q} \backslash \{ 0 \}$ .
Все ненулевые элементы множества вещественных чисел образуют группу по умножению $\mathbb{R}^* = \mathbb{R} \backslash \{ 0 \}$ .
Все четные числа образуют группу по сложению. Множество четных числе можно представить как $\{ 2n | \: n \in \mathbb{Z} \}$ . Тогда ноль входит в эту группу и является нейтральным элементом, сумма четных чисел четна, а противоположным к элементу является элемент . В общем случае, любое подмножество целых чисел, представимое в виде $m\mathbb{Z} = \{m \cdot n | \: n \in \mathbb{Z}\}$ , образует группу по сложению.

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

Подмножество элементов группы называется подгруппой группы , если оно само является группой.

Скрытый текст

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

Пример. Рассмотрим группу целых чисел относительно сложения $\mathbb{Z}^+$ . Возьмем ее подмножество $\mathbb{N}$ - множество всех натуральных чисел. Это подмножество не является группой по сложению, так как, как минимум, оно не содержит обратных элементов.

Количество элементов в группе называется порядком группы и обозначается через.

Группа называется конечной, если она содержит конечное количество элементов ( $|G| < \infty$ ), иначе группа называется бесконечной ( $|G| = \infty$ ).

Далее будем рассматривать только конечные группы. Пусть - конечная мультипликативная группа, - элемент группы . Рассмотрим последовательность элементов $1, g, g^2, g^3, g^4, \dots$ Так как группа конечна, то очевидно, что, начиная с некоторой степени, элементы начнут повторяться. Следовательно, существует натуральное число такое, что .

Скрытый текст

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

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

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

И именно к решению этой задачи мы, в том числе, совсем скоро и придём в нашем повествовании

Группа, все элементы которой являются степенями какого-то элемента $g \in G$ называется циклической подгруппой группы и обозначается $\langle g \rangle$ . Говорят, что циклическая подгруппа $\langle g \rangle = \{ g^n | \: n \in \mathbb{Z} \}$ порождена элементом , - образующий элемент (генератор) этой циклической подгруппы. Группа называется циклической, если существует элемент такой, что $\langle g \rangle = G$ . Все циклические группы абелевы. Наименьшее натуральное число такое, что , называется порядком элемента и обозначается $\textrm{ord}(g) = n$ ( $\textrm{ord}(g) = \infty$ , если такого не существует).

Скрытый текст

Пример. Вернемся к рассмотренным раннее классам вычетов. Важным примером конечной циклической группы, которая активно используется в криптографии, является группа классов вычетов $\mathbb{Z}_n$ по модулю натурального числа . Множество $\mathbb{Z}_n$ является группой по сложению, нейтральным элементов является класс вычетов , а образующим элементом - .

Легко проверить, что множество классов вычетов обладает всеми свойствами группы по сложению. Однако множество $\mathbb{Z}_n$ не является группой по умножению. В группу по умножению $\mathbb{Z}_n^*$ входят все обратимые элементы множества $\mathbb{Z}_n$ . Элемент не имеет обратного для любого натурального числа, поэтому его надо исключить из группы по умножению. Более того, не при любых значенияхвсе остальные элементы множества $\mathbb{Z}_n$ будут иметь обратные. Забегая вперед, скажем, что все ненулевые элементы множества $\mathbb{Z}_n$ являются элементами группы $\mathbb{Z}_n^*$ тогда и только тогда, когда - простое число.

Теорема. Пусть $G = \langle g \rangle$ - циклическая группа. Тогда любая подгруппа группы тоже циклическая.
Теорема (Лагранжа). Порядок и индекс подгруппы делят порядок группы.

Мы не будем вдаваться в подробности и определять понятие индекса подгруппы. Для нас будут больше важны следствия из этой теоремы:

Порядок любого элемента конечной группы делит порядок группы.
Для любого элемента конечной группы порядкаимеет место равенство: .
Если - порядок элемента $a \in G$ , , то тогда и только тогда, когда делит .

Теорема. Пусть - группа (не обязательно циклическая), $g \in G$ , $\mathrm{ord}(g) = n$ . Тогда,

$\mathrm{ord}(g^m) = \frac{n}{\text{НОД}(n, m)}$

, где $m, n \in \mathbb{Z}$ , - наибольший общий делитель чисел и .

Пусть $G = \langle g \rangle$ - циклическая группа, $|G| = \textrm{ord}(g) = |\langle g \rangle| = n$ . Сколько элементов таких, что $\langle g^m \rangle = G$ , где - целое число? (Сколько образующих у конечной циклической группы порядка ?)

Так как $g^m \in G$ :

$|\langle g \rangle| = \textrm{ord}(g^m) = \frac{n}{\textrm{НОД}(n, m)}$

Тогда если $\langle g^m \rangle = G$ , то:

$\frac{n}{\textrm{НОД}(n, m)} = n \Leftrightarrow \textrm{НОД}(n, m) = 1$

Следовательно, и должны быть взаимно простыми. Т.е. у конечной циклической группы порядка столько образующих элементов, сколько чисел $1 \leq m \leq n - 1$ таких, что $\textrm{НОД}(n, m) = 1$ .

Скрытый текст

И именно здесь в повествовании начинают появляться простые числа, которые теперь будут сопровождать нас всё оставшееся время, пока мы изучаем конечные поля. Возможно, вы уже слышали, что криптография тесно связана с большими простыми числами и что математики и программисты постоянно занимаются их поиском. Это не случайность, и по мере изучения конечных полей станет понятно, почему именно простые числа оказываются настолько важны и какую роль они играют в построении криптографических систем.

И тут нам окажется крайне полезна функция Эйлера.

Функция Эйлера $\varphi(n)$ - функция, значение которой равно количеству натуральных чисел, которые меньше и взаимно просты с ним.

Таким образом, конечная циклическая группа порядка содержит ровно $\varphi(n)$ образующих. Кроме того, если целое число делит порядок группы , то в группе существует единственная подгруппа порядка .

Функция эйлера обладает свойством мультипликативности: $\varphi(mn) = \varphi(m) \cdot \varphi(n)$ .

Если число - простое, то все числа меньше взаимно просты с ним, следовательно $\varphi(p) = p - 1$ . Рассмотрим число , где - простое, - натуральное. Тогда среди натуральных чисел, меньших , не взаимно просты с только числа, кратные , т.е. $p, 2p, 3p, \dots, p^{n-1}p$ . Всего таких чисел $p^{n - 1}$ . Следовательно, $\varphi(p^n) = p^n - p^{n - 1}$ .

Теорема (Основная теорема арифметики). Любое натуральное число представимо единственным образом в виде $n = p_1^{d_1} \cdot p_2^{d_2} \cdot \: \dots \: \cdot p_k^{d_k}$ , где $p_1 < p_2 < \dots < p_k$ - простые числа, - натуральные, $i = 1, \dots, k$ . Такое представление числа называется каноническим разложением на простые сомножители.

Тогда, используя свойство мультипликативности функции Эйлера и основную теорему арифметики, для произвольного натурального числа

$\varphi(n) = n \prod_{p | n} \bigg( 1 - \frac{1}{p} \bigg)$

, где - простое число, которое принимает все значения из разложения на простые сомножители.

Теорема (Эйлера). Для любого натурального и любого натурального такого, что , справедливо отношение

$a^{\varphi(n)} \equiv 1 \: (\mathrm{mod} \: n)$

Частным случаем теоремы Эйлера является малая теорема Ферма.

Теорема (Малая теорема Ферма). Для любого простого числа и для любого целого числа , не кратного , справедливо отношение

$a^{p - 1} \equiv 1 \: (\mathrm{mod} \: p)$

Таким образом, возведение в большую степень элемента конечной циклической группы , $\textrm{ord}(g) = m$ , можно упростить:

$g^n = g^{n \: \textrm{mod} \: m}$

Поэтому представлять элементы в виде степеней образующего элемента группы довольно удобно. Теорема Эйлера активно используется в криптографии. Пусть $x, y \in \{ 1, \dots, m - 1 \}$ такие, что $x \cdot y = 1 \: (\textrm{mod} \: m)$ . И пусть $h = g^k, k \in \{ 0, 1, \dots, m - 1 \}$ . Тогда

$(h^x)^y = h^{xy} \equiv h^1 = h$

Найти числа можно также по теореме Эйлера:

$x \cdot y = 1 \: (\textrm{mod} \: m) \implies y = x^{-1} \equiv x^{\varphi(m) - 1} \: (\textrm{mod} \: m)$

Таким образом, образующие элементы активно используются на практике, особенно в криптографии.

Скрытый текст

Осталось потерпеть совсем немного - с основной теорией мы почти закончили и уже совсем скоро перейдём к практике.

Приведем вероятностный алгоритм поиска образующего элемента циклической группы.

Алгоритм.
Вход: порядок циклической мультипликативной группы , разложение на простые сомножители $n = p_1^{d_1} \cdot p_2^{d_2} \cdot \: \dots \: \cdot p_k^{d_k}$ , где - разные простые числа, - натуральные, $i = 1, \dots, k$ ;
Выход: образующий элемент $g \in G$ ;
выбрать случайный элемент $g \in G$
для $i \leftarrow 1$ до :
$b \leftarrow g^{n / p_i}$
если , то перейти к 1
вернуть

Пояснение к алгоритму. Порядок любого элемента группы делит порядок группы, поэтому перебираем делители порядка группы вида . Если $g^{n / p_i} = 1$ , то существует число $m \in \{ 1, 2, \dots, d_i \}$ такое, что $g^{n / p_i^m} = 1$ . Так как делит , то

$g^{n / p_i} = (g^{n / p_i^m})^{p_i^{m-1}} = 1^{p_i^{m-1}} = 1$

И наоборот, если $g^{n / p_i} \neq 1$ , то $g^{n / p_i^m} \neq 1$ для любого $m \in \{ 1, 2, \dots, d_i \}$ .

Эффективность алгоритма определяется тем, что группа содержит $\varphi(n)$ образующих элементов, следовательно, вероятность того, что случайно выбранный элемент является образующим, равна $\varphi(n) / n$ . Для этого отношения было доказано следующее свойство:

$\frac{\varphi(n)}{n} > \frac{1}{e^{\gamma} \ln \ln n + 2.50637 / \ln \ln n }$

для $n \geq 3$ , где $\gamma$ - постоянная Эйлера. Более того, если взять в качестве большое простое число, это отношение будет близко к единице.

Скрытый текст

Соотношение выше было взято из Rosser J.B., Schoenfeld L. Approximate formulas for some functions of prime numbers. 1962. Illinois J. Math. 6 (1): 64–94. Theorem 15.

Если алгоритм используется в мультипликативной группе вычетов по модулю простого числа $\mathbb{Z}_p^*$ , то его эффективность можно повысить. Для этого необходимо выбрать число , где - простые числа, - относительно небольшое натуральное число. Числа вида называются безопасными простыми числами (обычно, ). При таком выборе числа разложение на простые сомножители порядка группы $| \mathbb{Z}_p^* | = p - 1$ является тривиальной задачей: . При

$\varphi(p - 1) = \varphi(rq) = \varphi(2) \cdot \varphi(q) = \varphi(q) = q - 1$

Тогда вероятность того, что случайно выбранный элемент $g \in \mathbb{Z}_p^*$ является образующим элементом, равна

$\frac{\varphi(n)}{n} = \frac{q - 1}{2q} \approx \frac{1}{2}$

Скрытый текст

Почитать про безопасные простые числа можно в T. Agoh. On Sophie Germain primes, Tatra Mt. Math. Publ. 20(65) (2000), pp. 65-73.

Автоматизация вычисления с помощью SageMath

Скрытый текст

SageMath - это свободная математическая программная система с открытым исходным кодом, распространяемая по лицензии GPL.

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

Для этого здесь и в последующих статьях я буду использовать SageMath. Вы можете установить данное ПО локально по инструкции либо использовать платформу CoCalc. Я воспользовался вторым вариантом, так как на платформе CoCalc есть возможность создать Jupyter Notebook и использовать его бесплатно без доступа в интернет. Нам доступ в интернет и не понадобится.

Реализация вероятностного алгоритма поиска образующего элемента циклической группы:

from sage.all import *

# выбираем простое число
prime = 6053
# создаем группу классов вычетов Zp
G = Integers(prime)

# вероятностный алгоритм поиска образующего элемента группы
def find_primitive_element(G):
    # вычисляем порядок группы по умножению
    multiplicative_order = euler_phi(G.order())
    
    # получаем простые делители порядка мультипликативной группы
    divisors = prime_divisors(multiplicative_order)
    while True:
        g = G.random_element()
        if g == 0:
            continue

        for d in divisors:
            if g**(multiplicative_order / d) == 1:
                break
        else:
            return g

g = find_primitive_element(G)
print(g)
assert g.multiplicative_order() == euler_phi(prime) # prime - 1

И что вам делать с этой информацией?

В этой статье мы познакомились с базовыми конструкциями, которые будем активно использовать в дальнейшем. И пусть пока материал мог показаться довольно теоретическим, очень скоро станет понятно, зачем всё это было нужно: практически каждое из рассмотренных понятий всплывает при работе с конечными полями.

В следующей статье мы перейдём к понятиям кольца и поля, а затем начнём работать уже непосредственно с конечными полями. Рассмотрим поля вида в общем случае, а также подробно разберём поля и . Построим их вручную, выполним основные вычисления и посмотрим, как автоматизировать всю эту работу с помощью SageMath.

Спасибо за уделённое время! Если тема оказалась вам интересна - следите за выходом следующих статей.