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

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

Пусть [math]G[/math] — группа, [math]a \in G[/math] . Требуется найти порядок элемента [math]a[/math] .

Решение

По следствию из теоремы Лагранжа порядок элемента является делителем порядка группы. Таким образом достаточно рассмотреть [math]a^n[/math] , где [math]n \in X[/math] , [math]X[/math] — делители порядка группы.

Алгоритм

Найти все делители [math]|G|[/math] перебором от 1 до [math]\sqrt<|G|>[/math]
Для каждого делителя [math]n[/math] проверить значение [math]a^n[/math] . Наименьший [math]n[/math] , такой что [math]a^n = e[/math] , является порядком элемента [math]a[/math] в группе.

Алгоритмическая сложность

Перебор от [math]1[/math] до [math]\sqrt<|G|>[/math] выполняется за [math]O(\sqrt<|G|>)[/math] . Возведение [math]a[/math] в степень [math]n[/math] выполняется за [math]O(\log n)[/math] . Следовательно время выполнения [math]O(\sqrt <|G|>\cdot \log<|G|>)[/math] .

Порядок элемента

Как найти порядок элемента группы. Число элементов в группе задано. Как найти элемент, имеющий максимальный порядок.Чему равен этот максимальный порядок. Есть ли методы- не просто переборные?

«Число элементов в группе задано» — этого мало, должна быть задана
сама группа.
Группа кольца вычетов по заданному модулю.

Имеется в виду аддитивная группа? (Если модуль m не является простым
числом, то говорить о мультипликативной группе мы не можем.)

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

У меня группа по умножению. Модуль у меня составной-произведение двух простых чисел.

Но только если модуль составной, то это всё-таки не группа.
(Но можно рассмотреть группу обратимых элементов.)

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

В теме Группы мне предложили задачу по криптосистеме RSA, а мы ее проходим в школе на спецкурсе. Кругликов предложил подумать, что делать, когда d не знаю. Вот поэтому задаю эти вопросы, у меня мысль про цикл, а для этого надо порядки элементов.

Есть методы «умно-переборные», основанные на теор. Лагранжа: порядок элемента делит порядок группы. Если известно разложение порядка группы на множители — перебор можно существенно сократить.

Универсального непереборного метода нет. Наверное, его и вообще быть не может.

Если задача — найти макс порядок элементов группы — она часто решается довольно просто. Только, при этом, далеко не всегда находится элемент макс. порядка, а только сам порядок.

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

Возводите свой элемент в степень, пока единица получится-и все. Алгоритм простой: степень в двоичный вид от старших разрядов к младшим, далее,если 1, то возведение в квадрат (по модулю) и умножение на основание, если 0, то просто в квадрат. Только зачем?
А может подумать сколько классов шифров существует, к какому классу относится RSA-думать как криптоаналитик, а не как математик. Может тогда появятся простые идеи.

, отсюда p+q=n+1-[m]\varphi (n)[/m]. Определяю экспериментально(Excel) порядок какого-либо элемента, для простоты Р(2), порядок Р(2) есть делитель [m]\varphi (n)[/m], поэтому [m]\varphi (n)=2P(2)k[/m], к=1,2,3,…. Тогда [m]p+q=n+1-2P(2)k[/m]. Составляю квадратное уравнение с теоремой Виета [m]<^>-(p+q)x+n=0[/m]. Решаю его при разных к=1,2,3,…. При том к, когда дискриминант есть полный квадрат, получаю два корня [m]<_>=p,<_>=q,[/m] получил факторизацию модуля n.
Пример. N=989. Получил Р(2)=154. p+q=682 при к=1, p+q=374 при к=2, p+q=66 при к=3. При к=3 получаю уравнение [m]<^>-66x+989=0[/m], его корни р=23, q=43. Проверка: 23*43=989.
А вдруг так никто не делал, я не видел.

В учебнике А.В. Рожков О.В. Ниссенбаум Теоретико-числовые методы в криптографии доказывается теорема. Сложность вычисления функции Эйлера не выше сложности задачи факторизации . Там используется квадратное уравнение при наличии функции Эйлера, как у тебя. Но вот оценка функции Эйлера через экспериментальное нахождение порядка элемента-такого я не встречал. Быть может кто-то из преподавателей знает?
В любом случае, это Ваше достижение.

Кольцо, определяющее структуру надгрупп нерасщепимого максимального тора Текст научной статьи по специальности «Математика»

ПРОМЕЖУТОЧНЫЕ ПОДГРУППЫ / НЕРАСЩЕПИМЫЙ МАКСИМАЛЬНЫЙ ТОР / СЕТИ / СЕТЕВЫЕ ГРУППЫ / ЭЛЕМЕНТАРНАЯ ГРУППА / ТРАНСВЕКЦИЯ. / INTERMEDIATE SUBGROUPS / NON-SPLIT MAXIMAL TORUS / NETS / NET GROUPS / ELEMENTARY GROUP / TRANSVECTION

Аннотация научной статьи по математике, автор научной работы — Шилов Александр Валентинович

Исследуются сети и сетевые кольца, ассоциированные с надгруппами нерасщепимого максимального тора , связанного с радикальным расширением основного поля.

i Надоели баннеры? Вы всегда можете отключить рекламу.

Текст научной работы на тему «Кольцо, определяющее структуру надгрупп нерасщепимого максимального тора»

Владикавказский математический журнал 2011, Том 13, Выпуск 2, С. 63-66

КОЛЬЦО, ОПРЕДЕЛЯЮЩЕЕ СТРУКТУРУ НАДГРУПП НЕРАСЩЕПИМОГО МАКСИМАЛЬНОГО ТОРА

Исследуются сети и сетевые кольца, ассоциированные с надгруппами нерасщепимого максимального

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

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

группы, элементарная группа, трансвекция.

Работа посвящена исследованию сети и сетевого кольца [1—3], ассоциированной с над-группой нерасщепимого тора, связанного с радикальным расширением основного поля.

