На главную

3. Какую пользу может принести использование данного представления чисел?

 

На первый взгляд польза невелика, так как, при существующей архитектуре компьютеров, использование двоичной системы выгоднее (B4). Однако, при неизбежном увеличении длины разрядной сетки, а также, в задачах обработки больших массивов данных, скорость вычислений можно повысить существенным образом. Например, время операции умножения жестко привязано к длине двоичного представления чисел, в то время как, при использовании жидкой системы счисления, скорость вычисления зависит лишь от количества ненулевых членов в данном представлении. На рисунке 6 показано отношение количества точек отжатого разложения чисел (обозначим К+) к их двоичному логарифму.

Рисунок 6.

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

                                                                           (2.14)

Поскольку, в среднем, количество единиц и нулей в двоичном представлении чисел равно, то в итоге получим ускорение обычного алгоритма умножения в

                                                                                                                 (2.15)

раза, или на 44 процента!

Что касается проблемы быстрого умножения чисел, то и здесь можно построить хорошие алгоритмы с использованием жидкой формы чисел, однако, асимптотическая эффективность данных алгоритмов улучшится лишь путем уменьшения мультипликативной константы в оценке сложности O(nlogn). Поэтому оставим данную тему          в покое.

Все сказанное выше справедливо и для операции возведения в степень и во многих других приложениях.

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

В криптографии, дискретным логарифмом называют натуральное число Х, удовлетворяющее уравнению

                                                                  AX = Y ,                                                              (2.16)

где A и Y элементы аддитивной группы поля GF, а Х – мультипликативной.

Причем Y  задано, Х надо найти, а в качестве А выбирают примитивный элемент данного поля. Подробности можно посмотреть в [10]. Вместо термина дискретный логарифм, проще звучит индекс элемента Y  по основанию А, записывается indАY.

Обозначим буквой Р порядок аддитивной группы поля GF(Р) и буквой Т  - порядок его мультипликативной группы, который иногда называют периодом.

Считается, что общая задача нахождения indАY, в такой постановке, очень трудна, то есть не доказано существование эффективного (B3) алгоритма для ее решения. Приемлемых результатов можно добиться лишь в частных случаях, например, когда порядок мультипликативной группы поля гладкий, т.е. все простые делители Т невелики.

Не будем претендовать на оригинальность, а предложим метод, внешне похожий на метод решета числового поля [11], но не требующий предварительной факторизации Т.

Чтобы не утомлять всех длинными умозаключениями, приведем сразу алгоритм вычисления дискретного логарифма на конкретном примере, а метод условно назовем методом постепенного высасывания индекса. Полная его модель показана в dl2203.xls.

Вначале заметим, что в средней форме любого числа Х=, присутствует примерно одинаковое количество членов вида (2.4) -  ( 0·3b , 1·3b ,  2·3b , 4·3b ) . Также можно разложить число на ( 0·3b , 1·3b ,  2·3b ) или ( 0·3b ,   2·3b , 4·3b ) . Причем двойки в обоих случаях составляют около трети от общего количества. Далее, если немного пошевелить параметром a (2.11), то эти двойки почти равномерно распределяться по всей длине числа L(X). Здесь нет ничего удивительного, так как, для любого натурального Х известно, что если Х и Х+1 не делятся на 3, то Х+2 обязано делится. Справедливо и другое правило – либо Х, либо Х+2, либо Х+4 делится на 3. Таким образом, возникает мысль, а нельзя ли заранее высосать члены 2·3b из числа Х, скажем так, вслепую. Оказывается иногда можно и на этом построен приведенный ниже пример.

Приступим.

Пусть дано уравнение

                                                     5X = 1671 ,  mod 2203 .                                                  (2.17)

Здесь, P = 2203 – простое число, тогда T = P - 1 = 2202 – порядок мультипликативной группы GF(2203).

А = 5 – порождающий элемент группы.

Небольшое замечание. Операции умножения и возведения в степень числа Y по модулю Р приводят к операциям сложения и умножения, на уровне индексов Х, но уже по модулю Т. Таким образом, двигать индексами верхнего уровня при помощи операций нижнего уровня на порядок сложнее, однако возможно.

Далее, 2202 делится на 3, следовательно, у поля есть кубические корни из единицы    .

Определяю индекс одного из них

                                                           iq = T / 3 = 734 .                                                       (2.18)

Тогда, для проверки делимости Х на 3, достаточно возвести Y в степень iq и проверить тождество

                                                                 Y iq 1 .

 

На этапе предварительных вычислений создаем базу данных ЕВd для следующей Е-сети:

Где значения Е вычисляются по формулам (2.5), (2.17).

Также пригодится q = 5734 = 5729  · 54  · 51 ( 2203) = 285.

В базе ЕВd искать будем элементы 5Е и 5, а по ним определять Е.

Сам алгоритм разбит на этапы и шаги, на каждом этапе выполняется семь шагов.

Образно назовем этапы неделями, а шаги днями.

Первая неделя.

На первый день, в понедельник, ищем в ЕВd числа Y0 = 1671 иY0 = 2203 – 1671 = 532.

Нет таких, и это хорошо.

Проверяем делимость Х на 3:

  1671734  ( 2203 ) = 1917 , на единицу не похоже, но что-то напоминает. Идем дальше.

Проверяем делимость Х - 2 на 3:

  ( 1671 · 5-2  )734  = 1917 · 5734  ( 2203 ) = 1 , попали.

Запоминаем В = 2, Y1 = 1671 · 5-2 = 1653 ( 2203 ), которому соответствует, пока неизвестное, Х1.

Теперь удаляем грамотно q  из оперативной памяти, он больше не нужен.

