конечные поля

[Naatikin]

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

Также известно число образующих.

спасибо

[VladimirKr]

Сугубо имхо.
В 90-е годы прошлого века эта задача, кажется, была эквивалентна задаче логарифмирования в конечных полях и полиномиального от степени расширения по сложности не имела. Но вроде как продвинулись в начале века. Посмотрите на атаки алгоритма открытого ключа Диффи-Хэлмена или Эль-Гамаля. Там были какие-то мощные продвижения.

[AV_77]

VladimirKr в сообщении #725158 писал(а):

В 90-е годы прошлого века эта задача, кажется, была эквивалентна задаче логарифмирования в конечных полях и полиномиального от степени расширения по сложности не имела.

К исходному вопросу это никакого отношения не имеет.

VladimirKr в сообщении #725158 писал(а):

Но вроде как продвинулись в начале века.

Продвинулись, но не слишком далеко. Ничего "мощного" там нет.

Naatikin в сообщении #725073 писал(а):

Как кроме перебора можно найти образующую? или как доказать, что конкретный элемент образующий?

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

[Naatikin]

AV_77 в сообщении #725183 писал(а):

Это не сложно, если известно разложение порядка группы в произведение простых чисел.

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

-- 18.05.2013, 22:59 --

и ещё если у меня 30 элементов, тогда я должен из образующей все 29 получить или есть другой способ доказательства?

[VAL]

Naatikin в сообщении #725548 писал(а):

AV_77 в сообщении #725183 писал(а):

Это не сложно, если известно разложение порядка группы в произведение простых чисел.

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

-- 18.05.2013, 22:59 --

и ещё если у меня 30 элементов, тогда я должен из образующей все 29 получить или есть другой способ доказательства?

Отвечу на последний вопрос. Надеюсь, это поможет Вам самому ответить на первый.

Если порядок мультипликативной группы конечного поля равен 30, то элемент, будет образующим этой группы тогда и только тогда, он не даст единицу ни 6-й, ни в 10-й, ни в 15-й степенях.

[Naatikin]

VAL, если я правильно понял, то логика следующая:
пусть $a$ элемент группы,n- порядок группы, тогда $a^n=e$. Для образующей только $a^n=e$, т.е. порядок элемента должен быть n.

Исходя из того, что порядок элемента должен быть простым числом из разложения порядка группы, надо исключать возможность получить единицу в степени 2,3,5. Или я ошибся?

[AV_77]

Если $n$ - порядок и $n = p_1^{k_1} p_2^{k_2} \ldots p_s^{k_s}$, то элемент $a$ образующий, если все элементы $a^{\frac{n}{p_1}}$, $a^{\frac{n}{p_2}}$, $\ldots$, $a^{\frac{n}{p_s}}$ отличны от единицы.

[Naatikin]

спасибо, именно это и хотел увидеть.