Пусть хп—й — неприводимый многочлен степени п над полем к, й £ к. Тогда вг = 6г-1, 1 ^ г ^ п, образует базис радикального расширения К = к( \/71), 9 = \[й поля К = к(9) над к. Мы рассматриваем нерасщепимый максимальный тор Т = Т(й), который является образом мультипликативной группы поля К = к( ^/71) при регулярном вложении в О = ОЬ(п,к).

С каждым вектором х = (х1 , х2 . хп) £ кп \ 0 связана невырожденная матрица С(х), элементы которой вычисляются по формулам

хг+1—, 3 ^ Ц гз [ йхп+г+1-,, 3 > г + 1.

В выбранном базисе тор Т = Т (й) определяется как матричная группа

С каждой матрицей С = С (х) = (сг,) связана обратная матрица С 1 = С (у) = = (Уъ • • • > Уп) £ кп, где г/г = \с<х) \' пРичем Си ~ алгебраическое дополнение элемента с1г матрицы С = С(х).

В работе рассматривается унитальное подкольцо К0 = К(й) поля к, порожденное элементами хгу,, йхгу5:

К0 = К(й) = ^хгу,-, йхг у3 : г + 3 ^ п +1, г + 5>п +1, х £ кп \ 0^>.

Пусть К — унитальное подкольцо поля к, й £ К. Пусть, далее, А1. Ап — идеалы кольца К, причем

А1 С . С Ап, йАп С А1.

Через а = (а^) = а(А^ А2. Ап) мы обозначаем сеть идеалов, определенную следующим образом

dAra+i+i-j, j ^ i + 1.

Сеть а = (а^-) = а(А1, А2. Ап) мы называем сетью, ассоциированной с тором Т. Далее, М(а) — сетевое кольцо (С(а) — сетевая группа) [1]. Подгруппу Е(а), порожденную всеми трансвекциями из С(а), мы называем элементарной сетевой подгруппой, соответствующей тору Т.

Основным результатом статьи является следующая

Теорема 1. Тор Т нормализует сетевое кольцо М(а) для произвольной сети а = а(А1, А2. Ап), ассоциированной с тором, тогда и только тогда, когда й0 ^ Я.

Квадратную матрицу а = (а^) порядка п назовем матрицей сетевого вида, если ее элементы удовлетворяют условиям:

ars — ar+1,s+1; arn — d 1 ar + 1, 1 ,

Нетрудно видеть, что сумма и произведение матриц сетевого вида является матрицей сетевого вида.

Ясно, что матрица сетевого вида полностью определяется первым столбцом. Пусть 1 ^ в ^ п. Обозначим через (е5) матрицу сетевого вида с первым столбцом (0. , 0,1, 0. , 0)т в котором единица стоит на позиции в. Например, при п = 5, (ез) выглядит следующим образом:

/ 0 0 0 d 0 \ 0 0 0 0 d 10000 01000 \ 0 0 1 0 0 /

Пусть x G k, M, N — подмножества поля k. Тогда положим x • M — и M + N — .

Далее, пусть a G M(n, k), A — (Ars) — квадратная таблица порядка n, состоящая из подмножеств поля k, т. е. Ars С k. Определим умножение a * A следующим образом:

a * A — B, Brs — ^ ark • Aks-fc=1

Таким образом, a * A — матрица, состоящая из подмножеств поля k. Аналогично определим A * a.

Пусть таблица A — (Ajj) состоит из подмножеств поля k. Тогда под M (A) мы понимаем множество матриц, у которых на позиции (i, j) стоит элемент из Ajj:

Квадратную таблицу A — (Ars), состоящую из подмножеств поля k, называется таблицей сетевого вида, если выполняются условия:

Arn — d 1 Ar+1,1, „ Ans — dA1,s+1

Кольцо, определяющее структуру надгрупп нерасщепимого максимального тора

Предложение 1. Пусть а £ М(п, к), А — квадратная таблица порядка п, состоящая из подмножеств поля к. Тогда аМ(А) С М(а * А). Обратное включение не всегда верно■ Далее, множество элементов, стоящих на позиции (г, в) во множестве матриц аМ (А), совпадает с множеством (а * А)„.

Доказательство теоремы вытекает из следующих двух предложений.

Предложение 2. с(ж)ас(у) £ М(а), где с(ж) £ Т, с(у) = с(ж)-1, а £ М(а).

Так как матрицы с(ж), а, с(у) имеют сетевой вид, то их произведение Е также имеет сетевой вид, поэтому включение достаточно показать для элементов первого столбца, т. е. С а51 = А5. При этом есть произведение в-ой строки матрицы с(ж) на матрицу а и на первый столбец матрицы с(у) (т. е. = с(ж)5ас(у)1).

Рассмотрим случай 1 ^ в < п:

= с(ж)5 ас(у)1 = (ж5 ,ж5-1. ж1,^жп. ^ж5+1)ас(у)1 = с(ж)5(е5+1)(е5+1)-1Ас(у)1 = й(жп,жп-1. ,ж1 )Вс(у)1.

Здесь В = (е5+1)-1 А — матрица сетевого вида (как произведение матриц сетевого вида). Первый столбец матрицы В выглядит следующим образом:

(Ая+1, А5+2. Ап, й-1 А1, й-1 А2. )т.

Обозначим через В1 = А5+1, В2 = А5+2, . Вп = й-1А5. Итак, матрица В является матрицей сетевого вида с первым столбцом: (В1, В2. Вп)т.

Далее, исходя из включений А1 С А2 С. С Ап, йАп С А1, имеем: В1 С В2 С . С Вп, йВп С В1.

Исходя из вышесказанного, получаем, что включение С А5 равносильно включению:

(жп,жп-1. ж1)^ .У2. С Вп.

При в = п получаем аналогичное включение: (жп,жп-1. ,ж1 )Ас(у)1 С Ап (т. е. при в = п матрица В совпадает с матрицей А).

Итак, доказываем, что (жп,жп-1. ,ж1)Вс(у)1 С Вп, т. е.

У] жп+1-кУгВкг С Вп.