На следующих шагах будем последовательно вычитать из Хi числа 6, 18, 54 …, при этом свойство делимости на 3 , по законам арифметики, должно сохраниться.

Вторник.

Проверяем Y1 = 1653 и –Y1 = 550 по ЕВd – нет.

Теперь полагаем,

или Х2 = 3·( 0 + 3 · Х1 ),

или Х2 = 3·( 2 + 3 · Х1),

или Х2 = 3·( 4 + 3 · Х1).

Всегда выбираем двойку, потому что она красивее нуля и четверки.

Вычисляем Y2 = Y1 · 5-6 = 1653 · 54 ( 2203 )  = 1142.

Среда, ускоряемся.

В ЕВd Y2 = 1142 и –Y2 = 1061 отсутствуют.

Создаем  Y3 = Y2 · 5-18 = 1142 · 1051 ( 2203 )  = 1810.

Четверг, пятница, суббота и воскресенье, тоже результата не приносят.

ЕВd: Y3 = 1810 ,  Y3 = 393   нет. Y4 = Y3 · 5-54    = 1810 · 914 ( 2203 )    = 2090.

ЕВd: Y4 = 2090 ,  Y4 = 113   нет. Y5 = Y4 · 5-162   = 2090 · 956 ( 2203 )    = 2122.

ЕВd: Y5 = 2122 ,  Y5 = 81     нет. Y6 = Y5 · 5-486   = 2122 · 2001 ( 2203 )  = 941.

ЕВd: Y6 = 941   ,  Y6 = 1262 нет. Y7 = Y6 · 5-1458  = 941 · 1218 ( 2203 )    = 578.

ЕВd: Y7 = 578   ,  Y7 = 1625 нет.

Отлично, стулья уменьшаются, шансы увеличиваются.

В воскресенье тормозим «абсолютом», чтобы на следующей неделе начать со свежей головой.

Этап второй.

Поскольку 6+18+54+162+486+1458 = 2184, то дальше продолжать не рекомендуем.

Нужен неожиданный ход.

Начали с 1671, семь членов в отпаде и никакого удовольствия. Прокачаем, сколько таких плохих чисел может остаться. В dlstat.xls приведена их статистика. Оказывается, что из 2203 плохих всего 519, то есть немногим больше четверти, хотя ожидалась треть.

Теперь можно бы и случайно попрыгать, но факты упрямо говорят, что сдвиг индекса начальных данных на 1021 или 2115 лучше, чем простой недетерминизм.

Для того чтобы не вычислять заново эту В, выбираем 2115, поскольку оно делится на 3.

Задаем Y1 = Y1 · 52115 = 1653 · 587  ( 2203 ) = 991.

Продолжаем по запланированной схеме и уже после среды попадаем в Е-сеть.

ЕВd: Y1 = 991   ,  Y1 = 1212 нет. Y2 = Y1 · 5-6   = 991 · 54 ( 2203 )     = 642.

ЕВd: Y2 = 642   ,  Y2 = 1561 нет. Y3 = Y2 · 5-18  = 642 · 1051 ( 2203 ) = 624.

ЕВd: Y3 = 624   ,  Y3 = 1579 нет. Y4 = Y3 · 5-54  = 624 · 914 ( 2203 )   = 1962.

ЕВd: Y4 = 1962   есть! 1962 = 512 . Стоп, теперь можно расслабится.

В ночь с четверга на понедельник делаем перезагрузку системы, дефрагментацию и пр.пр. Утром чистим ковер и кулер, загоняем крысу на место и приступаем к последнему этапу.

Имеем в наличии Y4 = 512, логично предположить, что Х4 = 12.

А день, какой был тогда, ах да, среда.

Х0 = Y4 + 6 + 18 + 54 = 90.

Учитываем сдвиг:          Х1 = Х0 – 2115 = -2025 ( 2202 ) = 177.

Окончательно:                Х = Х1 + В = 179.

Проверяем:                     5179 = 5162 · 512 · 54 · 51= 2150 · 1962 · 625· 5  ( 2203 ) =   1671.

Все, на выход.

В заключение сдаем бутылки и подсчитываем расходы.

Используя формулу (2.13), получим, что для хранения базы данных нам потребуется порядка O(2·e·ln(Т)) ячеек памяти.

Один раз возводили в степень iq (2.18). По оценке, взятой из книги [10], получим O(2·log2(T)) умножений. Однако, учитывая, что iq можно отжать до К+(iq) членов и применяя формулу (2.14), улучшим оценку до O(ln(T)/2) умножений в конечном поле.

Нетрудно показать, что количество шагов в одном этапе, оценивается как O(ln(T)). Труднее оценить количество самих этапов. Известно [12], что для периода Т, имеющего в своем разложении небольшое количество простых делителей, не существует эффективных  детерминированных алгоритмов. Небольшое исследование показало dlstat.xls, что среднее количество этапов оценивается величиной 0.001·Т, в то время как максимальное в три раза больше.

На рисунке 7 показано распределение общего количества шагов для нашего примера.

Рисунок 7.

Среднее количество полных шагов составляет 11, максимальное 62.

Подведем итоги.

В приведенном методе предполагалось наличие кубического корня из единицы в поле. Конечно, это слишком частный случай. Но не обязательно зацикливаться на тройке. Смешанную систему счисления можно слепить из любых чисел. Преимущество метода будет проявляться в том случае, если в поле найдется корень из единицы сравнительно небольшой степени, при этом не нужно раскладывать порядок мультипликативной группы на простые множители.

Попутно, в примере, был проиллюстрирован метод возведения в степень S, с помощью отжатой формы S+ , который очевидно имеет минимально возможную оценку сложности вычисления.

 

              

 


The Programs And Source Codes Rambler's Top100 Rambler's Top100