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


9.2.1 Представление чисел

Пусть $ A,N,e$ -- три целых положительных числа многократной точности, причем $ A<N$. Тогда для любого $ e$ при вычислении $ A^e\bmod N=C$, результат редукции $ C\in\{1,\ldots,N-1\}$. Если представить $ e$ $ 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$, где $ 0<B<N-1$ [Кнут, стр. 482-510]. Таким образом, во всех дальнейших рассуждениях $ e$ будет представляться только как двоичная строка. Кроме того, числа $ A,B,N$, а также $ P$ -- частичное произведение и $ S$ -- текущий результат будут представляться $ n$-битовыми двоичными векторами, например, $ N[1,\ldots,n]$, где $ N[1]$ и $ N[n]$ -- младший и старший биты $ N$ соответственно.

Так как в интеллектуальных карточках, как правило, из-за ограниченных размеров рабочего пространства используется вычислительная система с фиксированной длиной слова, то $ A,B,N,P$ и $ S$ будут также рассматриваться как векторы $ \widehat A[1,\ldots,m]$, $ \widehat
B[1,\ldots,m]$, $ \widehat N[1,\ldots,m]$, $ \widehat
P[1,\ldots,m']$ и $ \widehat S[1,\ldots,m']$, где каждый элемент вектора (элемент одномерного массива) есть цифра $ r$-ичной системы счисления, $ m'=m+h$, величина $ h$ будет изменяться в зависимости от вида алгоритма. Основание $ r$ такой системы будет ограничено длиной машинного слова $ \lambda$, т. е. $ 2\leqslant r\leqslant2^\lambda$ и цифры такой системы имеют вид $ 0,1,\ldots,r-1$. При этом $ n$ и $ m$ связаны соотношением $ n=s*m$, где $ s=\lfloor
\log_2r\rfloor$ (в дальнейших рассуждениях $ \log\alpha$ -- логарифм по основанию 2). Наиболее целесообразно выбрать основание $ r=2^\lambda$ как наиболее экономное представление чисел в машине, ибо при $ r<2^\lambda$ на представление чисел уходит больше памяти. Например, широко принятое на практике представление десятичных чисел в двоично-десятичном коде требует на 20% большего объема памяти, чем двоичное представление тех же чисел [Ш]. Тем не менее, иногда полезно представлять ситуацию, когда $ r=10$ [Кнут, стр. 283] или $ r=10^k$, например, при отладке программ.

Следует также обратить внимание на тот факт, что при выполнении арифметических операций над числами многократной точности, например, по классическим алгоритмам Кнута [Кнут, стр. 282-302], основание $ r$ следует уменьшать, чтобы не возникло переполнение разрядной сетки. Так, для операции сложения уменьшение выполняется до $ r=2^{\lambda-1}$, для умножения -- до $ r=2^{\lambda/2}$. Однако если архитектурой вычислительной системы предусмотрен флаг переноса или хранение промежуточного результата с двойной точностью, то можно возвращаться к основанию $ r=2^\lambda$.

Далее будет показано, что для ускоренного суммирования могут использоваться избыточные системы счисления. В [Pa], например, предложена обобщенная знаковая система для представления широкого класса избыточных числовых систем. Однако сегодня находят применение лишь немногие из них. Так, в [Bak] для выполнения сложения в случае явного представления сохраняемого переноса (CARRY-SAVE ADDITIONS -- CSAs) в алгоритме $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$ используется система с основанием $ r=2$, которая определена на множестве $ \{0,1,2\}$. В [Ta] предложен высокоскоростной алгоритм умножения $ n$-разрядных чисел со скоростью пропорциональной $ O(\log n)$, где используется система, определенная на множестве $ \left\{1,0,\overline1\right\}$. Такая же система для кодирования $ e$ используется в ускоренном алгоритме $ A^e\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$ в [CMY]. Для представления чисел в таких системах требуется в два раза больше вентилей, чем для представления чисел в обычном двоичном виде.


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 9.2.2 Ускоренное вычисление A*B modulo N Вверх: 9.2 Алгоритмические проблемы реализации и применения криптографических протоколов на интеллектуальных карточках Назад: 9.2 Алгоритмические проблемы реализации и применения криптографических протоколов на интеллектуальных карточках   Содержание   Предметный указатель


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