информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Где водятся OGRыСтрашный баг в WindowsВсе любят мед
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
 С наступающим 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Поправки 26.03.04 18:49  Число просмотров: 4075
Автор: Xelator Статус: Незарегистрированный пользователь
<"чистая" ссылка>
К сожалению нет у меня уже исходников - ну ооочень давно было дело.

Попробуем еще раз на словах.
1) простое деление столбиком, которое используете вы содержит
- сравнение старшего бита делимого с делителем.
в первый раз они всегда равны, затем после первого вычитания следующие страшие биты делимого могут быть нулями.
- сдвиг делителя, чтобы его старший бит стоял там же где и текущий старший бит делимого
- вычитания делителя из делимого

И так по кругу. Если у вас делитель 256-битный, а делимое 512-битное (после умножения двух 256-битных чисел например), то потратим 256 сравнений, и в худшем случае 256 сдвигов 256-битного делителя и 256 вычитаний делителя из делимого. Если предположить что у нас поровну нулей и единиц в делимом (это ведь криптография и должно быть равномерное распределение?), то в среднем 128 сдвигов и вычитаний делителя.

2) блочное деление, которое я описывал дляфиксированногоделителя. если делитель нефиксированный, то ко времени работы алгоритма надо добавить время построения таблицы.
в нашем случае в роли делителя должен выступать порождающий элемент, т.е. величина фиксированная.

предварительные действия - они же генерация таблицы:
- выбрать размер таблицы , он же ширина блока. Возьмем 8 бит, размер таблицы тогда 256 ячеек.
- получить все числа такие, что они при умножении на делитель генерируют результат, у которого старшие 8 бит принимают всевозможные значения. Таковых должно быть 256 в нашем случае.
Получив таковые числа, построить таблицу, в которой каждый элемент равен результату умножения делителя на одно из чисел. Отсортировать эту таблицу по значению старших 8 бит результата.

Слов много, а на самом деле делов на полкопейки - например, берете полином у которого старшие биты поочередно заполняете 256 возможными значениями и делите обычным алгоритмом. Получается то, что нужно само собой.

Теперь блочный алгоритм деления.
- прочитать старший 8-битный блок 512-битного делимого
- по его значению выбрать элемент из таблицы (помните, мы ее сортировали так, чтобы само значение могло быть одновременно и индексом)
- вычесть 256-битное табличное значение из делимого

Итого сложность в операциях = 256/8 = 32 блока => 32 раза прочитать 8-битный блок из делимого, по этому индексу 32 раза прочитать 256-битное табличное значение и 32 вычесть это табличное значение.

У первого алгоритма = 256 сравнений, 128 сдвигов и 128 вычитаний
У второго = 32 чтения из делимого, 32 чтения из таблицы, 32 вычитания.
Надо понимать, что чтения здесь не стоят ничего - это просто адреса для вычитания.
Итого в 8 раз меньше вычитаний, нет вообще 128 сдвигов и 256 сравнений.

Прокатывает объяснение? Если да, то продолжим для трехчленов и пятичленов.
<theory> Поиск 






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach