Порядок элемента группы

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

Миша, Вы напишите условие задачи. А то так, в общем, трудно что-то ответить.

Если порядок элемента конечный — то наивным возведением в степень можно найти его порядок. Правда конечный — не значит маленький, так что может и не сработать на практике.

Если о группе что-то известно — часто можно дать эффективные ответы на оба Ваших вопроса. Скорее всего Ваши группы — именно такие: либо группы вычетов либо подгруппы симметрической группы малого порядка.

Группа вычетов по модулю. У меня лично модуль 527.

Группа по сложению?

Почти наверное по сложению — иначе нулевым вопросом был бы порядок группы :)

527 = 17*31.

0 — порядка 1;
31k, 1<=k<=16 — порядка 17, всего 16 штук;
17m, 1<=m<=30 — поррядка 31, всего 30 штук;
остальные 480 — порядка 527, эти остальные тоже можно охарактеризовать одним словом в терминах делимости.

Мне ведь нужен не ответ, а научиться решать. Может быть , Вы покажете, как Вы это сделали.

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

Чтобы что-то показывать — нужно знать, что Вы знаете или не знаете и где у Вас камень преткновения образовался.

По сложению: порядок элемента a — это такое число n, что an делится на 527, а ak не делится на 527, если 1<=k<=(n-1).

По умножению: порядок элемента a — это такое число n, что ((a^n)-1) делится на 527, а ((a^k)-1) не делится на 527, если 1<=k<=(n-1). Конечно, НОД(a,527)=1, иначе a — не элемент искомой группы.

Предположим, что Вы умеете искать порядок элемента a в группах вычетов по модулям 17 и 31. Если эти порядки — u и v, то порядок a в Вашей группе — это НОК(u,v).

Также для того, чтобы искать порядок, полезна теорема Лагранжа: порядок элемента делит порядок группы. Конечно, применять ее надо по маленьким модулям, а не по 527.

А теперь рассказывайте, что конкретно Вам непонятно в написанном и что еще Вы хотите услышать?

Если так, то группа циклическая.
Найдите образующий элемент. Те его степени, которые взаимно просты с порядком группы, будут иметь порядок 480. Если степень элемента — делитель 480, скажем, n то есть для некоторого m nm=480, то порядок этого элемента равен m.

Разумеется, группа нециклическая. И максимальный порядок элемента в ней — 240.
Порядок группы — да, 480.

Вообще-то строение групп вычетов и то, когда они циклические — это неотъемлемая часть любого около-математического образования.

Алексей Владимирович, пост #11 написан в ответ на #9, причем в тексте это явно указано: "Если так, то...".

Зачем предполагать заведомо неверные вещи и давать заведомо невыполнимые советы?

Для начала используйте : порядок элемента является делителем функции Эйлера.

Что-то Вы меня совсем запутали. Мне подсказали, что в группе есть элемент, имеющий порядок 480. Это так? Ведь Anonimus Vulgaris пишет, максимальный порядок в ней 240. Так что же верно?.

Тот, кто Вам это подсказал — жестоко ошибается. Либо Вы сами неправильно поняли подсказку — Вам могли сказать, что порядок группы — 480, а Вы это поняли как "максимальный порядок элемента".

Зато теперь у Вас есть хороший повод самостоятельно понять, почему прав Anonimus, а не неизвестный подсказчик. Как Вы при этом будете действовать — в конкретных терминах делимости или в абстрактных прямых суммах групп — вопрос вторичный и чисто технический. Я бы Вам посоветовал пока не усугублять с абстракцией.

Хочешь все увидеть и почувствовать проведи лабораторную работу как в ИКСИ. В Exele сделай элементарную программу возведения в степень по модулю. В твоем случае сразу увидишь, что порядок,например элемента 2 равен 40, а 5 равен 48. Действительно они являются делителями функции Эйлера для 527, она равна 480.

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

Скорее всего по сложению — о чем я и сказал в №7.

Хотя, если специальность около-криптографическая — группа по умножению будет актуальнее.

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

Другой вопрос — зачем пускать изучение теории групп на самотек?

Действительно, мы ( с братом) учимся на информационной безопасности в МИРЭА. У нас лектор из ВШЭ, он сам признался, что он спец по матану -, линейной алгебре и аналитической геометрии. А должна быть общая алгебра. Поэтму самообучаемся.
Я сам понял, что не всякая группа вычетов по модулю является циклической. Теперь еще возник вопрос: а какой может быть максимальный порядок элемента при заданном порядке группы, в моем случае 480. Почему он 240, как это узнать.
А программу в Exel попробую сделать, недавно изучали.

Наберите в поисковике мультипликативная группа вычетов

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

А 240 он потому, что 240 = НОК(16,30). Z17 и Z31 — циклические группы по умножению, пусть Z17 = <a>, Z31= <b>, 2<=a<=15, 2<=b<=29. Тогда любое натуральное число с, такое, что
1<=c<=527; НОД(с,527)=1 представимо в виде с=(a^k)(mod 17), c=(b^m)(mod 31) и его порядок моментально находится (если поищите в этой ветке — даже формулу сможете собрать). Главное — число с k=m=1 тоже есть и его порядок ровно 240, а порядок всех остальных 240 не превосходит (поймете, когда соберете формулу).


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