Первый случай: к ^ г. Тогда В&г = В^ для некоторого номера Далее, сумма индексов п +1 — к + г ^ п + 1, поэтому жп+1-куг £ й.

В обоих случаях получаем включение гВт С Вп, г £ Д, которое является верным. >

Предложение 3. Если тор Т нормализует М(а) для любой сети а, то йо С й.

Из условия получаем с(ж)М(а)с(у) С М(а) для любой матрицы с(ж) £ Т. Зафиксируем позицию (г, в). Рассмотрим таблицу а’ = (а^-), где аГ5 = аГ5, остальные а- = 0. Ясно, что М(а’) С М(а) и с(ж)М(а’)с(у) С М(а).

Согласно предложению 1 множество элементов, стоящих на позиции (п, 1) во множестве матриц с(х)М(ст’)е(у), совпадает с множеством

С другой стороны, множество элементов, стоящих на позиции (п, 1) во множестве М(а), есть множество ап1 = А.

Таким образом, получаем, что хп+1_г • ув • агв с А.

Рассмотрим два случая.

Первый случай: п + 1 — г + в ^ п + 1 (т. е. г ^ в). В этом случае агв = А и хп+1_г • У в £ К.

Заменим п + 1 — г = к. Тогда получим, что при к + в ^ п +1, х&ув £ К. А при к + в > п +1, йх&ув £ К. Поэтому К0 С К. >

1. Боревич З. И. Описание подгрупп полной линейной группы, содержащих группу диагональных матриц // Зап. науч. семинаров ПОМИ.—1976.—Т. 64.—С. 12-29.

2. Боревич З. И., Койбаев В. А. О кольцах множителей, связанных с промежуточными подгруппами, для квадратичных торов // Вестн. СП6ГУ.—1993.—Т. 1, № 2.—С. 5-10.

3. Койбаев В. А., Шилов А. В. О подгруппах полной линейной группы, содержащих нерасщепимый максимальный тор // Зап. науч. семининаров ПОМИ.—2010.—Т. 375.—С. 130-138.

Статья поступила 27 февраля 2011 г.

Шилов Александр Валентинович Северо-Осетинский государственный университет им. К. Л. Хетагурова, аспирант каф. алгебры и геометрии РОССИЯ, 362040, Владикавказ, ул. Ватутина, 46

A RING DETERMINING THE STRUCTURE OF OVERGROUPS OF A NON-SPLIT MAXIMAL TORUS

We study nets and net rings associated with overgroups of a non-split maximal torus determined by with the radical extension of the main field.

Key words: intermediate subgroups, non-split maximal torus, nets, net groups, elementary group, transvection.

теория-групп — Элемент максимального порядка в группе обратимых элементов

Здравствуйте! Нужно указать элемент максимального порядка в группе обратимых элементов кольца Z560. Дано кольцо Z560. Необходимо найти максимальный порядок элемента по умножению. На данный момент результат следующий: Z560≅Z16×Z7×Z5 То есть, исходное кольцо изоморфно прямому произведению соответствующих групп. Также получена оценка сверху максимального порядка изоморфной группы: НОК(φ(2^4),φ(7),φ(5))=24 После исследования каждого кольца по отдельности, я сделала следующий вывод: в Z16 максимальный порядок 8 (элемент 3), в Z7 — это 6 (элемент 3), в Z5 — это 4 (элемент 2). делаем вывод, что элемент (3,3,2) является максимальным по умножению, далее решаю систему линейных сравнений. Буду рада, если укажете на неправильные рассуждения, скорее всего, они присутствуют.

задан 11 Июн ’20 15:22

lin
17 ● 4
0&#037 принятых

1 ответ

Тут общая идея верная, только для числа 16 получится не циклическая группа порядка 8, а группа Z4xZ2. Максимальный порядок элемента равен 4, и он достигается на элементе 3. Если заменить 24 на 12, то всё будет правильно.

отвечен 11 Июн ’20 16:01

falcao
300k ● 9 ● 38 ● 55