Циклическая группа

[NchK]

Доброго времени суток!
Заранее извините за неточные определения, так как я далеко не математик и даже близко не стою с ним.
Имеется кольцевая группа порожденная элементом равным 9 взятая по модулю.
При модуле 11 она выглядит так:
$G=(9, 4, 3, 5, 1)$
Так как $9^1 \mod 11 =9$
$9^2 \mod 11 =4$
$9^3 \mod 11 =3$
$9^4 \mod 11 =5$
$9^5 \mod 11 =11$

При небольших значениях модуля все легко решается в лоб. А вот когда модуль огромный, то хочется найти решение по-оптимальней. Собственно пока возникает 3 вопроса:
1. Есть ли какой алгоритм для нахождения индекса элемента?
$9^x \mod n = m$
Если брать пример выше, то, например, найти x при $m=5$, модуль равен 11. Ответ: $x=4$

Гугл и википедия вторит, что "эффективные алгоритмы для решения задачи дискретного логарифмирования в общем случае неизвестны "
Ладно, если надо, то можем и поперебирать. Отсюда вытекает второй вопрос:
2. А можем ли мы определить, а есть ли вообще решения, чтобы за зря не заниматься перебором?
Опять, если брать тот же пример, то при m=7 решений нет.

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

3. Как определить порядок данной группы взависимости от модуля?
При $ n=11$ всего 5 элементов (9, 4, 3, 5, 1)
при $ n=29$ порядок 14 (9, 23, 4, 7, 5, 16, 28, 20, 6, 25, 22, 24, 13, 1)
А вот при $ n=41$ имеем (9, 40, 32, 1)
А если модуль будет несколько миллионов, то как высчитать?

Спасибо!

[iifat]

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

NchK в сообщении #1295778 писал(а):

Как определить порядок данной группы

Малая теорема Ферма: $a^{\varphi(n)}\equiv1\pmod n$ для взаимно простых $a$ и $n$, так, кажется. Стало быть, порядок $a$ будет делителем $\varphi(n)$. Это не освобождает, естественно, от головной боли с разложением $\varphi(n)$ на множители...

[VAL]

NchK в сообщении #1295778 писал(а):

$9^5 \mod 11 =11$

Конечно же, Вы имели в виду $9^5 \mod 11 =1$

И еще пара моментов.

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

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

[NchK]

Благодарю за ответы

iifat в сообщении #1295784 писал(а):

Это не освобождает, естественно, от головной боли с разложением $\varphi(n)$ на множители...

Головная боль еще та

-- 08.03.2018, 01:40 --

VAL,

Цитата:

Конечно же, Вы имели в виду $9^5 \mod 11 =1$

Именно так. Поторопился, опечатался

Цитата:

Во всех примерах у Вас модули простые. Возможно, Вас интересует именно этот случай

Модули простые.

Что ж буду углубляться в теорию