СПРОСИ ПРОФИ
👍
+1
👎 137

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

Как найти именно наименьший порядок элемента группы. Как найти все элементы заданного порядка в группе.
В типовом домашнем задании эти задачи есть, а лекции только по линейной алгебре. Лектор говорит, чтобы общую алгебру мы изучали самостоятельно. Наверное, сам не знает. Вот такое обучение в ВУЗе.
теория групп алгебра математика обучение     #1   14 окт 2013 15:57   Увидели: 395 клиентов, 6 специалистов   Ответить
👍
+1
👎 1
Миша, Вы напишите условие задачи. А то так, в общем, трудно что-то ответить.
👍
+1
👎 1
Если порядок элемента конечный — то наивным возведением в степень можно найти его порядок. Правда конечный — не значит маленький, так что может и не сработать на практике.

Если о группе что-то известно — часто можно дать эффективные ответы на оба Ваших вопроса. Скорее всего Ваши группы — именно такие: либо группы вычетов либо подгруппы симметрической группы малого порядка.
  #3   14 окт 2013 16:27   Ответить
👍
+1
👎 1
Группа вычетов по модулю. У меня лично модуль 527.
  #4   14 окт 2013 16:30   Ответить
👍
+1
👎 1
Группа по сложению?
👍
+1
👎 1
Почти наверное по сложению — иначе нулевым вопросом был бы порядок группы :)

527 = 17*31.

0 — порядка 1;
31k, 1<=k<=16 — порядка 17, всего 16 штук;
17m, 1<=m<=30 — поррядка 31, всего 30 штук;
остальные 480 — порядка 527, эти остальные тоже можно охарактеризовать одним словом в терминах делимости.
  #7   14 окт 2013 20:25   Ответить
👍
+3
👎 3
Мне ведь нужен не ответ, а научиться решать. Может быть , Вы покажете, как Вы это сделали.
  #8   15 окт 2013 10:09   Ответить
👍
0
👎 0
Все же я думаю, что группа у меня по умножению. Мне подсказали, что максимальный порядок 480.
  #9   15 окт 2013 10:15   Ответить
👍
0
👎 0
Чтобы что-то показывать — нужно знать, что Вы знаете или не знаете и где у Вас камень преткновения образовался.

По сложению: порядок элемента 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.

А теперь рассказывайте, что конкретно Вам непонятно в написанном и что еще Вы хотите услышать?
  #10   15 окт 2013 13:20   Ответить
👍
+2
👎 2
Если так, то группа циклическая.
Найдите образующий элемент. Те его степени, которые взаимно просты с порядком группы, будут иметь порядок 480. Если степень элемента — делитель 480, скажем, n то есть для некоторого m nm=480, то порядок этого элемента равен m.
👍
0
👎 0
Разумеется, группа нециклическая. И максимальный порядок элемента в ней — 240.
Порядок группы — да, 480.

Вообще-то строение групп вычетов и то, когда они циклические — это неотъемлемая часть любого около-математического образования.
  #12   15 окт 2013 13:44   Ответить
👍
+2
👎 2
Алексей Владимирович, пост #11 написан в ответ на #9, причем в тексте это явно указано: "Если так, то...".
👍
0
👎 0
Зачем предполагать заведомо неверные вещи и давать заведомо невыполнимые советы?
  #15   15 окт 2013 15:08   Ответить
👍
0
👎 0
Для начала используйте : порядок элемента является делителем функции Эйлера.
  #5   14 окт 2013 16:51   Ответить
👍
+2
👎 2
Что-то Вы меня совсем запутали. Мне подсказали, что в группе есть элемент, имеющий порядок 480. Это так? Ведь Anonimus Vulgaris пишет, максимальный порядок в ней 240. Так что же верно?.
  #14   15 окт 2013 14:56   Ответить
👍
0
👎 0
Тот, кто Вам это подсказал — жестоко ошибается. Либо Вы сами неправильно поняли подсказку — Вам могли сказать, что порядок группы — 480, а Вы это поняли как "максимальный порядок элемента".

Зато теперь у Вас есть хороший повод самостоятельно понять, почему прав Anonimus, а не неизвестный подсказчик. Как Вы при этом будете действовать — в конкретных терминах делимости или в абстрактных прямых суммах групп — вопрос вторичный и чисто технический. Я бы Вам посоветовал пока не усугублять с абстракцией.
  #16   15 окт 2013 15:13   Ответить
