Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ТЕОРЕМА B.2 (Модульные операции)
- ТЕОРЕМА B.3 (Групповое возведение в степень)
- ТЕОРЕМА B.4 (Выбор равномерных элементов)
| ТЕОРЕМА B.1 (Операции с целыми числами) Даны целые числа a и b, можно
выполнить следующие операции в течение полиномиального времени «a» и «b»: 1. Вычисление суммы a + b и разности a − b; 2. Вычисление произведения ab; 3. Вычисление положительных целых чисел q и r < b, так что a = qb + r (т.е., вычисление деления с остатком); 4. Вычисление наибольшего целого делителя a и b, gcd(a, b); 5. Вычисление целых чисел X, Y при Xa + Y b = gcd(a, b). Следующие результаты доказаны в приложении B.2: ТЕОРЕМА B.2 (Модульные операции) Даны целые числа N > 1, a и b, можно выполнить следующие операции в течение полиномиального времени в «a», «b», and «N «: 1. Вычисление модульной редукции [a mod N ]; 2. Вычисление суммы [(a + b) mod N ], разности [(a − b) mod N ], и произ- ведения [ab mod N ]; 3. Определение, является ли a обратимой по модулю N ; 4. Вычисление мультипликативной инверсии [a−1 mod N ], в предположении, что a обратимо по модулю N ; 5. Вычисление возведения в степень [ab mod N ]. Нижеследующее обобщает теорему B.2(5) для произвольных групп: ТЕОРЕМА B.3 (Групповое возведение в степень) Пусть G – группа, за- 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. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|