Введение в современную криптографию
Использование предварительных вычислений
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Возведение в степень произвольных групп
| Использование предварительных вычислений. Если основание a известно зара-
нее, и существует ограничение на длину показателя степени b, то можно использовать предварительные вычисление и небольшой объем памяти, чтобы ускорить вычисление [ab mod N ]. Пусть «b» ≤ n. Тогда предварительно вычислим и сохраним n значений x0 := a, x1 := [a2 mod N ], . . . , xn−1:= [a2n-1mod N ]. Принимая во внимание показатель степени b с двоичным представлением bn−1 • • • b0 (записанным от наиболее значимого до наименее значимого бита), имеем . Поскольку bi ∈{0, 1}, количество умножений, необходимое для вычисления, результат ровно на единицу меньше, чем вес Хэмминга b. Возведение в степень произвольных групп Эффективный алгоритм модульного возведения в степень, приведенный выше, переносится в простой способ, чтобы обеспечить эффективное возведе- ние в степень в любой группе, до тех пор, пока операция основной группы может быть выполнена эффективно. В частности, если G является группой, а g – элементом G, то gb можно вычислить, используя не более 2 • «b» применений операции основной группы. Предварительное вычисление может быть исполь- зовано в точности так же, как описано выше. Если порядок q из G известен, то ab = a[b mod q] (см. предположение 8.52) и это мож- но использовать для ускорения вычисления при редукции b по модулю q, прежде всего. С учетом (аддитивной) группы ZN , только что описанный алгоритм возведе- ния в степень группы дает метод вычисления «возведения в степень» который отличается от метода, обсуждавшегося ранее, опирающегося на стандарт- ное целочисленное умножение с последующей модульной редукцией. При сравне- нии двух подходов к решению одной и той же проблемы, обратите внимание, что исходный алгоритм использует специфическую информацю о ZN ; в частности он (по существу) рассматривает «показатель степени» b в качестве элемента ZN (воз- можно, при редукции b по модулю N прежде всего). В противоположность «возве- дению в квадрат и умножению» только что представленный алгоритм, рассматри- вает ZN только как абстрактную группу. (Конечно, групповая операция сложения по модулю N зависит от специфики ZN ). Суть этого обсуждения заключается лишь в том, чтобы показать, что некоторые групповые алгоритмы являются универ- сальными (т.е., они одинаково хорошо применимы ко всем группам), тогда как не- которые групповые алгоритмы основаны на специфических свойствах отдельных 328 групп или классов групп. Мы видели некоторые примеры этого явления в главе 9. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|