Первообразная корня числа

[Mikle1990]

Есть простое число $q=71$.
Как узнать первообразную корня этого числа?

Теорию я нашёл. Но нигде нет конкретного примера . А мне всегда пример нужен. Не мог ли бы показать, как вы находите $a$ - первообразную корня числа $q$?

(Оффтоп)

Мне это нужно для обмена ключами по схеме Диффи-Хеллмана.

-- Чт окт 18, 2012 14:31:53 --

Еле еле нашёл пример. Но кое-что в нём не понимаю.

Пример. Пусть $n=41$. Имеем $C=\varphi({41})=40=2^{3}\cdot5$

Итак, первообразный корень не должен удовлетворять двум сравнениям:
$a^{8}\equiv1\pmod{41}$ , $a^{20}\equiv1\pmod{41}$.

Дальше многим будет ясно, как найти $a$. Но давайте остановимся вот на чём:
1. Зачем число $40$ представлено как $2^{3}\cdot5$?
2. Откуда мы взяли показатели степени $a$: $8$ и $20$ ?

[bot]

Для простого $p$ мультипликтивная группа кольца $\mathbb Z/p\mathbb Z$ циклическая и её порядок равен $\varphi (p)$. Первообразный - это образующий группы, то есть должен порождать всю циклическую группу.

[RIP]

Mikle1990 в сообщении #632410 писал(а):

1. Зачем число $40$ представлено как $2^{3}\cdot5$?
2. Откуда мы взяли показатели степени $a$: $8$ и $20$ ?

Есть такой простой критерий. Пусть $m\in\mathbb N$, $a\in\mathbb Z$, $(a,m)=1$. Тогда $a$ является первообразным корнем по модулю $m$ тогда и только тогда, когда для любого простого $q|\varphi(m)$ выполнено:

$$a^{\frac{\varphi(m)}q}\not\equiv1\pmod m.$$

[Mikle1990]

bot, слишком сложно для меня.
Для начала пускай кто-нибудь ответит на мои 2 вопроса. Хоть будет от чего оттолкнуться.

RIP, можно совсем простым языком?
Откуда мы взяли показатели степени $a$: $8$ и $20$ ? Т.е. как вычислены эти два значения $8$ и $20$?

[bot]

$8=\dfrac{40}5, \, 20=\dfrac{40}2$

[Sonic86]

Mikle1990 в сообщении #632442 писал(а):

Откуда мы взяли показатели степени $a$: $8$ и $20$ ? Т.е. как вычислены эти два значения $8$ и $20$?

Мы берем $40=\varphi(41)$ раскладываем на простые множители: получаем делители $2$ и $5$. Считаем $\frac{40}{2}=20, \frac{40}{5}=8$.

Mikle1990 в сообщении #632410 писал(а):

Дальше многим будет ясно, как найти $a$.

И как же?

[Mikle1990]

bot, спасибо большое.

Sonic86, спасибо.
Как найти? Перебором

[Sonic86]

Mikle1990 в сообщении #632454 писал(а):

Как найти? Перебором

Оптимистично
На самом деле да, перебором довольно быстро находится. Всего образующих $=\varphi(\varphi(p))$, т.е. довольно много...