Найти образующие группы

[wooddii]

Добрый вечер! Пусть $p=2^s - 1$ - это простое число, $q = p^2$, $i: i^2 = -1 $.
а) ] $ a^2+b^2 - $ образующая группы $F^*_p$, требуется доказать, что в таком случае $a+bi - $ образующая группы $F^*_q$;
б) показать, что $4+i$ и $3+2i$ являются образующими группы $F^*_{31^2}$.

Порядок группы $F^*_p$, очевидно, равен $p-1=2^s$. Порядок $F^*_q$ равен $q-1 = p^2 - 1$. Группы циклические. Так как $a^2+b^2$ - образующая $F^*_p$, то порядок $(a^2+b^2)$ также равен $p-1=2^s$. Отсюда следует, что $(a^2+b^2)^{(p-1)} = e$, где e - единичный элемент группы $F^*_p$. Основываясь на этом факте, нужно доказать, что $(a+bi)^{(q-1)} = e$, где e - единичный элемент группы $F^*_q$. При этом q-1 должно быть минимальным таким натуральным числом $k$, что $(a+bi)^k = e$. Как сделать этот переход? Лишь используя арифметические преобразования?

[vpb]

wooddii в сообщении #1313311 писал(а):

Лишь используя арифметические преобразования

Отнюдь. Что Вы знаете об автоморфизмах конечных полей? Как выглядят автоморфизмы $F_q$ над $F_p$ ?

[wooddii]

К сожалению, не проходили еще такого, поэтому, наверное, и возникла трудность в решении задачи...

Группа автоморфизмов $F_q$ над $F_p$ совпадает с группой, порождённой $\varphi$. $\varphi$ - это отображение $F_q$ в себя, $\varphi(x)=x^p$.
Есть соответствующая теорема, которая доказывает, что группа, порождённая $\varphi$ является циклической группой порядка n.

Верно?

[Null]

$p=2^s - 1$
$p-1=2^s$
Необычно.

[wooddii]

Null в сообщении #1313414 писал(а):

$p=2^s - 1$
$p-1=2^s$
Необычно.

Опечатка, конечно же)

[vpb]

wooddii в сообщении #1313311 писал(а):

$p-1=2^s$.

Это, очевидно, опечатка. wooddii, да, описание группы автоморфизмов правильное. Теперь такой вопрос. Каков порядок группы автоморфизмов в нашем случае? Нельзя ли описать нетривиальный автоморфизм по другому? Затем покажите, что всегда $(a+bi)^{p+1}=a^2+b^2$.

Впрочем, коль автоморфизмы не проходили, можно и непосредственно рассуждать попробовать... Покажите, что всегда $(a+bi)^p=a-bi$.

[wooddii]

vpb в сообщении #1313424 писал(а):

wooddii в сообщении #1313311 писал(а):

$p-1=2^s$.

Это, очевидно, опечатка. wooddii, да, описание группы автоморфизмов правильное. Теперь такой вопрос. Каков порядок группы автоморфизмов в нашем случае? Нельзя ли описать нетривиальный автоморфизм по другому? Затем покажите, что всегда $(a+bi)^{p+1}=a^2+b^2$.

Впрочем, коль автоморфизмы не проходили, можно и непосредственно рассуждать попробовать... Покажите, что всегда $(a+bi)^p=a-bi$.

В нашем случае порядок группы автоморфизмов равен двум, так как $q=p^2$.
Вот $(a^2+b^2)^p = (a^2+b^2)$. Так как группа циклическая, верно, что $(a-b\cdot i)^p = (a-b\cdot i)$ или нет?

[vpb]

wooddii в сообщении #1313641 писал(а):

В нашем случае порядок группы автоморфизмов равен двум, так как $q=p^2$

Верно.

wooddii в сообщении #1313641 писал(а):

Вот $(a^2+b^2)^p = (a^2+b^2)$. Так как группа циклическая, верно, что $(a-b\cdot i)^p = (a-b\cdot i)$ или нет?

Это вообще Вы написали что-то странное. Кажется, Вы чего-то сильно не понимаете. Можете доказать, что отображение $\varphi(x)=x^p$ --- действительно автоморфизм поля ?

[wooddii]

vpb в сообщении #1313656 писал(а):

wooddii в сообщении #1313641 писал(а):

В нашем случае порядок группы автоморфизмов равен двум, так как $q=p^2$

Верно.

wooddii в сообщении #1313641 писал(а):

Вот $(a^2+b^2)^p = (a^2+b^2)$. Так как группа циклическая, верно, что $(a-b\cdot i)^p = (a-b\cdot i)$ или нет?

Это вообще Вы написали что-то странное. Кажется, Вы чего-то сильно не понимаете. Можете доказать, что отображение $\varphi(x)=x^p$ --- действительно автоморфизм поля ?

Отображение удовлетворяет свойствам гомоморфизма. Так как $F_q$ поле, то ядро равно нулю. Отображение, таким образом инъективно. Так как поле конечно, то отображение еще и сюръективно. Получили, что такое отображение - изоморфизм. Изоморфизм, отображающий алгебраическую систему на себя - автоморфизм.

[vpb]

wooddii в сообщении #1313661 писал(а):

Отображение удовлетворяет свойствам гомоморфизма

Поясните, почему.

[wooddii]

vpb в сообщении #1313678 писал(а):

wooddii в сообщении #1313661 писал(а):

Отображение удовлетворяет свойствам гомоморфизма

Поясните, почему.

По умножению: $(ab)^p = a^p \cdot b^p$
По сложению: $(a+b)^p = a^p + b^p$, так как в разложении (a+b)^p все коэффициенты, кроме единиц делятся на p.

[vpb]

Хорошо. Теперь такой вопрос: почему в нашем случае $F_p$ не содержит квадратного корня из $-1$ ? Вообще, когда (для каких $p$) содержит, а для каких нет? Чему равно $i^p$ ?

-- 20.05.2018, 16:07 --

И во вторую свою тему посмотрите, там небольшой ляпсус.

[wooddii]

vpb в сообщении #1313682 писал(а):

Хорошо. Теперь такой вопрос: почему в нашем случае $F_p$ не содержит квадратного корня из $-1$ ? Вообще, когда (для каких $p$) содержит, а для каких нет? Чему равно $i^p$ ?

Так как многочлен $x^2+1$ неприводим в $F_p$.
Ох, тяжко отвечать, коль не проходили мы этого всего)

-- 20.05.2018, 18:34 --

$i^p = i$?

[vpb]

wooddii в сообщении #1313696 писал(а):

$i^p = i$?

Отнюдь. А если бы и так было, Вы, очевидно, все равно не понимаете почему.

wooddii в сообщении #1313696 писал(а):

Так как многочлен $x^2+1$ неприводим в $F_p$.
Ох, тяжко отвечать, коль не проходили мы этого всего)

А почему он неприводим ? Это же и значит, собственно, что корня из $-1$ нет.
И вообще... как же я буду Вам помогать, если, как выясняется, вы базового материала не проходили, и того, и этого, и третьего ?
Несколько дней назад я отвечал тоже на вопрос по конечным полям, там есть список литературы. Поищите. Почитайте. А то, я вижу, у Вас в голове какие-то обрывочные сведения.

Ну, допустим, данную задачу я Вам могу объяснить, кое-как. Но вообще необходимость улучшения знаний имейте в виду.

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

Знаете ли Вы, как устроена мультипликативная группа $F^\ast_p$ ?

[wooddii]

vpb в сообщении #1313703 писал(а):

wooddii в сообщении #1313696 писал(а):

$i^p = i$?

Отнюдь. А если бы и так было, Вы, очевидно, все равно не понимаете почему.

wooddii в сообщении #1313696 писал(а):

Так как многочлен $x^2+1$ неприводим в $F_p$.
Ох, тяжко отвечать, коль не проходили мы этого всего)

А почему он неприводим ? Это же и значит, собственно, что корня из $-1$ нет.
И вообще... как же я буду Вам помогать, если, как выясняется, вы базового материала не проходили, и того, и этого, и третьего ?
Несколько дней назад я отвечал тоже на вопрос по конечным полям, там есть список литературы. Поищите. Почитайте. А то, я вижу, у Вас в голове какие-то обрывочные сведения.

Ну, допустим, данную задачу я Вам могу объяснить, кое-как. Но вообще необходимость улучшения знаний имейте в виду.

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

Знаете ли Вы, как устроена мультипликативная группа $F^\ast_p$ ?

$F^*_p=F_p\setminus \left\lbrace 0 \right\rbrace$

-- 20.05.2018, 19:23 --

Литературу нашел, ознакомлюсь.
Нет, учат хорошо, просто пропало несколько лекций и практика идет впереди)