Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 9.2.5 Альтернативный подход Вверх: 9.2 Алгоритмические проблемы реализации и применения криптографических протоколов на интеллектуальных карточках Назад: 9.2.3 Методы ускорения операции сложения   Содержание   Предметный указатель

9.2.4 Ускоренное вычисление

Вряд ли можно найти метод ускоренного возведения в степень эффективнее, чем бинарный метод, основанный на считывании степени слева направо. В силу ряда причин [Кнут, стр. 485] использование в этом методе любого другого основания не дает особого выигрыша при большом значении показателя степени.

Этот метод достаточно прост и нагляден, история его восходит еще к 200 г. до н. э. Пусть $ e[1,\ldots,n]$ двоичное представление положительного числа $ e$ и $ A$, $ B$ и $ N$ -- положительные целые числа в $ r$-ичной системе счисления, тогда псевдокод алгоритма $ A^e\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$ имеет вид, представленный на рис. 10.

Рис. 10. Алгоритм $ A^e\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$. Бинарный метод, основанный на считывании степени слева направо
\begin{figure}\par\centerline{\it Алгоритм 6}\par\bigskip\centerline{\vbox{\tt ... ...}write($B$); \symbol{''7B}\textrm{$B$~--- результат}\symbol{''7D}}}}\end{figure}

Из описания алгоритма 6 видно, что число обращений к операции вида $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$ будет $ \log e+\beta(e)$, где $ \beta(e)$ -- число единиц в двоичном представлении операнда $ e$.

Для ускорения операции дискретного возведения в степень используется также метод, основанный на аддитивных цепочках (см., например, [Кнут], [Y]).

Бинарный метод может быть усовершенствован за счет перекодирования степени $ e$. При многократном использовании операции возведения в степень такой алгоритм дает выигрыш не менее 30% по сравнению с бинарным методом [CMY]. Сущность этого усовершенствования проиллюстрирована на рис. 11 и заключается в представлении $ e$ в избыточной форме, где $ е[i]\in\left\{1,0,\overline1\right\}$. Эффект достигается за счет уменьшения количества "не-нулей" (т. е. $ 1$, $ \overline1$) в избыточном представлении $ e$ по сравнению с его двоичным представлением.

Рис. 11. Алгоритм $ A^e\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$. Метод, основанный на перекодировании $ e$
\begin{figure}\par\centerline{\it Алгоритм 7}\par\bigskip\centerline{\vbox{\tt ... ...}write($B$); \symbol{''7B}\textrm{$B$~--- результат}\symbol{''7D}}}}\end{figure}

Значение $ A^{-1}\mskip-\medmuskip\mkern5mu \mathbin{\rm modulo}\penalty900 \mkern5mu\mskip-\medmuskip N$ можно предварительно вычислить при помощи расширенного алгоритма Евклида: вычисляются целые $ R$ и $ S$ такие, что $ RA+SN=1$, где НОД$ (A,N)=1$. Пусть $ n_1$ -- число единиц до кодирования, $ n_2$ -- число "не-нулей" после кодирования, тогда если $ е$ достаточно велико и необходимо вычислить последовательность $ A_i^e\mskip-\medmuskip\mkern5mu \mathbin{\rm modulo}\penalty900 \mkern5mu\mskip-\medmuskip N$, где $ i=1,2,\ldots,\gamma$, то общий выигрыш в среднем может составить $ \gamma*(n_1-n_2)$.

Целесообразно рассматривать операции $ A^e\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$ и $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$ не по отдельности, а в комплексе. Так как обращение первой функции ко второй происходит неоднократно, а значения $ A$ и $ N$ при этом не меняются, то имеет смысл для сокращения общего времени передавать $ A$ и $ N$ в процедуру вычисления $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$ только при первоначальном обращении. Операция $ B*B\mskip-\medmuskip\mkern5mu \mathbin{\rm modulo}\penalty900 \mkern5mu\mskip-\medmuskip N$ рассматривается как частный случай $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$, что предусматривает передачу в соответствующую процедуру только одной переменной (если $ N$ при первоначальной инициализации уже передано). Можно рассматривать $ B*B\mskip-\medmuskip\mkern5mu \mathbin{\rm modulo}\penalty900 \mkern5mu\mskip-\medmuskip N$ как $ B^2\mskip-\medmuskip\mkern5mu \mathbin{\rm modulo}\penalty900 \mkern5mu\mskip-\medmuskip N$ и уменьшить таким образом время выполнения за счет методов ускорения операции возведения в квадрат, предложенных, например, в [Ш]. Однако в этом случае требуется дополнительная аппаратура.

При окончательной реализации алгоритма следует предусмотреть в выходных данных флаг ошибки, например:

    0 -- деление на ноль;

    1 -- $ A$ и $ B$ по величине больше $ N$;

    2 -- некорректное представление чисел в $ r$-ичной системе счисления;

    3 -- переполнение установленной длины переменных $ A$, $ B$, $ N$, $ P$ и $ S$

и т. д.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 9.2.5 Альтернативный подход Вверх: 9.2 Алгоритмические проблемы реализации и применения криптографических протоколов на интеллектуальных карточках Назад: 9.2.3 Методы ускорения операции сложения   Содержание   Предметный указатель

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100