Содержание к диссертации
Введение
Раздел I. Аналитический обзор методов и алгоритмов решения задач большой алгоритмической сложности 17
1.1. Анализ методов и алгоритмов решения теоретико-числовых задач большой алгоритмической сложности 17
1.2. Анализ методов и алгоритмов выполнения арифметических операций при решении задач большой алгоритмической сложности 33
1.3. Обоснование целесообразности применения целочисленной арифметики для решения задач большой алгоритмической сложности 41
1.4. Постановка цели и задач исследования 53
Выводы по первому разделу 56
Раздел II. Разработка методов и алгоритмов модульного возведения в степень многоразрядных чисел 58
2.1. Модификации классического алгоритма модульного возведения в степень многоразрядных чисел 58
2.2. Развитие метода и алгоритма Монтгомери ускоренного модульного умножения многоразрядных чисел 63
2.3. Разработка базовых методов и алгоритмов расширения системы оснований и масштабирования чисел, представленных в системе остаточных классов 75
2.4. Адаптация метода и алгоритма Монтгомери модульного умножения многоразрядных чисел для системы остаточных классов 84
2.5. Разработка метода и алгоритма модульного возведения в степень многоразрядных чисел на базе алгоритма Монтгомери, адаптированного для системы остаточных классов 90
2.6. Компьютерное моделирование и сравнительная оценка разработанного метода и алгоритма модульного возведения в степень многоразрядных чисел 104
Выводы по второму разделу 110
Раздел III. Разработка методов и алгоритмов деления многоразрядных чисел, представленных в системе остаточных классов 113
3.1. Развитие метода и алгоритма деления многоразрядных чисел на основе спуска Ферма 113
3.2. Разработка метода и алгоритма целочисленного деления многоразрядных чисел на основе итераций Ньютона 120
3.3. Разработка метода и алгоритма сравнения чисел по величине в системе остаточных классов 129
3.4. Реализация метода и алгоритма деления Ньютона, адаптированного для системы остаточных классов 135
3.5 Компьютерное моделирование и сравнительная оценка разработанного метода и алгоритма деления многоразрядных чисел, представленных в системе остаточных классов 145
Выводы по третьему разделу 150
Заключение 152
Список литературы 155
Приложения 171
- Анализ методов и алгоритмов выполнения арифметических операций при решении задач большой алгоритмической сложности
- Обоснование целесообразности применения целочисленной арифметики для решения задач большой алгоритмической сложности
- Развитие метода и алгоритма Монтгомери ускоренного модульного умножения многоразрядных чисел
- Разработка метода и алгоритма целочисленного деления многоразрядных чисел на основе итераций Ньютона
Введение к работе
Одним из основных направлений развития средств вычислительной техники является разработка высокопроизводительных вычислительных устройств (ВВУ). Это обусловлено в первую очередь необходимостью решения широкого спектра важных для теории и практики математических задач, требующих вычислений с целыми многоразрядными числами или величинами, меняющимися в больших диапазонах.
В настоящее время интенсивно развивается прикладная и вычислительная теория чисел, отвечая потребности в надежной передаче, хранении и обработке коммерческой и другой цифровой информации [5,21,44,56,67,68]. В результате чего возникает огромное количество вычислительных задач, приводящих к вычислениям, при которых значения
целочисленных переменных значительно, в 10 - 10 и более раз, превышают максимум диапазона типовых вычислительных устройств, определяемого длиной аппаратно-поддерживаемого машинного слова. Кроме того, по мере развития криптографических методов и средств защиты информации сложность решаемых теоретико-числовых задач постоянно увеличивается. Возникающая при этом проблема состоит в том, что обширные классы существующих методов и алгоритмов для решения задач такого рода в рамках быстродействия обеспечиваемого современными вычислительными устройствами практически не могут быть реализованы [28,29,49,66,128].
Так же следует отметить, что проблему повышения производительности вычислительных устройств следует решать в тесной взаимосвязи с задачей обеспечения заданной точности вычислений. В реальном вычислительном процессе все вычисления осуществляются с конечным числом знаков и ошибки округлений возможны как на этапе представления данных, так и при выполнении вычислений [4,15,19,55,57,61,76,87]. Особые трудности возникают при решении плохообусловленных задач, в которых накопление ошибок округлений может
носить катастрофический характер [33,48,73,77]. Традиционным направлением повышения точности вычислений является увеличение разрядной сетки вычислительных устройств, но это влечет за собой увеличение аппаратурных и вычислительных затрат и не приводит к полному устранению ошибок округлений [64]. В современных математических системах (Mathcad, Maple и др.) для реализации вычислений, в которых исключаются ошибки округлений, используется рациональная арифметика на основе схемы приведения дробей. Однако такой подход также не является рациональным [25].
Таким образом, для решения многих научных, технических и промышленных задач мощности современных компьютеров не хватает. Не смотря на то, что ресурсы современной вычислительной техники, функционирующей в позиционной системе счисления (ПСС), постоянно совершенствуются и увеличиваются, они не могут быть безграничными в принципе. Поиск новых путей повышения эффективности вычислений, привели исследователей к объективному выводу, что в рамках обычной ПСС скачкообразного ускорения выполнения арифметических операций (АО) и полного исключения ошибок округлений добиться практически невозможно. Те или отдельные приемы совершенствования алгоритмов выполнения АО, развития архитектурных особенностей способствуют увеличению производительности, но оставляют ее в рамках одного и того же порядка [16,91].
Фундаментальной стратегией теоретических и практических исследований, осуществляемых в настоящее время, как у нас, так и за рубежом, является применение подходов, базирующихся на интенсивном использовании различных форм параллелизма на алгоритмическом, программном и аппаратном уровнях.
В свете сказанного исключительно большое значение имеют исследования, ориентированные на применение нетрадиционных способов кодирования числовой информации и соответствующих им параллельных
7 вариантов компьютерной арифметики. Многочисленные исследования
отечественных и зарубежных ученых показали, что ПСС исчерпала свои
возможности для построения ВВУ. Поэтому актуален переход к
непозиционным системам счисления, наиболее перспективной из которых
является система остаточных классов (СОК) или модулярная система
счисления [2,19,84,94,100,107,108,155].
Главным достоинством СОК является высокий уровень естественного параллелизма на уровне системы счисления. Представление операндов в виде набора остатков по малым основаниям позволяет избежать длинных межразрядных переносов при выполнении арифметических операций. Эта особенность дает значительные преимущества СОК перед ПСС при выполнении модульных операций сложения, вычитания и умножения. Особенно это актуально, если в качестве операндов выступают многоразрядные числа. Причем преимущества СОК растут вместе с разрядностью обрабатываемых данных.
Кроме этого СОК обладает такими особенностями как высокая точность, надежность, способность к самокоррекции, а также имеет возможность обменных операций между точностью, быстродействием и надежностью. Ни одна из ПСС не позволяет находить и, тем более, исправлять ошибки в процессе выполнения арифметических операций [2,12,50,54,75,82,83,96].
Известно, что СОК уже в настоящее время широко применяется для решения обширных классов трудоемких задач в самых разных прикладных областях науки и техники [39,40,101,123,145]. Вычисления с многоразрядными числами, являются одной из областей, в которых СОК имеет неоспоримые преимущества перед другими системами, и в первую очередь перед ПСС [51,54,138].
Также СОК, благодаря своему естественному внутреннему параллелизму, в последние годы выдвигается как наиболее приоритетная базовая основа для передовых высокопроизводительных компьютерных
8 технологий таких, в частности, как мультипроцессорная, суперкомпьютерная, нейронносетевая и другие [35,43,53,69,93,95,99,137]. Предпосылкой к созданию неирокомпьютерных вычислительных средств с модулярным представлением и обработкой данных является семантическое сходство математических моделей нейронных сетей и китайской теоремы остатков. Построение ВУ на основе согласованных свойств СОК и нейронных сетей позволяет выйти на следующий более прогрессивный этап развития параллельных принципов обработки информации, который может обеспечить возможность решения более сложных задач [91,97,98].
Ввиду изложенного понятна актуальность исследований ориентированных на применение СОК для построения ВВУ, и в частности для обработки многоразрядных чисел.
Не смотря на то, что вопросами применения СОК сегодня занимается огромное количество научных, исследовательских, учебных учреждений, как у нас в стране, так и за рубежом, и интерес к СОК постоянно возрастает, однако сегодня существует еще очень большой перечень рационально нерешенных задач, которые ограничивают широкое применение на практике вычислительных структур на базе СОК [51,52,69,91]. Это, прежде всего, невозможность визуального сравнения чисел, определение знака числа, трудность выполнения немодульных операций, таких как масштабирование и деление произвольных чисел. Кроме того, если обрабатываются многоразрядные числа, то значительные трудности могут возникнуть даже при выполнении модульных операций, а именно при выполнении операции модульного возведения в степень (МВС). Преодоление этих трудностей является первоочередной задачей для исследователей в области применения СОК для оптимизации выполнения арифметических операций, особенно для многоразрядных чисел.
Объектом исследования являются модулярные вычислительные структуры для обработки многоразрядных чисел.
Предметом исследования являются методы и алгоритмы выполнения множества немодульных операций и трудоемких модульных операций, которые являются основой эффективной модулярной обработки многоразрядных чисел.
Целью исследования является повышение скорости выполнения арифметических операций над многоразрядными числами с применением возможностей системы остаточных классов.
Научная задача исследования состоит в разработке методов и алгоритмов модулярных вычислений для выполнения арифметических операций над многоразрядными числами.
Для достижения поставленной цели общая научная задача была разбита на ряд частных задач:
Адаптация метода и алгоритма Монтгомери модульного умножения многоразрядных чисел для системы остаточных классов.
Разработка метода и алгоритма модульного возведения в степень многоразрядных чисел в системе остаточных классов.
Моделирование и сравнительная оценка разработанного метода и алгоритма модульного возведения в степень многоразрядных чисел.
Разработка метода и алгоритма деления многоразрядных чисел, представленных в системе остаточных классов.
Моделирование и сравнительная оценка разработанного метода и алгоритма деления многоразрядных чисел, представленных в системе остаточных классов.
Методы исследований. Для решения поставленных задач использованы методы теории чисел, алгебры, численных методов, теории алгоритмов, математического моделирования, математического анализа.
На защиту выносятся следующие основные положения:
1. Модифицированный метод и алгоритм Монтгомери ускоренного
модульного умножения многоразрядных чисел.
2. Метод и алгоритм модульного возведения в степень многоразрядных
чисел, сочетающий преимущества представления чисел в системе
остаточных классов и алгоритма ускоренного модульного умножения
Монтгомери.
Результаты компьютерного моделирования и сравнительная оценка эффективности предложенного метода и алгоритма модульного возведения в степень многоразрядных чисел.
Метод и алгоритм деления многоразрядных чисел, основанный на системе остаточных классов и итерациях Ньютона.
Результаты компьютерного моделирования и сравнительная оценка предложенного метода и алгоритма деления многоразрядных чисел, представленных в системе остаточных классов.
Научная новизна полученных в диссертации результатов состоит в следующем:
Впервые метод и алгоритм Монтгомери ускоренного модульного умножения многоразрядных чисел адаптирован для системы остаточных классов. Такая модификация стала возможной благодаря использованию обобщенной позиционной системы счисления с аналогичным набором оснований.
Впервые предложен метод и алгоритм модульного возведения в степень многоразрядных чисел, реализованный на базе классического алгоритма модульного возведения в степень и алгоритма Монтгомери, адаптированного для системы остаточных классов.
Выполнено компьютерное моделирование в среде MATLAB, на основе которого проведена сравнительная оценка эффективности предложенного метода и алгоритма модульного возведения в степень. Оценка показала, что его применение дает огромный выигрыш по времени выполнения операции модульного возведения в степень, причем этот выигрыш растет с ростом разрядностей операндов.
Впервые метод и алгоритм деления, основанный на итерациях Ньютона, реализован в системе остаточных классов. Для его реализации использовалась расширенная система остаточных классов, которая определяет вычислительный диапазон равный приблизительно квадрату от соответствующего нормального диапазона.
Выполнено компьютерное моделирование в среде MATLAB, на основании которого проведена сравнительная оценка модулярных методов и алгоритмов деления на основе итераций Ньютона и спуска Ферма. Оценка
показала, что предложенный метод Ньютона имеет огромное преимущество по количеству итераций при делении чисел, разрядность которых значительно отличается.
Практическая значимость. Разработанные модулярные методы и алгоритмы выполнения арифметических операций над многоразрядными числами могут быть использованы для целей развития теоретико-числовых методов и алгоритмов, а соответственно и для развития различных областей, в которых они применяются, в частности криптографии (криптографические системы, проверка простоты целых чисел, факторизация, дискретное логарифмирование).
Достоверность и обоснованность полученных в диссертационной работе теоретических результатов и формируемых на их основе выводов обеспечивается строгостью производимых математических - выкладок. Справедливость выводов относительно эффективности предложенных моделей, методов и алгоритмов подтверждена компьютерным моделированием в системе MATLAB.
Реализация результатов. Разработанные методы и алгоритмы модулярных вычислений для задач большой алгоритмической сложности внедрены в учебный процесс Ставропольского государственного университета при обучении студентов 5 курса специальности «Математика» по дисциплинам специализации «Обработка информации в системе остаточных классов» и «Модулярные нейрокомпьютерные технологии», что подтверждено актом об использовании научных результатов в учебном процессе.
Апробация работы. Основные результаты диссертационного исследования докладывались на Международной школе-семинаре по геометрии и анализу памяти Н.В.Ефимова (Ростов-на-Дону - Абрау-Дюрсо, сентябрь, 2006г.), XW Международной молодежной научной конференции "Туполевские чтения" (Казань, ноябрь, 2006г.), VIII Международной научно-технической конференции "Проблемы техники и технологии телекоммуникаций" (Уфа, ноябрь, 2007г.), Ш Международной научно-технической конференции "Инфокоммуникационные технологии в науке, производстве и образовании" (Ставрополь, май, 2008г.), 51-й научно-методической конференции
12 "Университетская наука - региону" (Ставрополь, апрель, 2006г.), 53-й научно-методической конференции "Университетская наука - региону" (Ставрополь, апрель, 2008г.).
Основное содержание исследования полностью отражено в 12 публикациях, две из которых в ведущих рецензируемых научных журналах из перечня журналов, рекомендованных ВАК Минобрнауки России для защиты докторских и кандидатских диссертаций.
Структура и объем диссертации. Работа состоит из списка сокращений и обозначений, введения, трех разделов, заключения, списка литературы, содержащего 156 наименований и семи приложений. Основная часть работы содержит 170 страниц машинописного текста.
Во введении обоснована актуальность и новизна темы исследования, сформулированы цели и задачи работы, изложены основные результаты исследований, показана их научная новизна и практическая значимость, указаны основные положения, выносимые на защиту.
В первом разделе проведен анализ различных методов и алгоритмов теоретико-числовых задач. В качестве задач такого рода выделены: проверка простоты целых чисел специального и произвольного вида, факторизация, вычисления с применением эллиптических кривых. Анализ показал, что практически все они требуют неоднократного выполнения двух трудоемких арифметических операций: модульного возведения в степень и деления произвольных чисел. Однако при реализации теоретико-числовых методов и алгоритмов в большинстве случаев исходными данными являются многоразрядные числа, разрядность которых постоянно растет. Поэтому выполнение входящих в них операций модульного возведения в степень и деления становится неприемлемо сложным.
Проанализированы базовые алгоритмы арифметики многократной точности (АМТ), которая применяется в современных ЭВМ для обработки многоразрядных чисел и представляет собой арифметику приведения по модулю. Анализ показал, что все они обладают главным недостатком, который характерен для ПСС в целом — это необходимость учета
13 зависимости между разрядами. Для того чтобы значительно повысить
эффективность выполнения арифметических операций над многоразрядными
числами необходимо применение такой арифметики, в которой бы
поразрядные связи отсутствовали.
Рассмотрены основы построения компьютерной арифметики на базе непозиционных систем, наиболее перспективной из которых является система остаточных классов. Описаны алгоритмы сложения, вычитания, умножения, а также принцип обработки рациональных чисел в СОК. Определены преимущества СОК в сравнении с ПСС на базе которой строится арифметика многократной точности: высокий уровень параллелизма, малая разрядность остатков, высокая точность, надежность и способность к самокоррекции, возможность реализации принципа конвейерной обработки информации. Выделен ряд областей, в которых преимущества СОК могут быть использованы максимально эффективно. Это в первую очередь обработка многоразрядных чисел. Обоснована необходимость разработки методов и алгоритмов выполнения операций модульного возведения в степень и деления многоразрядных чисел на основе СОК.
Во втором разделе рассмотрена возможность применения классического алгоритма модульного возведения в степень для обработки многоразрядных чисел. Так как классический алгоритм модульного возведения в степень состоит из ряда модульных умножений, то главным вопросом является разработка эффективного алгоритма для выполнения этих операций. Трудность заключается в том, что операция модульное умножение по произвольному модулю предполагает реализацию операции деления, которая является достаточно сложной в любой системе счисления, в том числе и в ПСС. Особенно если операндами являются многоразрядные числа.
Для ускорения операции модульного умножения выбран метод и алгоритм Монтгомери, основная идея которого заключается в преобразовании операндов в некоторые остатки и вычислении произведения
14 этих остатков. Полученный результат умножения преобразуется назад к нормальному виду. Такой подход выгоден, если необходимо вычислить ряд умножений в преобразованной сфере. Главное преимущество алгоритма Монтгомери состоит в том, что операция модульного умножения по произвольному модулю с помощью определенных преобразований заменяется рядом сложений и умножений по модулю, представляющему собой степень двойки. Применение такого модуля при аппаратной реализации позволяет трудоемкую операцию деления заменить несколькими битовыми операциями сдвига. Для того чтобы алгоритм Монтгомери подходил для практической реализации удобнее всего выбрать двоичную систему счисления. Однако алгоритм Монтгомери и его модификации применяются в обычной ПСС, поэтому время их выполнения остается в рамках одного и того же порядка.
Предложен метод и алгоритм выполнения операции расширения системы оснований системы остаточных классов на основе представления ортогональных базисов в ОПСС. Его сложность оценивается
оЫпк -l)~ + (к +1) щ + пг + 2{к - l)j битовых операций, где р^
наибольшее основание СОК, рг - основание по которому определяется
остаток, щ - разрядность основания р^, пг - разрядность основания рг, к -
количество оснований. На основе предложенного метода расширения системы оснований разработан параллельный метод масштабирования с отбрасыванием остатка.
Метод и алгоритм Монтгомери ускоренного модульного умножения многоразрядных чисел адаптирован для СОК. На его базе разработан метод и алгоритм модульного возведения в степень многоразрядных чисел.
Выполнено компьютерное моделирование и проведена сравнительная оценка разработанного метода и алгоритма модульного возведения в степень многоразрядных чисел. Сравнительная оценка показала, что по вычислительной сложности (количеству битовых операций) алгоритм
15 Монтгомери, адаптированный для системы остаточных классов уступает
основному алгоритму Монтгомери приблизительно в 1,2 раза. Однако за счет малой разрядности оснований СОК и параллельной структуры вычислений разработанный метод и алгоритм дает огромный выигрыш по времени реализации операции модульного возведения в степень, причем этот выигрыш растет с ростом разрядностей операндов. Применение разработанного алгоритма позволяет время вычисления RSA шифрования с 1024 битовыми операндами уменьшить в 17,5 раз.
В третьем разделе рассмотрен итерационный модулярный метод и алгоритм общего деления на основе модификации метода спуска Ферма. Его недостатком является то, что в случае если разрядности делимого и делителя отличаются значительно, то для вычисления округленного частного может потребоваться много итераций. В то же время если допустимая ошибка задана не выше 0.1, то достаточно провести всего четыре итерации.
Разработан метод и алгоритм деления в СОК, основанный на итерациях Ньютона. В сравнении с алгоритмом деления, основанным на спуске Ферма, алгоритм обладает несколькими преимуществами. Во-первых, нет необходимости составления, хранения и аппроксимации таблицы приблизительных делителей. Во-вторых, количество итераций для определения величины |_M/Z>J не зависит от величины делимого. Таким образом, если необходимо разделить несколько чисел на одно и тоже число Ь, то величина |_M/6J может быть вычислена один раз. Алгоритм на основе
спуска Ферма при делении каждой новой пары чисел а и b выполняется полностью. В-третьих, предложенный алгоритм имеет огромные временные преимущества при делении чисел, разрядность которых значительно
отличается. Кроме того, количество итераций может быть уменьшено, если в
if качестве начального приближения выбрать Z\=2 , где К выбирается из
условия
M/2K+l
MI2K
Для того чтобы реализовать предложенный метод и алгоритм деления в СОК, разработан параллельный алгоритм выполнения операции сравнения чисел. Этот алгоритм является универсальным, так как он позволяет различать равенство двух чисел, знак числа, абсолютное значение чисел и переполнение разрядной сетки ЭВМ. Время сравнения при использовании этого метода равно 0([log2 я]+1), где п - число оснований СОК.
Выполнено компьютерное моделирование в системе MATLAB и проведена сравнительная оценка методов и алгоритмов деления спуска Ферма и итераций Ньютона. Которая показала, при условии выполнения только одной итерации они имеют приблизительно одну вычислительную сложность. Если выполняется деление чисел одинаковой разрядности или если их разрядность отличается незначительно, то метод Ферма реализуется быстрее. Если разрядности делимого и делителя отличаются значительно, огромное преимущество по времени выполнения деления дает применение метода Ньютона. Например, если делимое 6-ти разрядное, а делитель 1024-х разрядное число, то время реализации разработанного метода и алгоритма деления в сравнении с методом спуска Ферма сокращается в « 138 раз.
В заключении подведены итоги и обобщены результаты исследования.
В приложении приведены численные примеры и листинги программ, а так же табличный материал необходимый для проводимых оценок.
Автор выражает искреннюю благодарность научному руководителю, заслуженному деятелю науки и техники РФ, доктору технических наук, профессору Н.И. Червякову, а так же коллективу кафедр высшей алгебры и геометрии и прикладной математики и информатики за помощь, оказанную при написании диссертации, и критические замечания, высказанные при ее обсуждении.
Анализ методов и алгоритмов выполнения арифметических операций при решении задач большой алгоритмической сложности
В большинстве современных компьютеров при обработке многоразрядных чисел используется арифметика многократной точности (АМТ). Суть этого способа обработки многоразрядных чисел состоит в том, что целое число, заполняющее например 10 машинных слов в памяти компьютера, размер слова которого со = 1010, имеет 100 десятичных разрядов. Однако, согласно АМТ, это число рассматривается как 10 разрядное по основанию 1010. То есть арифметика многократной точности представляет собой арифметику приведения по модулю [11,36,112,119,131].
Проанализируем алгоритмы четырех базовых арифметических операции над многоразрядными числами [11,36,131]: сложения, вычитания, умножения и деления. Причем можно рассматривать только неотрицательные целые числа, так как арифметические операции над отрицательными целыми числами, числами с разделяющей точкой и числами в формате с плавающей точкой получаются путем несложных модификаций алгоритмов для неотрицательных целых чисел.
Пусть х - неотрицательное п - разрядное целое число по основанию Ъ. То есть оно может быть представлено в виде где хп_х Ф О. Представление чисел в виде (1.2.1) называется представлением по основанию b и записывается как х = (Х„_1ЛГ,3_2...Л:]Х0)b.
В первую очередь необходимо проанализировать алгоритмы операций сложения и вычитания многоразрядных чисел. Несмотря на то, что эти операции в АМТ, как и в любой другой арифметике, являются простыми, но в то же время они являются самыми главными. Так как на них основаны алгоритмы более сложных операций. При этом достаточно рассмотреть только алгоритмы сложения и вычитания чисел с одинаковым числом разрядов в представлении по основанию Ъ. Сложение и вычитание чисел с различным числом разрядов можно свести к случаю одинакового числа разрядов путем приписывания нулей слева у числа с меньшим количеством разрядов.
На рисунке 1.2.1 приведена схема алгоритма сложения многоразрядных чисел арифметики многократной точности.
Согласно этой схеме каждая цифра j - го разряда результата сложения w = {wnwn_x...wxWo)b получается путем последовательного суммирования цифр j - го разряда слагаемых и цифры переноса с, полученной при нахождении j— \ - го разряда результата сложения, и приведения этой суммы по модулю Ъ. Таким образом, для определения цифры каждого последующего разряда результата сложения необходимо сначала определить цифру предыдущего разряда и цифру переноса. Так как здесь выполняется сложение МЧ, то для того, чтобы не допустить выхода результата сложения за пределы разрядной сетки соответствующего арифметического устройства цифры каждого разряда последовательно приводятся по модулю b. Если b = 2 или b - размер машинного слова, то для этого нет необходимости выполнять деление. Достаточно взять соответствующий разряд (или разряды) в записи Xj + у j + с.
Алгоритмы сложения и вычитания многоразрядных чисел арифметики многократной точности аналогичны и имеются небольшие отличия. Но для того, чтобы эти операции выполнялись настолько быстро, насколько это возможно, чаще всего используются различные алгоритмы [36].
На рисунке 1.2.2 приведена схема алгоритма вычитания многоразрядных чисел арифметики многократной точности. Цифра j - го разряда результата вычитания g = (gn-\gn-2—S\So)b получается путем последовательного вычитания соответствующих цифр j - го разряда операндов и сложения этой разности с цифрой переноса к, полученной при нахождении цифры j — \ - го разряда результата вычитания. Так же как и при сложении МЧ, для того, чтобы избежать переполнения, цифры каждого разряда g = х- - у + к последовательно приводятся по модулю b
Обоснование целесообразности применения целочисленной арифметики для решения задач большой алгоритмической сложности
Главными целями процесса развития современных вычислительных устройств были и остаются повышение их производительности и обеспечение высокой информационной и технической надежности. На сегодняшний день это обусловлено в первую очередь тем, что во многих областях науки и техники возникает широкий спектр математических задач, приводящих к вычислениям, при которых переменные значительно, в 103-106 и более раз, превышают максимум типового компьютерного диапазона [30,44,68].
Общей фундаментальной стратегией исследований в области создания высокопроизводительных вычислительных устройств, осуществляемых в настоящее время, как у нас, так и за рубежом, является применение нетрадиционных способов кодирования числовой информации и соответствующих им параллельных вариантов компьютерной арифметики.
В свете сказанного актуален переход к непозиционным системам счисления, наиболее перспективной из которых является система остаточных классов (СОК), или модулярная система счисления. Эта мысль зародилась в середине 50-х годов прошлого века, когда чешские ученые М.Валах А. Свобода предложили для кодирования целых чисел в математических машинах использовать кольцо вычетов по составному модулю с попарно взаимно простыми основаниями. В течение последующих 50-ти лет работы многих ученых (А.А.Ляпунова, О.Б.Лупанова, И.Я.Акушского, Д.И.Юдицкого, Е.С.Адрианова, А.Ф.Чернявского, А.А.Коляды, Н.И.Червякова, В.А.Краснобаева) были посвящены возможностям применения этой системы в ЭВМ [3,16,50,51]. Основная идея СОК состоит в том, чтобы оперировать не непосредственно многоразрядным числом х, а его остатками или вычетами X! = хmodрх, х2 = хmodр2, ..., хп = xmodpn, где р},р2,...,рп - взаимно простые числа, называемые модулями или основаниями СОК, вычеты определяются как хг- = x — \xjpi\-pi, і = \,п. В этом случае объём диапазона п представимых чисел в этой системе характеризуется величиной Р = YlP, и /=i любое целое положительное число х из этого диапазона можно представить в виде набора остатков от деления этого числа на выбранные основания системы [2,70,109], то есть Характерной особенностью представления (1.3.1) является то, что каждый остаток х,- получается независимо от других, но при этом содержит информацию обо всем числе. Возможность такого представления числа определяется теоремой о делении с остатком в кольце целых чисел [8,13]. Теорема 1.3.1. Если х є Z, р є Z, р Ф 0 , то существуют единственные Установить взаимнооднозначное соответствие между целыми числами из диапазона [0,Р) и их остатками помогает следующая теорема [60]. Теорема 1.3.2. Если pt, i = \,n — попарно простые целые числа, а х; остатки от деления любого целого числа х на числа pt, i = l,n, тогда наборами остатков (л;,, х2,..., хп) взаимнооднозначно, то есть Если обрабатываются целые числа и результат приводится по одному модулю р, то такая арифметическая система называется одномодульной СОК. При этом важно выбирать р настолько большим, чтобы все данные и решение задачи не превышали его значение. Иначе некоторые решения могут быть неверными, но они будут сравнимы по модулю р с правильными ответами. Эта ситуация называется псевдопереполнением. Избежать ее можно, используя несколько модулей, то есть многомодульную СОК [19].
Один и тот же рабочий диапазон может быть достигнут с помощью различных наборов оснований и способов, позволяющих выбирать такие наборы, существует большое количество. В общем случае вопрос о выборе той или иной системы оснований СОК решается неоднозначно и обычно связан с характером решаемой задачи. Поэтому для того, чтобы осуществить рациональный выбор сначала необходимо определить критерий оптимизации набора оснований [22,23,42,60,71].
Рассматривая вычисления в пределах модулярной арифметики (МА) все операции можно разбить на две группы: модульные и немодульные.
Операции сложения, вычитания и умножения в остаточной арифметике относятся к модульным операциям, то есть не требуют знания позиционных характеристик (ПХ) обрабатываемых чисел и поэтому считаются быстрыми. Остановимся на правилах их выполнения.
Развитие метода и алгоритма Монтгомери ускоренного модульного умножения многоразрядных чисел
Изучение литературы [111,119,131,134] показало, что одним из самых эффективных алгоритмов модульного умножения многоразрядных чисел является алгоритм модульного умножения Монтгомери, основная идея которого заключается в преобразовании двух целых чисел в некоторые остатки и вычислении произведения этих остатков. Полученный результат умножения преобразуется назад к нормальному виду. Такой подход выгоден, если необходимо вычислить ряд умножений в преобразованной сфере (например, при МВС).
Для того чтобы применить алгоритм Монтгомери для модульного умножения двух целых чисел а и Ъ необходимо выполнить преобразование обоих операндов согласно алгоритму представленному на рисунке 2.2.1.
Значение М может быть найдено с помощью расширенного алгоритма Евклида [8,19]. Для исключения деления при преобразовании каждого операнда, то есть при нахождении t, можно применить следующий подход. Используя деление один раз вычислить величину R2 modM. Далее для того чтобы получить преобразованный вид каждого операнда, например операндов а и Ъ нужно алгоритм на рисунке 2.2.1 применить к
Т-a-R"modM и T = b-R modM. В этом случае при выполнении модульного сокращения на R сложная операция деления заменяется операцией сдвига, которая является битовой операцией. В результате будут получены операнды в преобразованном виде, то есть А = a-RmodМ и B = b-RmodM. Монтгомери представлена на рисунке 2.2.2. Алгоритм вычисляет S = ABR l modМ.
На каждой итерации алгоритма приведенного на рисунке 2.2.2 для вычисления qi необходимо самое большее 0{к х (га + к)) битовых операций умножения и 0(т) битовых операций сложения, а для вычисления Sj+\ необходимо 0{lk х т) битовых операций умножения и 0(2т) битовых операций сложения. Кроме этого при вычислении д; два раза выполняется операция приведения по модулю. Значение qt вычисляется таким образом, что величина S + at В + qt М кратна /3. Отсюда следует главное преимущество алгоритма модульного умножения Монтгомери — модульное сокращение на /3 выполняется не делением, а смещением или сдвигом вправо, а на выполнение этой операции времени не тратится. До выполнения основной части алгоритма один раз вычисляется значение М", при этом порядок сложности равен порядку сложности расширенного алгоритма Евклида.
Для того чтобы алгоритм модульного умножения Монтгомери подходил для практической реализации удобнее всего выбрать систему счисления по основанию (5-2. Схема этого алгоритма представлена на рисунке 2.2.3. Такой выбор дает ряд преимуществ.
Во-первых, так как из условия (,М,2)=1 следует, что модуль М должен быть нечетным, то это приводит к М mod 2 = 1, следовательно М" = - 1/ML = 1. Таким образом, при выборе системы по основанию /3 = 2 нет необходимости вычисления вспомогательной величины М".
Во-вторых, при вычислении qt приведение по модулю выполняется только один раз и так как модуль (3 = 2, то эта операция представляет собой выделение младшего разряда в двоичном представлении и требует выполнения одной битовой операции.
Разработка метода и алгоритма целочисленного деления многоразрядных чисел на основе итераций Ньютона
Разработанный алгоритм модульного возведения в степень объединяет преимущества алгоритма Монтгомери, который является одним из самых эффективных алгоритмов модульного умножения многоразрядных чисел и преимущества СОК, которые особенно сильно проявляются при работе с многоразрядными числами.
Применение алгоритма Монтгомери модульного умножения многоразрядных чисел позволяет реализацию трудоемкой операции деления МЧ заменить рядом простых операций над числами малой разрядности, то есть рядом сложений, умножений и сдвигов. При этом его применение для модульного умножения многоразрядных чисел оправдано и дает значительное преимущество по времени реализации модульного умножения, если выполняется целый ряд модульных умножений в преобразованном виде, например при модульном возведении в степень.
Применение СОК позволяет полностью исключить длинные межразрядные переносы. Вычисления проводятся по каждому основанию параллельно и время их выполнения не суммируется. Также применение СОК позволяет заменить обработку многоразрядных чисел, обработкой чисел, разрядность которых не превышает разрядности оснований, в результате чего получается значительное сокращение времени реализации.
Для того чтобы выполнить сравнительную оценку разработанного алгоритма модульного возведения в степень многоразрядных чисел в СОК необходимо сделать некоторые уточнения.
Классический алгоритм модульного возведения в степень может быть сведен к ряду модульных умножений и возведений в квадрат (умножения числа на самого себя), которые в модифицированном варианте выполняются параллельно, и главным вопросом является разработка эффективного алгоритма для выполнения этих операций. Поэтому для того, чтобы оценить преимущество, даваемое разработанным алгоритмом модульного возведения в степень многоразрядных чисел в СОК нет необходимости сравнивать его с . классическим алгоритмом модульного возведения в степень в целом. Достаточно оценить этот выигрыш для одной операции модульного умножения. Тогда во всем классическом алгоритме модульного возведения в степень выигрыш будет умножен на количество операций модульного умножения и возведения в квадрат, которое необходимо выполнить.
Опираясь на изученную литературу, для повышения скорости выполнения операции модульного умножения выбран алгоритм Монтгомери. Вначале этого алгоритма выполняется прямое преобразование операндов, а в конце обратное преобразование результата. Поэтому его выполнение оправдано только, если необходимо выполнить ряд модульных умножений в преобразованной сфере, то есть как при выполнении операции модульного возведения в степень. С учетом этого для оценки представленного в параграфе 2.2 на рисунке 2.2.3 алгоритма модульного умножения Монтгомери (далее по тексту Монтгомери) достаточно оценить непосредственно алгоритм без учета прямого и обратного преобразования. Преобразование Монтгомери можно оценить отдельно, однако его сложность, в случае если последовательно выполняется большое количество модульных умножений, практически не повлияет на преимущество, даваемое непосредственно алгоритмом Монтгомери.
Так как алгоритм Монтгомери и его модификации применяются в обычной ПСС, то их сложность остается в рамках одного и того же порядка. Для уменьшения времени реализации алгоритм Монтгомери был адаптирован для СОК. Для того чтобы применить адаптированный алгоритм необходимо сначала перевести операнды из ПСС в СОК, а результат модульного умножения из СОК в ПСС. Существует большое количество алгоритмов для выполнения этих преобразований, но все они достаточно сложные. Поэтому преимущества представленного в параграфе 2.4 на рисунке 2.4.1 алгоритма Монтгомери, адаптированного для СОК (далее по тексту Монтгомери + СОК) в сравнении с основным алгоритмом Монтгомери могут быть оценены только с точки зрения вычислительного устройства целиком работающего в СОК.
Таким образом, при оценке разработанного алгоритма модульного возведения в степень многоразрядных чисел преобразования, которые необходимо выполнить в начале и в конце алгоритма Монтгомери, а так же прямое ПСС-СОК и обратное СОК-ПСС преобразования оцениваться не будут.
С учетом сделанных уточнений для оценки разработанного алгоритма модульного возведения в степень многоразрядных чисел необходимо сравнить алгоритмы Монтгомери и Монтгомери + СОК, которые имеют абсолютно идентичную структуру. В алгоритме Монтгомери для нахождения значения д, требуется 0(т +1) битовых операций, а для вычисления Sj+\ требуется 0(2т +1) битовых операций, где т - разрядность операндов. Следовательно, время нахождения результата модульного умножения определяется временем реализации 0{т{т +1 + 2т +1)) или 0(3т + 2тJ битовых операций. Для оценки алгоритма Монтгомери+СОК необходимо оценить порядок сложности операций сложения и умножения чисел в СОК, а так же порядок сложности операции определения остатка расширением системы оснований. В СОК для выполнения вычислительного алгоритма сложения по модулю pi нужно выполнить 0(]log2(РІ —1)[ ) или 0((rif -і)")битовых операций, а для умножения по модулю pj необходимо выполнить 0(]log2/?;[) или 0(rij) битовых операций. Скобки }х[ означают наименьшее целое, превосходящее JC , а щ разрядность основания pi.
