Введение в современную криптографию



Pdf көрінісі
бет235/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   231   232   233   234   235   236   237   238   ...   249
Криптография Катц

ТЕОРЕМА 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.


Достарыңызбен бөлісу:
1   ...   231   232   233   234   235   236   237   238   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет