331
и поэтому мы может отобрать однородный элемент ZN в течение времени
poly(n) и с пренебрежимо малой вероятностью ошибки в n.
Случай ZN* . Рассмотрим следующую группу ZN* , при n = ||N|| , как и ра-
нее. Определить, является ли n-битная строка x элементом ZN* так же просто
(см.пражнения).
Более того,
Верхняя граница poly(n) является следствие приведенной ниже теоремы.
ТЕОРЕМА B.15 Для N ≥ 3 длиной n, имеем N/φ(N )< 2n.
(Известны более строгие ограничения, но для нашей цели достаточно указанных
выше). Теорему можно доказать с помощью постулата Бертрана (теорема 8.32), но мы
ограничимся доказательством двух особых случаев: когда N является простым числом
и когда N является произведением двух (различных) простых чисел одинаковой длины.
Анализ прост, когда N – четное число. Здесь φ(N ) = N − 1, и
таким образом
(используя тот факт, что N является нечетным для второго неравенства ). Рассмотри
следующий случай N = pq для p и q различных, нечетных простых чисел. Тогда
Мы пришли к выводу, что когда N является простым или произведением двух
различных нечетных простых чисел, существует алгоритм для генерации одно-
родного элемента ZN*, который действует в течение времени полинома в n =
||N|| и выводит fail (ошибка) с вероятностью пренебрежимо малой в n.
На протяжении этой книги, когда мы говорим об отборе однородного элемен-
та из ZN или ZN* мы попросту игнорируем пренебрежимо малую вероятность
вывода fail (ошибка), понимая, что это не оказывает существенного влияния на
анализ.
Достарыңызбен бөлісу: