Перейти к содержимому

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

  • автор:

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

Дано кольцо $%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 раз(а).

$S_n$— группа перестановок со стандартным произведением-композицией.

с какого боку подходят к таким вопросам?
у меня в задании конретно спрашивают про $S_<14>$» /><br />количество вариантов 14! но что мне это даёт?<br />надо представить в виде произведения непересекающихся циклов?</p>
<p>не понимаю в общем, хоть это и всего лишь 1/4 вопроса и видимо не должно быть сложно технически.</p>
<h2>Порядок элемента</h2>
<p>Аддитивная группа кольца вычетов по модулю m — циклическая, <br />в ней есть элементы порядка m, но могут быть и элементы <br />меньшего порядка, их порядки должны быть делителями числа m.</p>
<p>Но только если модуль составной, то это всё-таки не группа. <br />(Но можно рассмотреть группу обратимых элементов.)</p>
<p>Игорь? А можно ли задать Вам вопрос? <br />Почему Вы не можете сразу написать всю задачу целиком? <br />Вы уже написали три поста, а что дано, что требуется, до сих пор не ясно.</p>
<p>Есть методы "умно-переборные", основанные на теор. Лагранжа: порядок элемента делит порядок группы. Если известно разложение порядка группы на множители — перебор можно существенно сократить.</p>
<p>Универсального непереборного метода нет. Наверное, его и вообще быть не может.</p>
<h3>Задайте свой вопрос по математике <br />профессионалам</h3>
<h4><i>Другие вопросы на эту тему:</i></h4>
<h4>Порядок элемента группы </h4>
<h4>Линейная алгебра </h4>
<h4>Теория групп — не могу решить задачу </h4>
<p>Помогите, плз, с задачей.</p>
<p>Доказать, что конечное множество перестановок А является группой относительно операции умножения перестановок, если произведение любой пары элементов из А принадлежит А.</p>
<p>С ассоцитивностью понятно все. Она наследуется из группы перестановок.<br />Не понимаю, как просто из того, что А замкнуто относительно операции умножения, взять нейтральный и обратный элементы.</p>
<h2>Алгебраические системы</h2>
<p><b>Определение 3.18</b> <i>Множество <img decoding=с двумя алгебраическими операциями +, \timesназывается ассоциативным кольцом, если в нём выполняются свойства:

  1. Fявляется коммутативной группой по сложению с нейтральным элементом 0(эта группа называется аддитивной).
  2. F<\setminus>\<0\>» /> является полугруппой (обозначается <img decoding=и a\times \left(b+c\right)=a\times b+a\times c<\forall>a,b,c \in F» />.</i></li>
</ol>
<p><b>Определение 3.19</b> <i>Кольца <img decoding=и Fназываются изоморфными, если существует отображение \varphi :K\rightarrow F, являющееся изоморфизмом аддитивных и мультипликативных групп этих колец.

    Определение 3.20 Полем называется кольцо F, в котором <F>^<*>» /> является коммутативной группой.</i></p>
<p><b>Определение 3.21</b> <i>Характеристикой поля называется наименьшее такое натуральное число <img decoding=, что p \cdot 1=1+1+1+<\dots>+1=0″ />, или 0, если такого <img decoding=не существует. Характеристика поля может быть только простым числом или нулем.

    Определение 3.22 Левым (правым) идеалом кольца называется любое его подкольцо, выдерживающее умножение слева (соответственно, справа) на любой элемент кольца. Подкольцо, являющееся левым и правым идеалом, называется двусторонним идеалом, или просто идеалом.

    Подкольцо Iразбивает кольцо Kна классы эквивалентности: a \equiv b\Leftrightarrow a-b \in I. Класс, содержащий элемент a, можно записать в виде:

    a+I=\left\<a+x\right|x \in I\>.» /></p>
<p>Если подкольцо является идеалом, то на множестве таких классов можно ввести операции сложения и умножения, относительно которых множество классов образует кольцо, называемое фактор-кольцом:</p>
<p><img decoding=

    Из определения идеала следует, что результат операций не зависит от выбора представителей a, b, то есть операции заданы корректно.

    Наиболее важными для нас будут следующие кольца и поля:

    1. Кольцо целых чисел \mathbb<Z>» /> относительно обыкновенных операций сложения и умножения.</li>
<li>Поле рациональных чисел <img decoding=. Также это кольцо можно себе представлять, как кольцо целых неотрицательных чисел, меньших n, с операцией сложения и умножения по модулю n. Такое кольцо является полем тогда и только тогда, когда n— простое число.
    2. Кольцо F[<x_1,<\dots>, x_n>]» /> многочленов от переменных <img decoding=.
    3. Фактор-кольцо F[<x>] / f(x) F[x]» /> кольца многочленов над полем <img decoding=по идеалу, порожденному одним многочленом <f>(<x>)» /> степени <img decoding=, то есть состоящему из всех многочленов, кратных f(x). Это кольцо можно также рассматривать, как кольцо многочленов степени меньше dс операцией сложения и умножения по модулю f(x). Такое кольцо является полем тогда и только тогда, когда многочлен f(x)неприводим над F.

    В криптографии нас будут интересовать больше всего конечные поля, то есть поля с конечным множеством F. Перечислим наиболее важные для нас свойства:

    1. Каждое конечное поле имеет простую характеристику p.
    2. Поле простого порядка не имеет подполей, и называется простым.
    3. Конечное поле характеристики pсодержит подполе порядка p.
    4. Конечное поле является линейным пространством над своим простым подполем, поэтому имеет порядок 

<p>^<n>» /> для некоторого натурального числа <img decoding=.
    5. Мультипликативная группа конечного поля циклическая. Если поле имеет простой порядок p, то порождающий его мультипликативную группу элемент называется примитивным корнем по модулю p.
    6. Конечные поля одного порядка изоморфны.

    Рассмотрим несколько связанных с кольцами вычетов задач, часто возникающих в криптографии.

    Пример 3.5 Найти мультипликативный порядок элемента 16по модулю 101, то есть порядок элемента 16мультипликативной группы \mathbb<Z>_<101>» />.</i></p>
<p><b>Решение.</b> Поскольку число 101 простое, порядок мультипликативной группы поля <img decoding=-ю и 100-ю степень излишне — видно, что наименьшая степень, в которой 16 даст единицу по модулю 101, это 25.

    Пример 3.6 Найти случайный примитивный корень по модулю 883.

    Решение. Порядок мультипликативной группы поля вычетов по модулю 883 равен 882=2 \cdot 9 \cdot 49. Будем выбирать случайное число xи возводить его в степени 882/2, 882/3, 882/7. Если в какой-то степени xдаст единицу, то его порядок меньше 882, и, следовательно, он не является примитивным корнем по модулю 883. Наоборот, порядок порождающего элемента является делителем числа 882, и если он не является делителем ни одного из чисел 882/2, 882/3, 882/7, то равен 882. В первой колонке таблицы приводятся случайно выбранные элементы x, а в следующих колонках — результаты возведения в степень.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *