теория-групп — Элемент с максимальным порядком в кольце
Дано кольцо $%Z_<546>$%. Необходимо найти максимальный порядок элемента по умножению. На данный момент результат следующий: $$ Z_ <546>\cong Z_ <2>\times Z_ <3>\times Z_ <7>\times Z_<13>$$ То есть, исходное кольцо изоморфно прямому произведению соответствующих групп. Также получена оценка сверху максимального порядка изоморфной группы: $$ НОК(\varphi(2), \varphi(3), \varphi(7), \varphi(13)) = 12 $$ После исследования каждого кольца по отдельности, я сделал следующий вывод: в $% Z_<2>, Z_ <3>$% максимальный порядок 2 (элементы 1 и 2 соответственно), в $% Z_ <7>$% — это 6 (элемент 3), в $% Z_ <13>$% — это 12 (элемент 2). делаем вывод, что элемент $% (1, 2, 3, 2) $% является максимальным по умножению, но я не понимаю, как найти соответствующий элемент в $% Z_ <546>$%? Буду рад, если укажете на неправильные рассуждения, скорее всего, они присутствуют.
задан 25 Фев ’19 1:35
1 ответ
У Вас с содержательной точки зрения почти всё уже сделано, но есть ряд терминологических неточностей. Понятие порядка элемента даётся не для колец, а для групп. С кольцом связана аддитивная группа, о которой здесь речь не идёт, и мультипликативная группа, которая и имеется в виду, так как сказано про умножение. Но не уточнено, из каких элементов она состоит. Если $%R$% — кольцо с единицей, то все его обратимые элементы образуют группу относительно умножения, обозначаемую $%R^<\ast>$%, и называемую группой обратимых элементов кольца, или его мультипликативной группой.
Для колец вычетов $%\mathbb Z_n$% группа $%\mathbb Z_n^<\ast>$% состоит из $%\varphi(n)$% элементов — тех остатков, которые взаимно просты с $%n$%.
Кольцо $%\mathbb Z_<546>$% в самом деле изоморфно прямому произведению, но не групп, а колец вычетов. В то же время, его мультипликативная группа изоморфна прямому произведению мультипликативных групп сомножителей, то есть $$Z_<546>^<\ast>\cong Z_2^<\ast>\times Z_3^<\ast>\times Z_7^<\ast>\times Z_<13>^<\ast>.$$ Известно, что для простого $%p$% группа $%\mathbb Z_p^<\ast>$% является циклической, то есть обладает элементом порядка $%\varphi(p)=p-1$%. Такие элементы для каждой из компонент Вы указали верно.
Для нахождения элемента порядка 12 в группе $%\mathbb Z_<456>^<\ast>$% можно поступить чуть проще (правда, его не следует называть «максимальным по умножению» — максимален ведь не сам элемент, а его порядок в группе). Берём сначала элемент 2: он имеет требуемый порядок по модулю 13, но его брать нельзя, так как он не взаимно прост с 546. Однако, прибавляя к нему несколько раз 13, мы получаем элемент с тем же свойством. Он имеет порядок 12 по модулю 13, а потому и по «старшему» модулю 546 он не уменьшится. Увеличиться он также не может, так как значение 12 максимально. Итого имеем 2, 15, 28, 41, и на последнем элементе можно остановиться, так как он не делится ни на одно из чисел 2, 3, 7, 13.
Тем не менее, если продолжать Ваше рассуждение, то надо решить систему линейных сравнений $%x\equiv1\pmod2$%; $%x\equiv2\pmod3$%; $%x\equiv3\pmod7$%; $%x\equiv2\pmod<13>$%.
Способы решения таких систем описаны в учебниках по теории чисел. См., например у Бухштаба. Здесь можно сразу заменить второе и последнее сравнение на условие $%x\equiv2\pmod<39>$%, записать решение в виде $%x=39y+2$%, и подставить в третье сравнение. Также надо будет учесть нечётность. В итоге должно получиться значение $%x=353$%. Такой остаток существует и единственен по известной теореме (китайская теорема об остатках).
отвечен 25 Фев ’19 3:12
@falcao, подскажите пожалуйста, а как поступать в такой ситуации(звездочки чего-то не показываются, имеются в виду только обратимые элементы):
С первыми двумя множителями прямого произведения все ясно, но вот с третьим как «руками» подобрать элемент порядка $%\varphi(7^2)=42$% не очень понятно.
@Квантиль: для построения элемента порядка 42 достаточно построить элементы взаимно простых порядков 2, 3, 7 и перемножить. Для начала берём первообразный корень по модулю 7 — число a=3. Его порядок по модулю 7 равен 6. По модулю 49 порядок делится на 6. Прямая проверка показывает, что здесь он равен 42, то есть нам случайно повезло, и это уже ответ. В общем случае, если вышло 6k, то берём a^k, и это элемент порядка 6. Примером элемента порядка p=7 по модулю p^2 будет 1+p, что проверяется через биномиальную формулу. В конце берём a^k(1+p) mod p^2.
@falcao, добрый вечер. Подскажите, пожалуйста, в примере от Квантиль каким образом поступать далее? Получается, наибольший порядок элемента = 42. Для первой группы из суммы образующий элемент g = 1 (mod 2), для второй – g = 2 (mod 3) , для третьей – g = 3 (mod 49). Итого получаем систему из трёх линейных сравнений. Решением является число x = 101 (mod 294). Но при проверке и возведении икса в степень 42 по модулю 294 не получается единицы… не понимаю, где допускаю ошибку в рассуждениях.
@Kai: ответ 101 правильный. Я только что это проверил. Думаю, Вы просто ошиблись при возведении в степень.
@falcao, благодарю! Если рассматривать вопрос о перечислении всех элементов степени 42, нужно поступить следующим образом: взять 3, имеющую степень 42 по модулю 49, и прибавлять к ней 49. Получается ряд: 52, 101, 150, 199, 248. Из этих чисел только два (101, 199) являются искомыми, так как взаимно просты с модулем. Поправьте, пожалуйста, если допустила ошибку.
@Kai: задача нахождения всех элементов кольца, порядок которых в мультипликативной группе равен 42, достаточно сложна. Таких элементов много (по-моему, штук 36), и их не так просто выписать. И сам метод надо обосновывать — почему выписаны будут все такие элементы? Оба числа 101 и 199 годятся, но это явно не весь «улов».
@falcao, можете рассказать, как Вы получили 36?
Проверил на компьютере. Наверное, можно к этому числу прийти и как-то вручную при помощи стандартной техники. Но выписывать все эти значения — задача явно громоздкая.
Здравствуйте
Математика — это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Научный форум dxdy
Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".
Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.
Не ищите на этом форуме халяву , правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.
Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.
найти элемент наибольшего порядка в группе перестановок
Последний раз редактировалось PAV 24.03.2012, 09:08, всего редактировалось 3 раз(а).
— группа перестановок со стандартным произведением-композицией.
с какого боку подходят к таким вопросам?
у меня в задании конретно спрашивают про
с двумя алгебраическими операциями
,
называется ассоциативным кольцом, если в нём выполняются свойства:
является коммутативной группой по сложению с нейтральным элементом
(эта группа называется аддитивной).
и
и
называются изоморфными, если существует отображение
, являющееся изоморфизмом аддитивных и мультипликативных групп этих колец.
Определение 3.20 Полем называется кольцо
, в котором
, что
не существует. Характеристика поля может быть только простым числом или нулем.Определение 3.22 Левым (правым) идеалом кольца называется любое его подкольцо, выдерживающее умножение слева (соответственно, справа) на любой элемент кольца. Подкольцо, являющееся левым и правым идеалом, называется двусторонним идеалом, или просто идеалом.
Подкольцо
разбивает кольцо
на классы эквивалентности:
. Класс, содержащий элемент
, можно записать в виде:
Из определения идеала следует, что результат операций не зависит от выбора представителей
,
, то есть операции заданы корректно.Наиболее важными для нас будут следующие кольца и поля:
- Кольцо целых чисел
. Также это кольцо можно себе представлять, как кольцо целых неотрицательных чисел, меньших
, с операцией сложения и умножения по модулю
. Такое кольцо является полем тогда и только тогда, когда
— простое число. - Кольцо
. - Фактор-кольцо
по идеалу, порожденному одним многочленом
, то есть состоящему из всех многочленов, кратных
. Это кольцо можно также рассматривать, как кольцо многочленов степени меньше
с операцией сложения и умножения по модулю
. Такое кольцо является полем тогда и только тогда, когда многочлен
неприводим над
.
В криптографии нас будут интересовать больше всего конечные поля, то есть поля с конечным множеством
. Перечислим наиболее важные для нас свойства:- Каждое конечное поле имеет простую характеристику
. - Поле простого порядка не имеет подполей, и называется простым.
- Конечное поле характеристики
содержит подполе порядка
. - Конечное поле является линейным пространством над своим простым подполем, поэтому имеет порядок
. - Мультипликативная группа конечного поля циклическая. Если поле имеет простой порядок
, то порождающий его мультипликативную группу элемент называется примитивным корнем по модулю
. - Конечные поля одного порядка изоморфны.
Рассмотрим несколько связанных с кольцами вычетов задач, часто возникающих в криптографии.
Пример 3.5 Найти мультипликативный порядок элемента
по модулю
, то есть порядок элемента
мультипликативной группы
-ю и
-ю степень излишне — видно, что наименьшая степень, в которой 16 даст единицу по модулю 101, это 25.Пример 3.6 Найти случайный примитивный корень по модулю
.Решение. Порядок мультипликативной группы поля вычетов по модулю 883 равен
. Будем выбирать случайное число
и возводить его в степени
,
,
. Если в какой-то степени
даст единицу, то его порядок меньше 882, и, следовательно, он не является примитивным корнем по модулю 883. Наоборот, порядок порождающего элемента является делителем числа 882, и если он не является делителем ни одного из чисел
,
,
, то равен 882. В первой колонке таблицы приводятся случайно выбранные элементы
, а в следующих колонках — результаты возведения в степень.- Кольцо целых чисел