👍
0
👎 0
Хочешь все увидеть и почувствовать проведи лабораторную работу как в ИКСИ. В Exele сделай элементарную программу возведения в степень по модулю. В твоем случае сразу увидишь, что порядок,например элемента 2 равен 40, а 5 равен 48. Действительно они являются делителями функции Эйлера для 527, она равна 480.
  #17   15 окт 2013 15:13   Ответить
👍
+2
👎 2
Надеюсь, что подсказчик ошибся и с порядком тоже, то есть группа все же по сложению.
Иначе совершенно непонятно, как можно давать такие задачи при том, что теории групп не учат вообще.
👍
−1
👎 -1
Скорее всего по сложению — о чем я и сказал в №7.

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

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

Другой вопрос — зачем пускать изучение теории групп на самотек?
  #19   15 окт 2013 15:48   Ответить
👍
0
👎 0
Действительно, мы ( с братом) учимся на информационной безопасности в МИРЭА. У нас лектор из ВШЭ, он сам признался, что он спец по матану -, линейной алгебре и аналитической геометрии. А должна быть общая алгебра. Поэтму самообучаемся.
Я сам понял, что не всякая группа вычетов по модулю является циклической. Теперь еще возник вопрос: а какой может быть максимальный порядок элемента при заданном порядке группы, в моем случае 480. Почему он 240, как это узнать.
А программу в Exel попробую сделать, недавно изучали.
  #20   15 окт 2013 16:53   Ответить
👍
0
👎 0
Наберите в поисковике мультипликативная группа вычетов
👍
+1
👎 1
Только не начинайте обучение с поисковиков и википедии. Почитайте нормальные книжки. Винберг, например, или Кострикин. Первая более математизирована, вторая — более "народная", но на вкус и цвет.... Ваши проблемы адекватно покроет любая.

А 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 не превосходит (поймете, когда соберете формулу).


Пишу все это на случай, если Вы действительно студент Миша, а не очередная инкарнация господина К-ва. И больше в данной ветке писать не планирую — информации уже более чем достаточно.
  #22   15 окт 2013 17:26   Ответить
👍
0
👎 0
Присоединяюсь к совету Anonimus Vulgaris ( не обращая внимание на понятные только мне его замечания о реинкарнации)- учиться не по интернету и Википедии, а по учебникам.
В ИКСИ используется учебник Кострикина и Глухова, Елизарова, Нечаева.
Я бы порекомндовал:
Математические и компьютерные основы криптологии. Учебное пособие

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

Харин Ю. С. Компьютерный практикум по математическим методам защиты информации: Учеб. пособие / Ю. С. Харин. С. В. Агиевич. — Мн.: БГУ, 2001. — 190 с.: ил.
ISBN 985-445-217-4
Данное учебное пособие является первым отечественным компьютерным практикумом по новому актуальному направлению прикладной ма тематики — математическим методам защиты информации. Содержит свыше 200 заданий по всем основным разделам криптологии, а также модели, методы и алгоритмы, необходимые для выполнения этих заданий в рамках лабораторных занятий на компьютере. Приводится описание оригинального пакета прикладных программ «КриптоЛаборатория». поддерживающего компьютерный практикум.
Для студентов бакалаврского и магистерского уровней, аспирантов, обучающихся: по математическим и инженерно-техническим специальностям, слушателей факультетов переподготовки и повышения квалификации, а также для специалистов в области прикладной математики, информатики и электроники, желающих познакомиться с математическими методами защиты информации.
  #23   16 окт 2013 10:16   Ответить
👍
0
👎 0
Также верно, что при модуле 527 максимальный порядок элемента никак не 480, а именно 240, т.к. 527=17*31.
  #24   16 окт 2013 10:20   Ответить
👍
0
👎 0
Спасибо за литературу.
Но хотя на такие вопросы можно ответить. Можно ли как-то узнать , какой элемент группы является порождающим.
Если я нашел порядок одного элемента. Сколько всего будет элементов с таким же порядком. Например, я сделал программу на Exel и подтвердил, что порядок элемента 2 есть 40 при модуле 527. Так сколько всего при этом будет элементов с порядком 40, можно ли их все указать.
  #25   16 окт 2013 18:42   Ответить
👍
+2
👎 2
Если группа не циклическая, то она не порождается одним элементом.
👍
0
👎 0
Считай функцию Эйлера от 40
  #27   17 окт 2013 14:10   Ответить
👍
+1
👎 1
Не спасет — это даст только часть элементов порядка 40. (Те, которые порождены двойкой)

Например, 461 имеет порядок 40, но не является степенью двойки (mod 527) :)
  #28   17 окт 2013 17:34   Ответить
👍
0
👎 0
Ну и как же быть. ?? Наверное же есть теория?.
  #29   17 окт 2013 18:53   Ответить
👍
+1
👎 1
Вся потребная Вам теория изложена в успешно заминусованном №10.
Если столь краткое изложение для Вас не подходит — Вам, тем более, надо читать учебники, где все тоже самое рассказывается очень подробно.

Не хотите читать учебники — разбирайтесь сами. Для начала забудьте про 527 и разберитесь, сколько элементов какого порядка есть в группе вычетов по простому модулю. И как эти элементы задать в явном виде, если они, для чего-то кому-то нужны.
  #30   17 окт 2013 19:08   Ответить
👍
0
👎 0
А вот, что мне попалось при изучении теории кодирования
Введение в алгебраические коды
Сагалович Ю.Л.
4 октября 2011 г
Утверждение 1.11.6. В приведенной системе вычетов по модулю m количество чисел, принадлежащих показателю δ, есть
φ(δ.)
Как с этим быть?
  #31   20 окт 2013 16:01   Ответить
👍
+1
👎 1
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).
  #32   20 окт 2013 23:58   Ответить
👍
+1
👎 1
Сам прочитал. Разумеется, Сагалович прав, а Вы невнимательны. Рекомендую к прочтению 1.1.15 :) Откуда сразу ясно, что в 1.1.16 рассматриваются только такие m, для которых Z/mZ циклическая (и все эти варианты в 1.1.15 перечислены :) )
  #33   21 окт 2013 00:11   Ответить
👍
+1
👎 1
1.1.15 читать как 1.11.5, конечно :)
  #34   21 окт 2013 00:16   Ответить
👍
0
👎 0
Спасибо. Более или менее разобрался. У всех были простые модули-там все проще, а умня составной.
Теперь вот выдали следующий типовик, полная темень для всех.
Может я его выложу, поможете??????!!!!!!!!!!!!!!!!!
  #35   22 окт 2013 12:33   Ответить
👍
0
👎 0
Если Вам ответят "нет" — не выложите? :)
Покажите уж, посмотрим.
👍
+1
👎 1
Могу предложить свое(в соавторстве с коллегой) пособие по основам криптографии. Вопросы, рассмотренные выше и близкие к ним, подробно изложены. Отправлю ответом на письмо. Пишите.
👍
0
👎 0
А где можно ознакомиться с Вашим пособием. Чем оно отличается от материалов, написанных профессионалами в криптологии. Вы же не из этой среды.

Задайте свой вопрос по математике
профессионалам

Сейчас онлайн 75 репетиторов по математике
Получите ответ профи быстро и бесплатно

Другие вопросы на эту тему:

👍
0
👎 01

Как находить обратные элементы в группе вычетов по модулю   1 ответ

помогите понять как находить обратные элементы в группе вычетов по модулю ,например, в Z8 обратные {-2,-1} , а в Z7 {-3,-2,-1} Спасибо
  30 окт 2016 01:08  
👍
0
👎 04

Линейная алгебра   4 ответа

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

Теория групп — не могу решить задачу   20 ответов

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

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

С ассоцитивностью понятно все. Она наследуется из группы перестановок.
Не понимаю, как просто из того, что А замкнуто относительно операции умножения, взять нейтральный и обратный элементы.
  25 мар 2013 22:54  
👍
0
👎 09

Треугольник наименьшего периметра.   9 ответов

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

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

Как найти порядок элемента группы. Число элементов в группе задано. Как найти элемент, имеющий максимальный порядок.Чему равен этот максимальный порядок. Есть ли методы- не просто переборные?
  08 апр 2012 11:39  
👍
0
👎 013

Группы   13 ответов

Как из кольца вычетов по заданному модулю сделать группу. С чего начать?
  31 мар 2012 11:08  
ASK.PROFI.RU © 2020-2022