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



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

Целочисленная арифметика
Основные операции
Мы начнем наше объяснение алгоритмической теории чисел с обсуждения сло-
жения/вычитания, умножения и деления с остатком целых чисел. Небольшое раз-
мышление показывает, что все эти операции могут быть выполнены в течение по-
линомиального времени в длине входных данных, с использованием для этих задач 
стандартных алгоритмов «начальной школы». Например, сложение двух положи-
тельных целых чисел a и b, при a > b может быть выполнено в течение времени, 


322
линейного в «a» пошагово, поочередно, по битам a иd b, начиная битами нижнего 
порядка и вычисляя соответствующий выходной бит и «текущий бит» на каждом 
шаге. (Подробности опущены). Умножение двух n-битных целых чисел a и b, что-
бы использовать другой пример, можно сделать созданием списка n целых чисел 
длиной не более 2n (каждое из которых равно a • 2i−1 • bi, где bi – i-й бит b) и 
последующим сложением этих n целых чисел, чтобы получить конечный результат.
(Деление с остатком, сложнее для реализации, но также может быть выполнено).
Несмотря на то, что этих алгоритмов начальной школы достаточно, чтобы проде-
монстрировать, что вышеупомянутые проблемы могут быть решены в течение поли-
номиального времени, интересно отметить, что эти алгоритмы в некоторых случаях 
– не самые лучшие из доступных. В качестве примера, простой алгоритм для умноже-
ния, приведенный выше, перемножает два n-битных числа за время O(n2), но суще-
ствует более хороший алгоритм, действующий в течение времени O(nlog23) (и даже 
этот алгоритм, не является самым лучшим из возможных). В то время как, разница 
несущественна для такого размера чисел, с которыми мы сталкиваемся ежедневно, 
она становится заметной, когда числа большие. В криптографических приложениях 
нередко используются целые числа, длиной тысячи битов (т.е., n > 1000) и разумный 
выбор используемых алгоритмов, становится критическим.


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




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

    Басты бет