*Нахождение генератора циклической группы

332
тором. Как и в разделе B.2.5, анализ этого метода требует понимания двух вещей:
• Как эффективно проверить, является ли данный элемент генератором, а также
• проверить часть элементов группы, которые являются генераторами.
Чтобы понять эти вопросы, сначала разработаем небольшое дополнительное 
теоретически-групповое основание.
Теоретико-групповое основание
Сначала займемся вторым вопросом. Напомним, что порядок элемента h – это 
наименьшее целое число i, для которого hi=1. Пусть g будет генератором груп-
пы G порядка q > 1; это означает, что порядок g равен q. Рассмотрим элемент 
h ∈G, который не является единичным (единичный элемент не может быть ге-
нератором G), и проверим h, может ли также быть генератором G. Поскольку 
g генерирует G, можно записать h = gx для некоторого x ∈ {1, . . . , q − 1} (об-
ратите внимание, что x ƒ= 0, поскольку h не является единичным элементом). 
Рассмотрим два случая:
Случай 1: gcd(x, q) = r > 1. Запишем x = α • r и q = β • r при этом α, β – ненуле-
вые целые числа меньше q. Тогда:
hβ = (gx)β = gαrβ = (gq )α = 1.
Таким образом, порядок h не более β < q и h не может быть генератором G.
Случай 2: gcd(x, q) = 1. Пусть i ≤ q будет порядком h. Тогда
g0 = 1 = hi = (gx)i = gxi,
подразумевая, что xi = 0 mod q согласно предположению 8.53. Это означает, что 
q | xi. Поскольку gcd(x, q) = 1, тем не менее, предположение 8.3 показывает, что 
q | i, и, таким образом, i = q. Мы пришли к выводу, что h является генератором G.
Резюмируя сказанное выше, видим, что для x∈ {1, . . . , q − 1 }элемент h = gx 
точно является генератором G. когда gcd(x, q) = 1. Итак, мы доказали следующее:
ТЕОРЕМА B.16 Пусть G – циклическая группа порядка q > 1 с генератором 
g. Существует φ(q) генераторов G и они точно задаются {gx| x∈Zg*}.
В частности, если G является группой порядка простого числа q, то она имеет 
φ(q) = q − 1 генераторов—точно в соответствии со следствием 8.55.
Теперь мы вернемся к первому вопросу – вопросу принятия решения, являет-
ся ли данный элемент h генератором G. Конечно, один способ проверить, гене-
рирует ли h G – это перечислить {h0, h1, . . . , hq−1} и посмотреть, включает 
ли этот список каждый элемент G. Это требует линейного времени в q (т.е., 
экспоненциального в ||q||) и поэтому неприемлемо для наших целей. Другой 
подход, если мы уже знаем генератор g, заключается в том, чтобы вычислить 
дискретный логарифм x = loggh и затем применить предыдущую теорему; од-
нако в общем случае, мы можем не иметь такого g, и, в любом, случае само вы-
числение дискретного логарифма может быть сложной задачей.
Если нам известна факторизация (простые множители) q, то мы можем по-
ступить лучше.

333

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: