321
писанная мультипликативно. Пусть g будет элементом этой группы и b неот-
рицательным целым числом. Тогда gb можно вычислить, используя poly(«b»)
групповые операции.
ТЕОРЕМА B.4 (Выбор равномерных элементов)
Существует веро-
ятностный алгоритм со следующими свойствами: на входе N ,
• Алгоритм работает в течение полиномиального времени в «N «;
• Алгоритм выводит fail (ошибка) с вероятностью пренебрежимо малой в
«N «; а также
• Настроенный так, чтобы не выводить fail (ошибка), алгоритм выводит
равномерно распределенный элемент ZN .
Алгоритм с аналоговыми свойствами для ZN* также существует.
Поскольку вероятность того, что любой алгоритм, упоминаемый в приведен-
ной выше теореме, выводит fail (ошибка), пренебрежимо мала, мы игнорируем
эту возможность (и вместо этого оставляем в неявном виде). В приложении B.2
также обсуждаются обобщения изложенного выше,
для случая выбора равно-
мерного элемента из какой-либо конечной группы (с учетом определенных тре-
бований к представлению элементов группы).
Доказательство нижеследующего приведено в приложении B.3:
ТЕОРЕМА B.5 (Тестирование и нахождение генераторов) Пусть G будет
циклической группой порядка q, предположим, что групповая операция и выбор
однородных элементов группы могут быть выполнены в единицу времени.
1. Существует алгоритм, который на входе q выполняет разложение на про-
стые множители q, и элемент g∈
G, действует в течение времени poly(«q») и
решает, является ли g генератором G.
2. Существует вероятностный алгоритм, который на входе q и разложении
на простые множители q, действует в течение времени poly(«q») и выводит
генератор G, кроме как с пренебрежимо малой вероятностью в «q». Настро-
енный на выходе генератор, равномерно распределен среди генераторов G.
Достарыңызбен бөлісу: