Группы

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

Основные теоретические проблемы информационного противостояния, задачи по их решению возлагаются на теории кодологии, криптологии и стеганологии, в которых во всем мире интенсивно развиваются направления кодоанализа, криптоанализа и стегоанализа. Практические аспекты также не остаются в стороне, но замечу, что в РФ активность не очень-то высока, сказывается инертность молодых (сам я разменял уже 9-й десяток, но администрация Хабра ограничила возрастной ценз 1950 г). Мое мнение, конечно, ограничено наблюдением потомства (вплоть до правнуков) и общением в интернете, а также с обучаемыми и сотрудниками фирмы, где подрабатываю. СМИ тоже добавляют негатива. Кто из молодежи чуть поумнел, уходят за бугор. Поведение остальных видите сами.

Экскурс по публикациям

Разработка (синтез) технических устройств требует от разработчика определенных знаний, умений ими пользоваться и других навыков подобного рода. Существенная составляющая таких знаний математическая. Это, как правило, алгебра, дискретная математика, геометрия, физика, математическая логика и др. Здесь в статье будем рассматривать алгебраические структуры не совсем в классическом изложении, но с достаточными уровнем строгости и точностью. Главной моей задачей является обеспечение доступности и понятности изложения вещей, которые я использую в своих текстах и изысканиях.

Например, здесь используется поле расширения GF (2⁸) и, если обойтись без него, ничего стоящего изложить не удается. Мои критерии оценки просты. Каждый семестр 2, а то и 3 экзамена и зачеты в разных учебных группах. Там слышу и вижу, что я излагал, выносил на практику, и что мне возвращают в ответах по экзаменационным билетам. Очень полезен анализ экзаменационных ответов, вижу, что следовало бы излагать кое-что по-другому, лучше.

А здесь свойства Z_N конечного числового кольца вычетов по составному модулю N =pq используются для поиска решения задачи факторизации больших чисел в рамках нового оригинального подхода. Понятно, что в каждой из последующих публикаций переносить часть стандартных математических средств было бы неразумно, посему принято решение собрать все в одном месте и при необходимости адресовать сюда читателей.

Здесь же рассматривается и используется группа точек эллиптической кривой на плоскости. Операция суммирования в группе очень специального вида, вызывающая недоуменные вопросы, типа как это Вам удается складывать точки кривой, даже от членов ГЭК.

Группы

Предварительно введем ряд необходимых определений.

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

Ниже, как напоминание, приводится таблица действий (операций) с конечными дискретными множествами, а на диаграммах для наглядности показаны и непрерывные множества А и В.

Таблица операций с множествами


Определение. Операцией называется отображение ААА или, например, аb=с; a,b,c A. Операции в алгебраических структурах другие нежели в арифметике, рассматриваются: унарные (например, обращение b^-1), бинарные, тернарные, ..., n-арные (по числу мест для операндов), или умножение перестановок, модулярные (взятие результата по (mod R)) и др. Говорят, что элементы а и b перестановочны или коммутируют, если ab = ba.

Определение. Группа это множество G элементов (любой природы), над которыми задана единственная операция, но она может быть сложением (+) и группа называется аддитивной, ее нейтральный элемент (0) или умножением () называется мультипликативной, ее нейтральный элемент (1), но как правило, операции эти не обычные арифметические, а специальные. Обозначается группа часто символом (G,), среди всех групп важное место отводится симметрическим группам перестановок степени n. Части элементов группы, сохраняющие свойства группы называются подгруппами. В сущности это такие же группы, только меньше исходной. Это неформальное определение группы, формальное будет приведено чуть позже.

Группа G, удовлетворяющая коммутативному закону ba =ab для всех a,b G называется в честь математика Абеля (1802 -1829) абелевой.

Примером аддитивной группы является набор слов кода Хемминга (см.здесь). Операция в этой группе 16 порядка суммирование слов по (mod2). С этой группой выполнялась операция разложения в смежные классы группы из 128 слов по подгруппе кода, а также строилась таблица Кели, элементы группы используются в кодере (базис пространства размерности 4) и декодере. Одним словом этот пример наглядно демонстрирует как может использоваться даже маленькая группа для решения очень важной практической задачи (связь).

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

Начнем с простого примера. Заданы n элементов (обозначим их цифрами 1,2,3,...,n) и образуем из них перестановки, число которых n! = 123...n. Ограничимся значением n=3, тогда 3! = 6.

Определение. Порядок группы число элементов в группе называется ее порядком. В примере число 6 это порядок группы.

В группе каждый элемент также имеет порядок, который является делителем порядка группы.
Определение. Порядок элемента группы это наименьший показатель степени элемента в мультипликативной группе (кратности в аддитивной b+b+b+b+...b =nb = 0, порядок =n), при котором он обращается в нейтральный элемент, например ()³=1, порядок ord() = 3.

В симметрической группе операцией является умножение перестановок. Это умножение аналогично матричному умножению, так как каждой перестановке степени n ставится в соответствие квадратная перестановочная матрица размерности nn, в которой каждая строка и столбец содержат единственную единицу. Ниже это показано для симметрической группы.



Для удобства работы с группой и ее элементами математиком Кели предложена таблица операций группы (ограниченного размера). В клетке на пересечении строки и столбца ставится результат операции с элементами, которые их обозначают. Результат (как и обозначение строк/столбцов) в таблице представляется десятичными номерами элементов, что экономит место.

Таблица умножения элементов (перестановок) группы


Заполнение 36 клеток таблицы умножения упрощается, если воспользоваться свойствами таблицы Кели.
Все строки и столбцы содержат элементы всей группы.
Крайние столбцы лексикографически упорядочены и встречно направлены (1-й сверху/вниз последний наоборот)
На главной диагонали таблицы стоят квадраты элементов, если там стоит 1, то элемент ей соответствующий инволюция; инволюциями в являются
Относительно диагоналей матрицы выполняется симметрия положений элементов.
Свойства таблицы позволяют при ее заполнении ограничиться вычислениями только 13 пар элементов (выше они показаны).

Симметрическая группа

Группа имеет маленький порядок (6) и для иллюстрации свойств не очень удобна. Далее будут приводится примеры с симметрической группой 24 порядка. Все четные перестановки степени n образуют знакопеременную подгруппу в симметрической группе, обозначаемую символом А_n.



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

По таблице умножения находятся подгруппы в составе большой группы. Необходимо помнить, что порядок меньшей подгруппы должен делить порядок большей.
Построим циклическую группу с порождающим р₁₄ элементом. Входим в таблицу 2. В строке 14 находим на пересечении с р₁₄ столбцом элемент р₂₄; в строке 24 находим в клетке пересечения с 14 столбцом элемент р₁₁ и наконец в клетке строки 11 на пересечении со столбцом 14 находим элемент р₁, т.е. нейтральный элемент 1. Итак, р₁₄р₁₄р₁₄р₁₄ = р₁, это элементы подгруппы 4-го порядка, значение которого нацело делит порядок 24:4 = 6. Для нее можно построить таблицу Кели и в ней не будут появляться никакие элементы кроме найденных.В этой подгруппе элементы р₁₄ и р₁₁ имеют 4-й порядок, а р₂₄ второй это инволюция.

Морфизмы групп

Отображение f группы (G,*) в группу (G',) называется гомоморфным (или гомоморфизмом), если для любых а,b G, f(a*b) = f(a)f(b). Обычно продолжают эти равенства так f(е) = е',
f (a^-1) = (f(a)) ^-1. Запись справа от равенства обозначает образ и называется образом, слева прообразом отображения f. Операции над образом и прообразом в общем случае не совпадают. Прообраз единицы (G',) при гомоморфизме f называется ядром этого гомоморфизма и обозначается ker f. Хорошо известным со школьных лет примером является такое отображение log (ab) = log (a) + log (b).

Элементы образа с операцией над ними (+), а в прообразе элементы связаны операцией () умножения. Гомоморфный образ группы есть группа (подгруппа), т.е., если f-гомоморфизм G на G' и G группа, то и G' группа. Гомоморфизм обобщение изоморфизма групп: если f взаимно однозначное гомоморфное отображение G на G', то оно изоморфно, что обозначается так GG'.
Две группы G и G' с операциями () и (*) называются изоморфными, если существует отображение f: G G' такое, что (отображение f сохраняет групповую операцию) образа;

Теорема. Пусть Н нормальная подгруппа группы G и G=G/H. Тогда отображение f группы G на G, заданное формулой f(a) =a является гомоморфизмом. Ядро этого гомоморфизма есть Н. Этот гомоморфизм часто называют естественным (каноническим).
Гомоморфизмы группы по существу исчерпываются каноническими гомоморфизмами.

Выполним разложение группы G 24-го порядка по ее подгруппе H ={1,8, 17,24} в смежные классы и построим для этого разложения факторгруппу по подгруппе Н. С этой целью выпишем в столбцы левые и правые произведения элементов подгруппы Н.



В таблице разложения группы G порядка 24 на классы смежности по подгруппе Н обозначены столбцы л1, л2, л3, л4, л5 имена левых и п1, п2, п3, п4, п5 правых смежных классов, ведущие представители классов по одному на столбец выписаны в следующей строке.

Средний столбец Н группа 4-го порядка (ядро гомоморфизма). Столбцы заполняются произведениями ведущих представителей классов на элементы группы Н. После заполнения столбцов выполняется сравнение классов. Если составы левых и правых классов совпадают, то говорят просто о классах смежности и обозначают Н = К0, К1, К2, К3, К4, К5. При этом подгруппа Н называется нормальной. Ведущим представителем очередного класса при заполнении таблицы выбирается наименьший элемент G, из не вошедших в уже построенные классы.

Полученные классы смежности далее рассматриваются как элементы новой группы, называемой факторгруппой группы G по подгруппе Н (обозначается факторгруппа G =G/H). Операцией в этой новой группе является умножение классов: для каждой пары классов, например, К3К5 = К2 строится таблица 44, в которой строки помечаются элементами первого сомножителя, а столбцы второго. Далее выполняют умножение как в группе G. Результат такого умножения дает 16 элементов, но все они принадлежат одному классу, в нашем случае классу К2.

Кроме отображений изоморфизмов гомоморфизмами являются эндоморфизмы и автоморфизмы. Гомоморфизм группы G в себя называется эндоморфизмом, а изоморфизм группы G на себя- автоморфизмом. Эти понятия сопоставимы с понятиями отображений неструктурированных множеств инъекцией, сюръекцией и биекцией.

Таблица 2 Кели симметрической группы $inline$S_4 (умножение Р_k = Р_i Р_j)$inline$

Коммутант

Каждой паре элементов а,b G сопоставим элемент, называемый коммутатором этой пары [a, b] = a ^-1b ^-1ab. Подгруппа К группы G, порожденная всеми ее коммутаторами, называется коммутантом группы G или производной подгруппой.



Группа G называется разрешимой, если цепочка G G' G'' G⁽ⁱ⁾..., где каждая подгруппа G⁽ⁱ⁾является коммутантом предыдущей, обрывается после конечного числа шагов на единичной подгруппе, например, G^(е)= 1.
В таблице 4 знакопеременная подгруппа G' =А₄ порядка 12 нормальная, из G = порядка 24, так как левый и правый смежные классы по этой подгруппе совпадают (классы это одно и тоже дополнение до полной группы ). Таблица 4 при этом сворачивается в меньшую 44 таблицу (коммутант), содержащую элементы G'' ={1,8,17,24} новой подгруппы, коммутант которой равен 1. Таблица 4 иллюстрирует разрешимость группы .

Заключение

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

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

Литература

Авдошин С.М., Набебин А.А. Дискретная математика. Модулярная алгебра, криптография, кодирование. М.: ДМК Пресс, 2017. -352 с.
Акимов О.Е. Дискретная математика.Логика, группы, графы- М.: Лаб.Баз. Зн., 2001. -352 с.
Андерсон Д.А. Дискретная математика и комбинаторика.- М.: Вильямс, 2003. -960 с.
Берлекэмп Э. Алгебраическая теория кодирования. -М.: Мир,1971.- 478 с.
Ваулин А.Е. Дискретная математика в задачах компьютерной безопасности. Ч 1- СПб.: ВКА им. А.Ф. Можайского, 2015. -219 с.
Ваулин А.Е. Дискретная математика в задачах компьютерной безопасности. Ч 2- СПб.: ВКА им. А.Ф. Можайского, 2017. -151 с.
Горенстейн Д. Конечные простые группы. Введение в их классификацию.-М.: Мир, 1985.- 352 с.
Грэхем Р., Кнут Д., Пташник О. Конкретная математика.Основание информатики.-М.: Мир,1998.-703 с.
Елизаров В.П. Конечные кольца. М.: Гелиос АРВ,2006. 304 с.
Иванов Б.Н. Дискретная математика: алгоритмы и программы М.: Лаб.Баз. Знаний., 2001. -280 с.
Иерусалимский Я.М. Дискретная математика: теория, задачи, приложения М.: Вузовская книга, 2000. -280 с.
Лидл Р., Нидеррайтер Г. Конечные поля: В 2-х т. Т.1 -М.: Мир,1988. 430 с.
Лидл Р., Нидеррайтер Г. Конечные поля: В 2-х т. Т.2 -М.: Мир,1988. 392 с.
Ляпин Е.С., Айзенштат А.Я., Лесохин М.М., Упражнения по теории групп.- М.: Наука,1967.-264 с.
Муттер В.М. Основы помехоустойчивой телепередачи информации. -Л. Энергоатомиздат,1990.- 288 с.
Набебин А.А.Дискретная математика.- М.: Лаб.Баз. Знаний., 2001. -280 с.
Новиков Ф.А. Дискретная математика для программистов.- СПб.: Питер, 2000. -304 с.
Холл М. Теория групп.-М.: Изд. ИЛ, 1962.- 468 с.
Шиханович Ю.А. Группы, кольца, решётки. СПб.: Кирцидели,2006. 368 с.
Шнеперман Л.Б. Курс алгебры и теории чисел в задачах и упражнениях: В 2-х ч Ч.2.-Мн.: Выш. шк., 1987. -256 с.
Шнеперман Л.Б. Сборник задач по алгебре и теории чисел.- Минск: Дизайн ПРО, 2000. -240 с.

К тем сведениям об эллиптических кривых (ЭК), которые доступны читателям Хабра и Интернета в целом, а также из бумажных книг, предлагаю дополнительные, уточняющие важные детали, опущенные в некоторых статьях. Например, в работе приводится изображение тора (рис. 4), но никаких оговорок не делается. Откуда он взялся, почему тор? Другие авторы вообще не упоминают эту фигуру. В чем здесь дело?

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

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

Пространства изучения моделей

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

Аффинные пространства

Рассмотрим множество наборов (а1, а2, , аn) из n элементов, где каждый аi F и F некоторое поле. Множество наборов обозначим символом и обычным способом введем для наборов операции сложения и умножения на скаляры. При условии замкнутости множества по этим операциям оно образует векторное пространство с аддитивным нейтральным элементом О = (0, 0, , 0).

Для удобства в дальнейшем условимся обозначать набор (а1, а2, , аn) символами а, в, с, а будем называть n-мерным аффинным пространством, его элементы аффинными точками, точку О = (0, 0, , 0) назовем началом координат. Если F конечное поле из элементов, где р простое, то содержит элементов (наборов, точек). При р = 2 получаем множество всех двоичных чисел разрядности k.

Аффинная плоскость

Пусть F конечное алгебраически замкнутое поле и Fо некоторое подполе поля F. Аффинная плоскость под полем F (дискретная конечная FF ) представляет собой множество всех {(, )} упорядоченных пар элементов , поля F. Каждую такую пару Q=(, ) называют точкой плоскости , а элементы , координатами точки Q. Если поле F является полем расширения некоторой степени n, то каждая координата точки Q представляет собой многочлен степени не выше n 1 от формальной переменной t.

Эллиптической кривой (ЭК) над полем F называется плоская гладкая кривая с уравнением вида
Индексы у коэффициентов в уравнении указывают степени, которые должны быть приписаны этим коэффициентам, чтобы уравнение ЭК стало однородным, т.е. чтобы каждое слагаемое в нем имело общую степень 6.

Через Е(F) обозначают множество, состоящее из точек , удовлетворяющих этому уравнению, с добавлением бесконечно удаленной точки О. Если К некоторое расширение поля F, то через Е(К) будет обозначаться множество, состоящее из точек удовлетворяющих уравнению ЭК и бесконечно удаленной точки О.

Пример 1. Для поля с характеристикой p = 5 и степенью расширения n = 3 задается примитивный элемент () и неприводимый многочлен Порядок поля при этом , а аффинная плоскость содержит точек с многочленами в роли координат точек.

Например, задание одной из точек эллиптической кривой в этом поле имеет вид , где многочлены координаты точки Q. Малая часть точек такой дискретной плоскости образует ЭК и еще меньшая их часть является аддитивной группой точек ЭК, которая строится здесь.

Пусть F алгебраическое замыкание поля поля F. Условие гладкости кривой означает, что в множестве Е(F) не существует точек, в которых одновременно обращались бы в нуль частные производные $inline$g(x,y)/x, g(x,y)/y,$inline$ где



Иными словами, система уравнений



не имеет решений, принадлежащих Е(F).

Проективное пространство

Символом по аналогии с предыдущим будем обозначать n-мерное проективное пространство над полем F. Очень важно понимать, как устроено это пространство, и в чем отличие от . С этой целью рассмотрим вначале множество наборов (ао, а1, , аn), в котором точка O=(0, 0, , 0) начало координат удалена.

Над множеством определим отношение эквивалентности: nмерная точка а = (ао, а1, , аn) эквивалентна точке b = (bо, b1, , bn), если существует такой элемент F*, где F* мультипликативная группа поля F, что aо=bо, a1=b1,...,an=bn. Просто убедиться в том, что все такие пары (a, b) из образуют отношение (~) эквивалентности, которое индуцирует разбиение множества на классы эквивалентности.

Все такие классы называются точками пространства и все элементы класса (т.е. сам класс) обозначаются символом [а], если точка а = (ао, а1, , аn) входит в состав класса, то такая точка а называется представителем класса. В геометрической терминологии все элементы (точки) произвольного класса [а] принадлежат прямой в пространстве , проходящей через точку а и начало координат в аффинном пространстве.

Пространство образованно элементами (точками). Это легко показать, так как пространство имеет элемент (без нулевого), мультипликативная группа F* поля F состоит из q 1 элементов (точек проективного пространства). Каждый класс эквивалентности (прямая) порождается произвольным элементом а = (а0, а1, , аn) умноженным на каждый элемент из F*, т.е. содержит q 1 элементов.

Тогда число |H| классов (их объёмы одинаковы) эквивалентности можно подсчитать по формуле:
Сравнение мощностей nмерных пространств аффинного и проективного показывает, что .

Пример 2: Пусть . Тогда мощность (порядок число элементов) аффинного пространства ;
мощность (порядок) аффинного пространства ; в нем |H| классов. мощность (порядок) проективного пространства , т.е. число классов эквивалентности точек пространства . Видим, каждый класс эквивалентности содержит 7 элементов. . =>585>512.

Проективная плоскость

Наряду с аффинной плоскостью в криптографии с эллиптическими кривыми используется проективная плоскость. Это связано с тем, что для ЭК, задаваемой в этой плоскости, формулы для групповой операции с точками ЭК не содержат действия деления, т.е. для вычисления координат результирующей точки не требуется обращения элемента в поле F, которая весьма трудоемка. Иногда для проективной плоскости используют обозначение , чтобы подчеркнуть вещественную природу (некомплексную) элементов.

Определение. Приведем в определении тройственное представление проективной плоскости:
= {прямые в , проходящие через начало координат} =
= {отношение вида X: Y: Z} =
= { \{0}/~, где (X: Y: Z), (Х:Y:Z), если R\0}.

В нижней (последней) строчке определения записано фактормножество точек пространства (трехмерного, вещественного) по отношению эквивалентности (~), где принадлежит F* -множеству вещественных чисел без нуля, т.е. мультипликативной группе поля.


Рисунок 1 Аффинная плоскость Z = 1

Легко может быть выполнен переход к произвольному векторному пространству над любым полем. Для того, чтобы представить отношение X: Y: Z для Z = 0, достаточно положить x = X/Z,
y = Y/Z. Этим достигается упрощение, так как исходное отношение задается теперь парой вещественных чисел.

Другими словами, класс эквивалентности троек (x, y, z) по отношению эквивалентности имеет единственного представителя (x, y, 1), третья координата которого Z /Z = 1 для всех точек.
К сожалению, Z все-таки может обращаться в нуль, и в этом случае наш способ представителя класса эквивалентности не годится.

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


Рисунок 2 Замены переменных, переводящие кривую в проективное пространство

Прямая общего положения в , проходящая через О, не содержится в плоскости (Z = 0) и, значит пересекает плоскость (Z = 1) в единственной точке, которая и представляет собой этот класс эквивалентности (т.е. прямую L в ). Прямые, лежащие в плоскости (Z = 0), не пересекают плоскость (Z = 1). Следовательно, они соответствуют не точкам из а асимптотическим направлениям или пучкам параллельных прямых в . Таким образом, можно представить как пространство, состоящее из плоскости , к которой добавлено по одной точке на бесконечности для каждого пучка параллельных прямых.

Ньютон занимался и кубическими кривыми, привел их классификацию, им сформулирована Теорема. Для любой неособой кубической кривой существует проективная замена координат, преобразующая кубическую кривую к кривой в форме Вейерштрасса с рациональными а и b. Например, m(m+1)/2=n(n+1)(2n+1)/6 после замены m=(у-9)/18 и n=(x-3)/6 получаем уравнение рациональные корни которого и будут решением задачи.

Приведем кривую к форме Вейерштрасса. Выполним проективную замену координат х = s -t, y = t. Эта замена осуществляет параллельную проекцию плоскости ху на плоскость st. Получаем кривую. Теперь спроецируем плоскость st на плоскость uv из центра. Еще одна замена координат s=1/3u и t =(6v+1)/6u. Новая кривая (в форме Вейерштрасса) получает вид

Вопрос на понимание ЭК: Какие два натуральных смежных числа при умножении у(у+1) равны произведению трех натуральных смежных чисел (х-1)х(х+1)? В уравнении есть как в ЭК.

Формулы групповой операции ЭК в проективном пространстве (плоскости).
Пусть задано уравнение ЭК в проективной плоскости в форме Вейерштрасса Е(GF(q)):

над полем характеристики р, (р 2 и р 3), получаемое путем перевода ЭК из аффинной в проективную плоскость. Точки такой ЭК можно рассматривать как эквивалентный класс точек (X, Y, Z) плоскости над полем GF(q).

Бесконечно удаленная точка O ,O представляет все ненулевые точки с отношением эквивалентности (X, Y, Z) ~(kX, kY, kZ). Такие точки обозначаются как (X, Y, Z) и среди них имеется единственная точка с координатой Z = 0 это точка (0, 1, 0). При Z = 0 обязательно и Х = 0, и существует только один класс эквивалентности с Х = Z = 0, содержащий бесконечно удаленную точку (0, 1, 0) Е(GF(q)) .

Существует возможность и обратного перевода ЭК из пространства в аффинное пространство . Для всех точек Q = (X, Y, Z) O производится замена (X, Y, Z) = (Х/Z, Y/Z, 1). При этом выполняется однозначное соответствие: точке (х = Х/Z, y = Y/Z) соответствует точка (X, Y, Z).
Формулы удвоения точки ЭК в проективном пространстве принимают вид:

,
где координата кратна .

Последующие преобразования обеспечивают получение формул группового сложения точек ЭК в проективных координатах.



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


При рассмотрении ЭК над расширенным полем , имеющих инвариант j 0 формулы принимают иной вид для случая

Комплексное пространство C

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

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

По причине линейной независимости периодов над R, 1/2R. Другое название для таких функций эллиптические функции. Для наших целей интерес представляет функция Вейерштрасса (z), которая удовлетворяет дифференциальному уравнению вида

где некоторые константы, зависящие от периодов 1, 2.

Сходство записанного уравнения с ЭК весьма значительное.
Зададим на плоскости С решетку ={m1 + n2|m,nZ} периодов, где m и n целые числа и узлы решетки целочисленные. Элементы решетки образуют нормальную подгруппу в группе комплексных чисел, и мы можем сформировать по этой группе факторгруппу C/.

Позднее покажем, что элементы факторгруппы можно отобразить в комплексные точки Е(С) ЭК Е, и такое отображение взаимно однозначно.
Многочлен правой части ЭК над комплексной плоскостью С.
Параметризацию удаётся осуществить для части ЭК на С, благодаря выбору необходимой функции .

В проективной комплексной плоскости с учетом полюсов функции параметризация устанавливает взаимно однозначное соответствие между множеством точек C/ и множеством Е(С) комплексных точек кривой Е. Такое соответствие оказывается биголоморфно.

Суммирование комплексных чисел определяется групповым законом сложения на торе C/. Ниже будет показано, что соответствие : C/Е(С) ЭК Е. Далее выясняется, что любая ЭК на С может быть нормализована подбором подходящей функции Вейерштрасса . В основе процедуры прояснение такой связи лежит возможность обращения эллиптических интегралов.

Эллиптические функции

Определение. Алгебраическую кривую называют эллиптической, если она как одномерное комплексное многообразие представляет собой тор (бублик).
Определение. Мероморфная двоякопериодическая функция называется эллиптической.

Определение. Аналитическая функция называется мероморфной, если у нее в конечной области С нет особых точек, отличных от полюсов.
Определение. Функция:f^C С({} называется двоякопериодической с периодами 1, 2 при линейной независимости периодов над R и f(z+1)=f(z)=f(z+2) для любых zC.

Двоякопериодическую функцию называют эллиптической, если она мероморфна. Множество эллиптических функций образует поле при фиксированных периодах 1, 2. В плоскости С точки 0, 1, 2 и 1+2 образуют вершины параллелограмма
П={11+22|0 1,2 1}, который называется фундаментальным. Стороны, сходящиеся в точке 0 и сама точка принадлежат П, а три другие вершины и две стороны не принадлежат П.

Особый интерес представляет фундаментальный параллелограмм и его граница.
Определение. Фундаментальным параллелограммом называется область плоскости С, заданная соотношением П ={11+22|0 1,2 1} где 1,2R.
Параллелограммом периодов называется любой параллелограмм вида +П, С. Для всех таких параллелограммов справедливы одинаковые условия.

Относительно эллиптических функций Ж. Лиувиллем (1809-1882) сформулированы и доказаны следующие результаты.

Теорема 1. Не существует отличных от констант целых эллиптических функций.
Доказательство. Целая эллиптическая функция непрерывна, так как не имеет полюсов; поэтому она ограничена на замыкании П. В силу периодичности функция ограничена на С, следовательно, она постоянна.

Следствие 2. Две эллиптические функции, имеющие одинаковые наборы полюсов и соответственно равные главные части в полюсах, отличаются на константу.

Теорема 3. Если эллиптическая функция f(z) не имеет полюсов на границе L параллелограмма П+, то сумма вычетов f(z) во всех полюсах, лежащих внутри П+, равна 0.

Эллиптическая функция Вейерштрасса. Эта функция играет важную роль для всей теории эллиптических функций в силу ее замечательных свойств. Займемся рассмотрением этих свойств подробнее и выясним, как и какие из них могут быть использованы для наших целей, связанных с изучением ЭК. Функция Вейерштрасса определяется над комплексной плоскостью C и представляется формулой.
,
где не содержит точку 0, т.е. решетка периодов с удаленной точкой 0 и фиксированными значениями 1, 2. Выражение под знаком суммы нельзя записывать через две суммы, так как каждая из них представляет расходящийся ряд.

Комплексная плоскость C с решеткой

Перейдем к рассмотрению комплексного случая ЭК.
Пусть 1 и 2 два линейно независимых на R комплексных числа. Обозначим через
={n1 +m2|n,m Z} порожденную ими решетку. Отождествим две точки комплексной плоскости С, если их разность принадлежит . После такого отождествления получим фактор-пространство С/.

На рисунке заштрихованная часть комплексной плоскости представляет собой фундаментальную область параллелограмм, сдвиги которого на элементы из накрывают всю плоскость С.


Рисунок 3. Фундаментальный параллелограмм в комплексной плоскости

Фактор-пространство С/ можно представить в виде фундаментального параллелограмма с отождествленными противоположными сторонами. Так как сложение комплексных чисел (x,y) x+y задает некоторое голоморфное отображение CCC, то С является комплексной группой Ли, а ее подгруппой. Таким образом, фактор-пространство С/ компактная комплексная группа Ли.

Пару (1, 2) можно умножить на комплексное число или и получить пару, состоящую из 1 и , где Im>0. Соответствующую решетку, порожденную 1 и обозначим через , а фактор-пространство С/ через E. Каждое пространство С/ изоморфно одному из E, причем E и E' изоморфны тогда и только тогда, когда


Функции на С/. Пусть g мероморфная функция на С/. Тогда qg мероморфная функция на С, удовлетворяющая условиям qg(z+1) = qg(z+2) = qg(z)
Таким образом, qg двоякопериодическая мероморфная функция на С. Обратно, каждая двоякопериодическая мероморфная функция на С (так называемая эллиптическая функция) определяет некоторую мероморфную функцию на С/.

Основная эллиптическая функция может быть представлена в виде ряда:



Рисунок 4 Представление ЭК в области фундаментального параллелограмма тороидальной поверхностью

На рис. 4 изображен тор, слева развертка его поверхности (плоский лист-прямоугольник). Развертка получена двумя перпендикулярными разрезами тора: вертикальным (в сечении дает малую окружность торцы цилиндрической поверхности) и горизонтальным вдоль образующей цилиндра, получаемого после первого разреза, и распрямления (топология) вдоль осевой линии. Линии разрезов: первая совмещается с координатной осью ординат (у), вторая границы (верхний и нижний края развертки) равноудаленные от оси абсцисс (х). Все целочисленные точки группы ЭК в этой системе координат получают вид (х, у).

Действительно, на рисунке видим симметричное относительно оси х расположение точек. Сплошная линия на торе (синяя) без разрывов на развертке представлена 4-я отрезками, концевые точки которых соответственно имеют совпадающие координаты. Другими словами, обратными действиями (склейкой) можно получить объемную фигуру тор, на поверхности которого все отрезки прямых воссоединятся в замкнутую пространственную винтовую линию. Условность этой иллюстрации в том, что плоская ЭК представляется в комплексной плоскости двоякопериодической функцией, удовлетворяющей уравнению Вейерштрасса.

Эта функция мероморфна на С, двоякопериодическая и имеет полюсы кратности 2 в точности в вершинах решетки . Очевидно, что и производная (z) является двоякопериодической функцией, имеющей полюсы кратности 3 в вершинах решетки .
(z) и (z) связаны между собой некоторым полиномиальным соотношением:
f((z), (z), 1) = 0.

Факторизация из полезных возможностей ЭК

разложение составного числа N на множители.
Формально алгоритм, предложенный Ленстрой содержит следующие шаги.
ш1. Выбирается ЭК над полем порядка N, т.е. целые числа из диапазона .
ш2. Рассматриваем кубическую кривую и базисную точку ЭК .

ш3. Вычисляем ; этим проверяется являются ли редукции кривой Е эллиптическими. Если НОД =N, переход к Ш1 и выбор нового b. Если , то получен нетривиальный делитель числа N. При , переход к Ш4

ш4. Выбираем число k, являющееся произведением небольших простых чисел в небольших степенях: k=НОК(2,3, ..., М), где М-натуральное число.
ш5. Вычисляем кратную базисной точку
ш6. Вычисляем . Если 1<D<N, то D- нетривиальный делитель N; если D =1, либо переход к ш4 и увеличиваем k, либо возврат к ш1 и выбор новой ЭК. Если D =1, то переход к ш4 и уменьшение значения k.

На ш5 вычисляется точка kP. Ее можно вычислить самое большее за шагов, т.е. сложения точек на кривой. Более того, при вычислениях используются только значения .

Замечание. Обычный подход многократное суммирование точки с собой. Ленстра заметил, что в кольце невозможность вычислить сумму точек (получить нейтральный элемент O), где необходимо вычислять коэффициент возникает деление на нуль чаще чем в поле, что может приводить к нейтральному элементу O быстрее. Действительно, разность обращается в нуль при значениях кратных не только самому N, но при кратных его делителям.

Пример Пусть задано составное число . Выберем Представим разложением по степеням 2. Будем вычислять




Следовательно, .
Теперь, вычисляя , получаем единицу (решения нет) и переходим к ш1 для выбора нового значения k, которое увеличим в 7 раз. Представим новое значение k степенями 2 вычислим
и редуцируем по модулю N,
Наконец, воспользуемся алгоритмом Евклида и получаем , нетривиальный множитель

Заключение

Не любую ЭК и ее группу можно отождествлять с точками на поверхности тора, а только в случае ЭК, представляемой в комплексной плоскости.
Вольное обращение с математическими понятиями и терминами не упрощает понимание существа дела, а наоборот запутывает. Авторы публикаций часто называют порядком ЭК порядок группы ее целочисленных точек. Читатель, обратившись к учебнику или к математической энциклопедии (в 5-ти томах), останется в недоумении, прочитав статьи об этих понятиях.

О некорректности с заданием полей расширения (отсутствие неприводимого многочлена и примитивного элемента) уже упоминалось во вводной части. Как это должно работать и работает демонстрируется в AES I, где приводится в явном виде поле расширения конкретного стандарта шифрования США, AES II здесь демонстрируются примеры использования поля расширения в реализации операций шифрования/расшифрования, корректирующие коды.

Аддитивная группа поля расширения раскладывается в смежные классы по подгруппе 16-го порядка. Эти классы являются элементами факторгруппы и классами эквивалентности. Эти ссылки сделаны на реальные, работающие в действительности вещи (не абстрактные примеры), не упрощенные простенькие упражнения.

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

Изначально от теории представлений отказались. Сегодня она играет важнейшую роль в большинстве областей математики.

Когда в конце XIX века впервые появилась теория представлений, многие математики сомневались в ценности этого подхода. В 1897 году английский математик Уильям Бёрнсайд писал, что сомневается в том, что эта необычная перспектива даст какие-то полезные результаты.

Бёрнсайд, по сути, говорил о том, что теория представлений бесполезна, сказал Джорди Уильямсон из Сиднейского университета в лекции 2015 года.

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

Не сразу становится понятно, что её стоит изучать, сказала Эмили Нортон из Кайзерслаутернского технического университета в Германии.

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

Математикам, по сути, про матрицы известно уже всё. Это одна из немногих математических тем, в которой мы хорошо и досконально разобрались, сказал Джаред Вайнштайн из Бостонского университета.

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

Возьмём сначала группы. Чтобы упростить пример, возьмём шесть симметрий равностороннего треугольника:

• Две вращательных (на 120 и 240).
• Три зеркальных (относительно линий, проведённых из каждой вершины через середину противоположной стороны).
• Тождественная симметрия когда с треугольником ничего не происходит.

Шесть этих симметрий образуют замкнутую вселенную элементов группу формально именуемую S3. Это группа, поскольку любое количество этих симметрий можно применить к треугольнику последовательно и в любом порядке, а итоговый результат будет таким же, как если бы вы применили только одну. К примеру, если отразить треугольник, а потом повернуть его на 120, то вершины переориентируются таким же образом, как если бы вы применили другое отражение.

Делаю что-то одно, потом делаю что-то другое. Важно то, что в итоге получается всё равно симметрия треугольника, сказал Нортон.



Математики называют комбинацию из двух симметрий композицией. Одно действие из группы (отражение) соединяется с другим (вращение) и даёт третье (другое отражение). Вслед за математиками композицию можно считать умножением.

Нам нравится считать наши операции умножением, хотя это не перемножение чисел, а умножение преобразований, сказал Нортон.

Это легко увидеть, если рассмотреть ненулевые вещественные числа, также формирующие группу. У вещественных чисел есть нейтральный элемент число 1. Любое вещественное число, если его скомбинировать с 1, то есть, умножить на неё, остаётся неизменным. Также можно перемножать любую комбинацию вещественных чисел в любом порядке, и результат тоже всегда будет вещественным числом. Математики говорят, что группа вещественных чисел замкнута относительно умножения, то есть, из группы нельзя выйти, просто перемножая её элементы.

С момента открытия групп в 1830-х, они стали одним из наиболее важных объектов математики. Они кодируют информацию о простых числах, геометрических пространствах и вообще почти всего, что интересует математиков. Решение важной задачи часто превращается в изучение связанной с ней группы. Однако большинство групп гораздо сложнее понять, чем группу симметрий равностороннего треугольника. В группы Ли, к примеру, входит не шесть элементов, а бесконечное количество.

Иногда группы становятся чересчур сложными, сказал Вайнштейн.

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

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

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

[2 0]
[0 2]

То он вытягивается в длину в два раза. Это пример линейного преобразования.



Другие матрицы выполняют другие линейные преобразования отражения, повороты и сдвиги. Есть и нейтральная матрица, оставляющая вектор без изменений (точно так же, как тождественная симметрия оставляет треугольник неизменным, а число 1 оставляет неизменными другие числа).

[1 0]
[0 1]

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

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

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

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

Почти всегда группу можно представить несколькими способами. К примеру, у S3 есть три разных представления через матрицы вещественных чисел: тривиальное, отражённое и знаковое.

Математики расставляют представления заданной группы в таблице таблице характеров где суммируется информация о группе. Строки обозначают каждое из различных представлений, а столбцы относятся к важным матрицам этих представлений матрице, сопоставленной нейтральному элементу группы, и матрицам, сопоставленным генерирующим элементам, порождающим все остальные элементы. Элементами таблицы служат значения, которые называют "следами" матриц, и подсчитывают через сумму диагональных элементов от левого верхнего угла к правому нижнему. Ниже приводится таблица характеров для трёх представлений S3.



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

Много разных представлений помнят разные вещи, и если собрать всё это вместе, получится такая калейдоскопическая картинка вашей группы, сказал Нортон.

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

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

Некоторые из самых продуктивных представлений не используют ни вещественные, ни комплексные числа. Они используют матрицы, элементы которых взяты из миниатюрных, или модульных числовых систем. Это мир арифметики циферблата, в котором 7+6 оборачивается вокруг 12-часового циферблата и даёт 1. У двух групп с одинаковыми таблицами характеров в вещественном представлении могут быть разные таблицы характеров в модульном представлении, что позволяет различать их.

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

Философия теории представлений начала с огромной скоростью поглощать огромные области математики во второй половине XX века, сказал мне Уильямсон.

Теория представлений и в частности, модульные представления сыграли важную роль в знаковом доказательстве Великой теоремы Ферма, полученном Эндрю Уайлсом в 1994 году. В задаче вставал вопрос о существовании решений уравнений вида aⁿ + bⁿ = cⁿ в целых числах. Уайлс доказал, что для n>2 таких решений не существует. Если говорить примерно, то он доказывал, что если бы такие решения существовали, привели бы к появлению группы эллиптической кривой с весьма необычными свойствами. Эти свойства были настолько необычными, что казалось возможным доказать невозможность существования подобного объекта. Однако напрямую доказать, что он не существует, оказалось слишком тяжело. Вместо этого Уайлс обратился к семейству модульных представлений, которое было бы связано с этой группой, если бы она существовала. Он доказал, что такого семейства модульных представлений быть не может, что означает, что не может существовать и группы (или эллиптической кривой), что означает, что и решений тоже не существует.

Что, в свою очередь, означает, что примерно через 100 лет после того, как Уильям Бёрнсайд отбросил теорию представлений как бесполезную, она оказалась критически важным компонентом, возможно, наиболее знаменитого доказательства XX века.

Я не мог придумать доказательства Великой теоремы Ферма, в котором бы нигде не использовалась теория представлений , сказал Вайнштейн.