Присоединяюсь к совету Anonimus Vulgaris ( не обращая внимание на понятные только мне его замечания о реинкарнации)- учиться не по интернету и Википедии, а по учебникам.
В ИКСИ используется учебник Кострикина и Глухова, Елизарова, Нечаева.
Я бы порекомндовал:
Математические и компьютерные основы криптологии. Учебное пособие

Авторы: Ю. С. Харин, В. И. Берник, Г. В. Матвеев, С. В. Агиевич

Харин Ю. С. Компьютерный практикум по математическим методам защиты информации: Учеб. пособие / Ю. С. Харин. С. В. Агиевич. — Мн.: БГУ, 2001. — 190 с.: ил.
ISBN 985-445-217-4
Данное учебное пособие является первым отечественным компьютерным практикумом по новому актуальному направлению прикладной ма тематики — математическим методам защиты информации. Содержит свыше 200 заданий по всем основным разделам криптологии, а также модели, методы и алгоритмы, необходимые для выполнения этих заданий в рамках лабораторных занятий на компьютере. Приводится описание оригинального пакета прикладных программ «КриптоЛаборатория». поддерживающего компьютерный практикум.
Для студентов бакалаврского и магистерского уровней, аспирантов, обучающихся: по математическим и инженерно-техническим специальностям, слушателей факультетов переподготовки и повышения квалификации, а также для специалистов в области прикладной математики, информатики и электроники, желающих познакомиться с математическими методами защиты информации.

Также верно, что при модуле 527 максимальный порядок элемента никак не 480, а именно 240, т.к. 527=17*31.

Спасибо за литературу.
Но хотя на такие вопросы можно ответить. Можно ли как-то узнать , какой элемент группы является порождающим.
Если я нашел порядок одного элемента. Сколько всего будет элементов с таким же порядком. Например, я сделал программу на Exel и подтвердил, что порядок элемента 2 есть 40 при модуле 527. Так сколько всего при этом будет элементов с порядком 40, можно ли их все указать.

Если группа не циклическая, то она не порождается одним элементом.

Считай функцию Эйлера от 40

Не спасет — это даст только часть элементов порядка 40. (Те, которые порождены двойкой)

Например, 461 имеет порядок 40, но не является степенью двойки (mod 527) :)

Ну и как же быть. ?? Наверное же есть теория?.

Вся потребная Вам теория изложена в успешно заминусованном №10.
Если столь краткое изложение для Вас не подходит — Вам, тем более, надо читать учебники, где все тоже самое рассказывается очень подробно.

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

А вот, что мне попалось при изучении теории кодирования
Введение в алгебраические коды
Сагалович Ю.Л.
4 октября 2011 г
Утверждение 1.11.6. В приведенной системе вычетов по модулю m количество чисел, принадлежащих показателю δ, есть
φ(δ.)
Как с этим быть?

1. Внимательно прочитать, что там написано и понять, то ли Вы не поняли утверждения, то ли Сагалович ошибся.

2. Взять небольшую группу вычетов по составному модулю и экспериментальным порядком убедиться, что число элементов порядка k не обязано быть равным phi(k).

Минимальный контр-пример — Z/8Z по умножению. В этой группе 4 элемента, 1 — порядка 1 и 3 — порядка 2. И 3 не равно phi(2).

3. Еще раз перечитать учебник, и, если 1.11.6 утверждает именно то, что написано в №31 — выкинуть учебник на помойку. Хотя, почти уверен, что в учебнике написано какое-то верное утверждение, например: число элементов порядка k в группе вычетов по ПРОСТОМУ модулю p по умножению равно phi(k), для всех k, делящих (p-1).

Сам прочитал. Разумеется, Сагалович прав, а Вы невнимательны. Рекомендую к прочтению 1.1.15 :) Откуда сразу ясно, что в 1.1.16 рассматриваются только такие m, для которых Z/mZ циклическая (и все эти варианты в 1.1.15 перечислены :) )

1.1.15 читать как 1.11.5, конечно :)

Спасибо. Более или менее разобрался. У всех были простые модули-там все проще, а умня составной.
Теперь вот выдали следующий типовик, полная темень для всех.
Может я его выложу, поможете??????!!!!!!!!!!!!!!!!!

Если Вам ответят "нет" — не выложите? :)
Покажите уж, посмотрим.

Могу предложить свое(в соавторстве с коллегой) пособие по основам криптографии. Вопросы, рассмотренные выше и близкие к ним, подробно изложены. Отправлю ответом на письмо. Пишите.

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

помогите понять как находить обратные элементы в группе вычетов по модулю ,например, в Z8 обратные {-2,-1} , а в Z7 {-3,-2,-1} Спасибо

найти в группе А12 элемент max порядка (12 в коэф., это группа четных перестановок)
я знаю как найти порядок всей группы, но не могу понять как именно элемента т.к. их очень много это не реально.

Помогите, плз, с задачей.

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

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

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

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

Как из кольца вычетов по заданному модулю сделать группу. С чего начать?