Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ДОКАЗАТЕЛЬСТВО
- Эффективные алгоритмы
- Проверка, что элемент является генератором
- АЛГОРИТМ B.18
| PROPOSITION B.17 Пусть G будет группой порядка q, а q =
раз- ложением на простые множители q, где {pi} – различные целые числа и ei ≥ 1. Зададим qi = q/pi. Тогда h ∈ G является генератором G , если и только если hqi ƒ= 1 for i = 1, . . . , k. ДОКАЗАТЕЛЬСТВО Одно из направлений простое. Допустим, что hqi = 1 для некоторого i. Тогда порядок h не более qi < q, и, таким образом, h не может быть генератором. С другой стороны, пусть h не является генератором, но вместо этого имеет порядок qr < q. Согласно предположению 8.54, мы знаем, что qr q. Это подраз- умевает, что qr можно записать как qr = , где ei' ≥ 0 и, минимум, для одно- го индекса j мы имеем ei' < ej . Но тогда qr делит , и, таким образом, (используя предположение 8.53) hqj =jh[qj mod q ] = h0 = 1. Это предположение не требует, чтобы G была циклической; если G не явля- ется циклической, то каждый элемент h ∈ G будет удовлетворять hqi = 1 для некоторого i и генераторы не существуют. Эффективные алгоритмы Имея результаты предыдущего раздела, покажем, как эффективно проверить, является ли данный элемент генератором, а также, как эффективно найти гене- ратор в произвольной группе. Проверка, что элемент является генератором. Предположение B.17, пря- мо предлагает эффективный алгоритм для решения вопроса, является ли дан- ный элемент h генератором или нет. АЛГОРИТМ B.18 Проверка, что элемент является Вход: Групповой порядок q; {pi}i=1k q; элемент h ∈G Выход: Решение от- носительно того, является ли h генератором G for i = 1 to k: if hq/pi = 1 return "h не является генератором" return "h является генератором" Корректность алгоритма очевидна из предположения B.17. Теперь покажем, что алгоритм завершает работу в течение полиномиального времени в «q». По- скольку в каждой итерации hq/pi можно вычислить в течение полиномиального времени, нам нужно только показать, что количество итераций k является поли- номом. Это как раз тот случай, поскольку целое число q может иметь не более, чем log2q = O(||q||) простых множителей; это потому, что и, таким образом, k ≤ log2q. 334 Алгоритм B.18 требует, чтобы простые множители порядка группы q были предоставлены в виде входных данных. Интересно заметить, что не известен эффективный алгоритм для проверки, является ли элемент произвольной груп- пы генератором, когда коэффициенты группового порядка не известны. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|