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

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

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

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

Имеется в виду аддитивная группа? (Если модуль 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.
А вдруг так никто не делал, я не видел.

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

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

Добрый день!
Подскажите пожалуйста алгоритм решения двух следующих задач или хотя бы с чего начать.

1. Указать элемент максимального порядка в группе обратимых элементов Z462 (*) кольца Z462 (и Z462 (*) и Z462 это остатки от деления по модулю 462). Доказать что его порядок действительно максимален.
Понял, что порядок это степень, при возведении в которую элемента получается 1 но как сделать задачу непонятно.

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

В группе GL2(Q) найти элемент конечного порядка, отличный от нейтрального
В группе GL2(Q) найти элемент конечного порядка, отличный от нейтрального

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

Сколько элементов порядка 4 в группе
Сколько элементов порядка 4 в \mathbb^* Мне кажется, что таких элемента два. А какие?

Сколько элементов порядка 6 содержится в группе?
Сколько элементов порядка 6 содержится в группе D2(C), где Dn(F)- группа невырожденных диагональных.

2703 / 1759 / 184
Регистрация: 05.06.2011
Сообщений: 5,078

1. Как понимаю, только полный перебор. Ну, не всех, естественно, остатков, только взаимно простых с 462. Опять же, если , то 25 можно не проверять. Метод не для ручного счёта, естественно.
Максимальная степень — делитель (посмотри функцию Эйлера), хотя это не сильно сокращает перебор. Впрочем, если дойдёшь до степени, большей наибольшего нетривиального делителя, значит, дальше можно не считать.

4162 / 3034 / 914
Регистрация: 19.11.2012
Сообщений: 6,178

Есть метод для счета в уме. Замечаем, что 462=2*3*7*11. По китайской теореме об остатках на языке колец

Тогда мультипликативная группа заданного кольца изоморфна прямому произведению мультипликативных групп сомножителей. Отсюда максимальный порядок это 30. Ну и указать элемент порядка 30 не составляет труда.
Например 5. Как проверить? А по каждому модулю 2,3,7,11 поочередно.

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

В данной квадратной матрице порядка 17 указать индексы всех элементов с наименьшим значением
В данной квадратной матрице порядка 17 указать индексы всех элементов с наименьшим значением

В данной квадратной целочисленной матрице порядка 17 указать индексы всех элементов с наибольшим значением
В данной квадратной целочисленной матрице порядка 17 указать индексы всех элементов с наибольшим.

Или воспользуйтесь поиском по форуму:

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

Дано кольцо $%Z_$%. Необходимо найти максимальный порядок элемента по умножению. На данный момент результат следующий: $$ Z_ \cong Z_ \times Z_ \times Z_ \times Z_$$ То есть, исходное кольцо изоморфно прямому произведению соответствующих групп. Также получена оценка сверху максимального порядка изоморфной группы: $$ НОК(\varphi(2), \varphi(3), \varphi(7), \varphi(13)) = 12 $$ После исследования каждого кольца по отдельности, я сделал следующий вывод: в $% Z_, Z_ $% максимальный порядок 2 (элементы 1 и 2 соответственно), в $% Z_ $% — это 6 (элемент 3), в $% Z_ $% — это 12 (элемент 2). делаем вывод, что элемент $% (1, 2, 3, 2) $% является максимальным по умножению, но я не понимаю, как найти соответствующий элемент в $% Z_ $%? Буду рад, если укажете на неправильные рассуждения, скорее всего, они присутствуют.

задан 25 Фев ’19 1:35

1 ответ

У Вас с содержательной точки зрения почти всё уже сделано, но есть ряд терминологических неточностей. Понятие порядка элемента даётся не для колец, а для групп. С кольцом связана аддитивная группа, о которой здесь речь не идёт, и мультипликативная группа, которая и имеется в виду, так как сказано про умножение. Но не уточнено, из каких элементов она состоит. Если $%R$% — кольцо с единицей, то все его обратимые элементы образуют группу относительно умножения, обозначаемую $%R^$%, и называемую группой обратимых элементов кольца, или его мультипликативной группой.

Для колец вычетов $%\mathbb Z_n$% группа $%\mathbb Z_n^$% состоит из $%\varphi(n)$% элементов — тех остатков, которые взаимно просты с $%n$%.

Кольцо $%\mathbb Z_$% в самом деле изоморфно прямому произведению, но не групп, а колец вычетов. В то же время, его мультипликативная группа изоморфна прямому произведению мультипликативных групп сомножителей, то есть $$Z_^\cong Z_2^\times Z_3^\times Z_7^\times Z_^.$$ Известно, что для простого $%p$% группа $%\mathbb Z_p^$% является циклической, то есть обладает элементом порядка $%\varphi(p)=p-1$%. Такие элементы для каждой из компонент Вы указали верно.

Для нахождения элемента порядка 12 в группе $%\mathbb Z_^$% можно поступить чуть проще (правда, его не следует называть «максимальным по умножению» — максимален ведь не сам элемент, а его порядок в группе). Берём сначала элемент 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$%.

Способы решения таких систем описаны в учебниках по теории чисел. См., например у Бухштаба. Здесь можно сразу заменить второе и последнее сравнение на условие $%x\equiv2\pmod$%, записать решение в виде $%x=39y+2$%, и подставить в третье сравнение. Также надо будет учесть нечётность. В итоге должно получиться значение $%x=353$%. Такой остаток существует и единственен по известной теореме (китайская теорема об остатках).

отвечен 25 Фев ’19 3:12

falcao
300k ● 9 ● 38 ● 55

@falcao, подскажите пожалуйста, а как поступать в такой ситуации(звездочки чего-то не показываются, имеются в виду только обратимые элементы):

С первыми двумя множителями прямого произведения все ясно, но вот с третьим как «руками» подобрать элемент порядка $%\varphi(7^2)=42$% не очень понятно.

(22 Фев ’20 1:18) Квантиль

@Квантиль: для построения элемента порядка 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.

(22 Фев ’20 1:28) falcao

@falcao, добрый вечер. Подскажите, пожалуйста, в примере от Квантиль каким образом поступать далее? Получается, наибольший порядок элемента = 42. Для первой группы из суммы образующий элемент g = 1 (mod 2), для второй – g = 2 (mod 3) , для третьей – g = 3 (mod 49). Итого получаем систему из трёх линейных сравнений. Решением является число x = 101 (mod 294). Но при проверке и возведении икса в степень 42 по модулю 294 не получается единицы… не понимаю, где допускаю ошибку в рассуждениях.

(7 Ноя ’21 1:42) Kai

@Kai: ответ 101 правильный. Я только что это проверил. Думаю, Вы просто ошиблись при возведении в степень.

(7 Ноя ’21 1:49) falcao

@falcao, благодарю! Если рассматривать вопрос о перечислении всех элементов степени 42, нужно поступить следующим образом: взять 3, имеющую степень 42 по модулю 49, и прибавлять к ней 49. Получается ряд: 52, 101, 150, 199, 248. Из этих чисел только два (101, 199) являются искомыми, так как взаимно просты с модулем. Поправьте, пожалуйста, если допустила ошибку.

(7 Ноя ’21 2:03) Kai

@Kai: задача нахождения всех элементов кольца, порядок которых в мультипликативной группе равен 42, достаточно сложна. Таких элементов много (по-моему, штук 36), и их не так просто выписать. И сам метод надо обосновывать — почему выписаны будут все такие элементы? Оба числа 101 и 199 годятся, но это явно не весь «улов».

(7 Ноя ’21 3:20) falcao

@falcao, можете рассказать, как Вы получили 36? ��

(7 Ноя ’21 5:52) Kai

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

(7 Ноя ’21 6:43) falcao
показано 5 из 8 показать еще 3

Здравствуйте

Математика — это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

задан
25 Фев ’19 1:35

показан
4622 раза

обновлен
7 Ноя ’21 6:43

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

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

Решение

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

Алгоритм

1. Найти все делители [math]|G|[/math] перебором от 1 до [math]\sqrt<|G|>[/math]
2. Для каждого делителя [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] .