Разработка методов и алгоритмов модулярных вычислений для задач большой алгоритмической сложности тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Лобес, Мария Владимировна

• Лобес, Мария Владимировна
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Лобес, Мария Владимировна

Основные обозначения и сокращения.

Введение.

Раздел I. Аналитический обзор методов и алгоритмов решения задач большой алгоритмической сложности.

1.1. Анализ методов и алгоритмов решения теоретико-числовых задач большой алгоритмической сложности.

1.2. Анализ методов и алгоритмов выполнения арифметических операций при решении задач большой алгоритмической сложности.

1.3. Обоснование целесообразности применения целочисленной арифметики для решения задач большой алгоритмической сложности.

1.4. Постановка цели и задач исследования.

Выводы по первому разделу.

Раздел II. Разработка методов и алгоритмов модульного возведения в степень многоразрядных чисел.

2.1. Модификации классического алгоритма модульного возведения в степень многоразрядных чисел.

2.2. Развитие метода и алгоритма Монтгомери ускоренного модульного умножения многоразрядных чисел.

2.3. Разработка базовых методов и алгоритмов расширения системы оснований и масштабирования чисел, представленных в системе остаточных классов.

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

2.5. Разработка метода и алгоритма модульного возведения в степень многоразрядных чисел на базе алгоритма Монтгомери, адаптированного для системы остаточных классов.

2.6. Компьютерное моделирование и сравнительная оценка разработанного метода и алгоритма модульного возведения в степень многоразрядных чисел.

Выводы по второму разделу.

Раздел III. Разработка методов и алгоритмов деления многоразрядных чисел, представленных в системе остаточных классов.

3.1. Развитие метода и алгоритма деления многоразрядных чисел на основе спуска Ферма.

3.2. Разработка метода и алгоритма целочисленного деления многоразрядных чисел на основе итераций Ньютона.

3.3. Разработка метода и алгоритма сравнения чисел по величине в системе остаточных классов.

3.4. Реализация метода и алгоритма деления Ньютона, адаптированного для системы остаточных классов.

3.5 Компьютерное моделирование и сравнительная оценка разработанного метода и алгоритма деления многоразрядных чисел, представленных в системе остаточных классов.

Выводы по третьему разделу.

Введение диссертации (часть автореферата) на тему «Разработка методов и алгоритмов модулярных вычислений для задач большой алгоритмической сложности»

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

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

5,21,44,56,67,68]. В результате чего возникает огромное количество вычислительных задач, приводящих к вычислениям, при которых значения

3 6 целочисленных переменных значительно, в 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].

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

В свете сказанного исключительно большое значение имеют исследования, ориентированные на применение нетрадиционных способов кодирования числовой информации и соответствующих им параллельных вариантов компьютерной арифметики. Многочисленные исследования отечественных и зарубежных ученых показали, что ПСС исчерпала свои возможности для построения ВВУ. Поэтому актуален переход к непозиционным системам счисления, наиболее перспективной из которых является система остаточных классов (СОК) или модулярная система счисления [2,19,84,94,100,107,108,155].

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

Кроме этого СОК обладает такими особенностями как высокая точность, надежность, способность к самокоррекции, а также имеет возможность обменных операций между точностью, быстродействием и надежностью. Ни одна из ПСС не позволяет находить и, тем более, исправлять ошибки в процессе выполнения арифметических операций [2,12,50,54,75,82,83,96].

Известно, что СОК уже в настоящее время широко применяется для решения обширных классов трудоемких задач в самых разных прикладных областях науки и техники [39,40,101,123,145]. Вычисления с многоразрядными числами, являются одной из областей, в которых СОК имеет неоспоримые преимущества перед другими системами, и в первую очередь перед ПСС [51,54,138].

Также СОК, благодаря своему естественному внутреннему параллелизму, в последние годы выдвигается как наиболее приоритетная базовая основа для передовых высокопроизводительных компьютерных технологий таких, в частности, как мультипроцессорная, суперкомпьютерная, нейронносетевая и другие [35,43,53,69,93,95,99,137]. Предпосылкой к созданию нейрокомпьютерных вычислительных средств с модулярным представлением и обработкой данных является семантическое сходство математических моделей нейронных сетей и китайской теоремы остатков. Построение ВУ на основе согласованных свойств СОК и нейронных сетей позволяет выйти на следующий более прогрессивный этап развития параллельных принципов обработки информации, который может обеспечить возможность решения более сложных задач [91,97,98].

Ввиду изложенного понятна актуальность исследований ориентированных на применение СОК для построения ВВУ, и в частности для обработки многоразрядных чисел.

Не смотря на то, что вопросами применения СОК сегодня занимается огромное количество научных, исследовательских, учебных учреждений, как у нас в стране, так и за рубежом, и интерес к СОК постоянно возрастает, однако сегодня существует еще очень большой перечень рационально нерешенных задач, которые ограничивают широкое применение на практике вычислительных структур на базе СОК [51,52,69,91]. Это, прежде всего, невозможность визуального сравнения чисел, определение знака числа, трудность выполнения немодульных операций, таких как масштабирование и деление произвольных чисел. Кроме того, если обрабатываются многоразрядные числа, то значительные трудности могут возникнуть даже при выполнении модульных операций, а именно при выполнении операции модульного возведения в степень (МВС). Преодоление этих трудностей является первоочередной задачей для исследователей в области применения СОК для оптимизации выполнения арифметических операций, особенно для многоразрядных чисел.

Объектом исследования являются модулярные вычислительные структуры для обработки многоразрядных чисел.

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

Целью исследования является повышение скорости выполнения арифметических операций над многоразрядными числами с применением возможностей системы остаточных классов.

Научная задача исследования состоит в разработке методов и алгоритмов модулярных вычислений для выполнения арифметических операций над многоразрядными числами.

Для достижения поставленной цели общая научная задача была разбита на ряд частных задач:

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

2. Разработка метода и алгоритма модульного возведения в степень многоразрядных чисел в системе остаточных классов.

3. Моделирование и сравнительная оценка разработанного метода и алгоритма модульного возведения в степень многоразрядных чисел.

4. Разработка метода и алгоритма деления многоразрядных чисел, представленных в системе остаточных классов.

5. Моделирование и сравнительная оценка разработанного метода и алгоритма деления многоразрядных чисел, представленных в системе остаточных классов.

Методы исследований. Для решения поставленных задач использованы методы теории чисел, алгебры, численных методов, теории алгоритмов, математического моделирования, математического анализа.

На защиту выносятся следующие основные положения:

1. Модифицированный метод и алгоритм Монтгомери ускоренного модульного умножения многоразрядных чисел.

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

3. Результаты компьютерного моделирования и сравнительная оценка эффективности предложенного метода и алгоритма модульного возведения в степень многоразрядных чисел.

4. Метод и алгоритм деления многоразрядных чисел, основанный на системе остаточных классов и итерациях Ньютона.

5. Результаты компьютерного моделирования и сравнительная оценка предложенного метода и алгоритма деления многоразрядных чисел, представленных в системе остаточных классов.

Научная новизна полученных в диссертации результатов состоит в следующем:

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

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

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

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

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

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

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

Реализация результатов. Разработанные методы и алгоритмы модулярных вычислений для задач большой алгоритмической сложности внедрены в учебный процесс Ставропольского государственного университета при обучении студентов 5 курса специальности «Математика» по дисциплинам специализации «Обработка информации в системе остаточных классов» и «Модулярные нейрокомпьютерные технологии», что подтверждено актом об использовании научных результатов в учебном процессе.

Апробация работы. Основные результаты диссертационного исследования докладывались на Международной школе-семинаре по геометрии и анализу памяти Н.В.Ефимова (Ростов-на-Дону - Абрау-Дюрсо, сентябрь, 2006г.), XIV Международной молодежной научной конференции "Туполевские чтения" (Казань, ноябрь, 2006г.), VIII Международной научно-технической конференции "Проблемы техники и технологии телекоммуникаций" (Уфа, ноябрь, 2007г.), 1П Международной научно-технической конференции "Инфокоммуникационные технологии в науке, производстве и образовании" (Ставрополь, май, 2008г.), 51-й научно-методической конференции

Университетская наука - региону" (Ставрополь, апрель, 2006г.), 53-й научно-методической конференции "Университетская наука - региону" (Ставрополь, апрель, 2008г.).

Основное содержание исследования полностью отражено в 12 публикациях, две из которых в ведущих рецензируемых научных журналах из перечня журналов, рекомендованных ВАК Минобрнауки России для защиты докторских и кандидатских диссертаций.

Структура и объем диссертации. Работа состоит из списка сокращений и обозначений, введения, трех разделов, заключения, списка литературы, содержащего 156 наименований и семи приложений. Основная часть работы содержит 170 страниц машинописного текста.

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

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

Проанализированы базовые алгоритмы арифметики многократной точности (АМТ), которая применяется в современных ЭВМ для обработки многоразрядных чисел и представляет собой арифметику приведения по модулю. Анализ показал, что все они обладают главным недостатком, который характерен для ПСС в целом - это необходимость учета зависимости между разрядами. Для того чтобы значительно повысить эффективность выполнения арифметических операций над многоразрядными числами необходимо применение такой арифметики, в которой бы поразрядные связи отсутствовали.

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

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

Для ускорения операции модульного умножения выбран метод и алгоритм Монтгомери, основная идея которого заключается в преобразовании операндов в некоторые остатки и вычислении произведения этих остатков. Полученный результат умножения преобразуется назад к нормальному виду. Такой подход выгоден, если необходимо вычислить ряд умножений в преобразованной сфере. Главное преимущество алгоритма Монтгомери состоит в том, что операция модульного умножения по произвольному модулю с помощью определенных преобразований заменяется рядом сложений и умножений по модулю, представляющему собой степень двойки. Применение такого модуля при аппаратной реализации позволяет трудоемкую операцию деления заменить несколькими битовыми операциями сдвига. Для того чтобы алгоритм Монтгомери подходил для практической реализации удобнее всего выбрать двоичную систему счисления. Однако алгоритм Монтгомери и его модификации применяются в обычной ПСС, поэтому время их выполнения остается в рамках одного и того же порядка.

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

Метод и алгоритм Монтгомери ускоренного модульного умножения многоразрядных чисел адаптирован для СОК. На его базе разработан метод и алгоритм модульного возведения в степень многоразрядных чисел.

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

Монтгомери, адаптированный для системы остаточных классов уступает основному алгоритму Монтгомери приблизительно в 1,2 раза. Однако за счет малой разрядности оснований СОК и параллельной структуры вычислений разработанный метод и алгоритм дает огромный выигрыш по времени реализации операции модульного возведения в степень, причем этот выигрыш растет с ростом разрядностей операндов. Применение разработанного алгоритма позволяет время вычисления RSA шифрования с 1024 битовыми операндами уменьшить в 17,5 раз.

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

Разработан метод и алгоритм деления в СОК, основанный на итерациях Ньютона. В сравнении с алгоритмом деления, основанным на спуске Ферма, алгоритм обладает несколькими преимуществами. Во-первых, нет необходимости составления, хранения и аппроксимации таблицы приблизительных делителей. Во-вторых, количество итераций для определения величины |M/Z>J не зависит от величины делимого. Таким образом, если необходимо разделить несколько чисел на одно и тоже число b, то величина |M/Z>J может быть вычислена один раз. Алгоритм на основе спуска Ферма при делении каждой новой пары чисел а и b выполняется полностью. В-третьих, предложенный алгоритм имеет огромные временные преимущества при делении чисел, разрядность которых значительно отличается. Кроме того, количество итераций может быть уменьшено, если в is качестве начального приближения выбрать Z\= 2 , где К выбирается из

Ь<[м/2К условия \м/2К+1

Для того чтобы реализовать предложенный метод и алгоритм деления в СОК, разработан параллельный алгоритм выполнения операции сравнения чисел. Этот алгоритм является универсальным, так как он позволяет различать равенство двух чисел, знак числа, абсолютное значение чисел и переполнение разрядной сетки ЭВМ. Время сравнения при использовании этого метода равно 0(\log2 я]+1), где п - число оснований СОК.

Выполнено компьютерное моделирование в системе MATLAB и проведена сравнительная оценка методов и алгоритмов деления спуска Ферма и итераций Ньютона. Которая показала, при условии выполнения только одной итерации они имеют приблизительно одну вычислительную сложность. Если выполняется деление чисел одинаковой разрядности или если их разрядность отличается незначительно, то метод Ферма реализуется быстрее. Если разрядности делимого и делителя отличаются значительно, огромное преимущество по времени выполнения деления дает применение метода Ньютона. Например, если делимое 6-ти разрядное, а делитель 1024-х разрядное число, то время реализации разработанного метода и алгоритма деления в сравнении с методом спуска Ферма сокращается в « 138 раз.

В заключении подведены итоги и обобщены результаты исследования.

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

Автор выражает искреннюю благодарность научному руководителю, заслуженному деятелю науки и техники РФ, доктору технических наук, профессору Н.И. Червякову, а так же коллективу кафедр высшей алгебры и геометрии и прикладной математики и информатики за помощь, оказанную при написании диссертации, и критические замечания, высказанные при ее обсуждении.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Лобес, Мария Владимировна

Основные результаты диссертационной работы состоят в следующем:

1. Исследована возможность применения классического алгоритма модульного возведения в степень для обработки многоразрядных чисел. Так как он состоит из ряда модульных умножений, то в качестве главной выделена задача разработки эффективного алгоритма для выполнения этой операции. Для ускорения операции модульного умножения выбран алгоритм Монтгомери. Для того чтобы алгоритм Монтгомери подходил для практической реализации, выбрана двоичная система счисления. Но так как алгоритм Монтгомери применяется в ПСС, то, несмотря на преимущества, его применение не дает скачкообразного повышения скорости выполнения операции модульного умножения.

2. Разработан метод расширения системы оснований на основе представления ортогональных базисов в ОПСС, который требует выполнения наибольшее основание, рг - основание по которому определяется остаток, п^ - разрядность основания рд., пг - разрядность основания рг, к количество оснований. На основе разработанного метода расширения системы оснований и известной теоремы теории чисел о делении с нулевым остатком реализована операция масштабирования чисел в СОК.

3. Алгоритм Монтгомери модульного умножения многоразрядных чисел адаптирован для СОК. Это возможно, если использовать ОПСС с тем же набором оснований, что и для СОК.

4. Разработан алгоритм модульного возведения в степень многоразрядных чисел на основе классического алгоритма модульного возведения в степень и алгоритма Монтгомери, адаптированного для СОК. В этом алгоритме результат каждого модульного умножения используется как один или оба (в случае возведения в квадрат) операнда последующего модульного умножения. битовых операций, где р^

5. Выполнено компьютерное моделирование в среде MATLAB и сравнительная оценка разработанных алгоритмов. Сравнительная оценка по общему количеству битовых операций, выполняемых в алгоритмах, в зависимости от разрядностей операндов показала, что основной алгоритм Монтгомери содержит в среднем в 1.2 раза меньше битовых операций в сравнении с алгоритмом Монтгомери, адаптированным для СОК. Однако оценка количества битовых операций определяющих время реализации алгоритмов в зависимости от разрядностей операндов показала, что применение алгоритма Монтгомери, адаптированного для СОК в сравнении с основным алгоритмом Монтгомери дает огромное преимущество по времени выполнения операции МУ, причем оно возрастает прямо пропорционально росту разрядностей операндов. Для 1024-х разрядных операндов время выполнения операции модульного возведения в степень сокращается в ^17 раз.

6. Показано, что метод деления на основе метода спуска Ферма является эффективным, простым в реализации и легко может быть модифицирован на язык кольцевых операций СОК. Однако он обладает тем недостатком, что в случае если делимое а - большое число, а делитель Ь-относительно малое, то для вычисления округленного частного может потребоваться много итераций. В то же время если допустимая ошибка задана не выше 0.1, то достаточно провести всего четыре итерации.

7. Разработан параллельный алгоритм выполнения операции сравнения чисел. Этот алгоритм является универсальным, так как он позволяет различать равенство двух чисел, знак числа, абсолютное значение чисел и переполнение разрядной сетки ЭВМ. Время сравнения при использовании этого метода равно 0([log2 п\+1), где п - число оснований

СОК.

8. Разработан алгоритм деления в СОК, основанный на итерациях Ньютона. В сравнении с методом деления, основанным на спуске Ферма алгоритм обладает несколькими преимуществами. Во-первых, нет необходимости составления, хранения и аппроксимации таблицы приблизительных делителей. Во-вторых, количество итераций для определения величины \M/b\ не зависит от величины делимого. Таким образом, если необходимо разделить несколько чисел на одно и тоже число Ь, то величина \M/b] может быть вычислена один раз. Алгоритм на основе спуска Ферма при делении каждой новой пары чисел а и b выполняется полностью. В-третьих, предложенный алгоритм имеет огромные временные преимущества при делении чисел, разрядность которых значительно отличается. Кроме того, количество итераций может быть уменьшено, если в качестве начального приближения выбрать Z\ — 2 , где

M/2K+l

М/2К

Ъ<

9. Выполнено компьютерное моделирование и сравнительная оценка методов деления спуска Ферма и итераций Ньютона. Которая показала, при условии выполнения только одной итерации они имеют приблизительно одну вычислительную сложность. Если выполняется деление чисел одинаковой разрядности или если их разрядность отличается незначительно, то метод Ферма реализуется быстрее в 1,2 раза. Если разрядности делимого и делителя отличаются значительно, огромное преимущество по времени выполнения деления дает применение метода Ньютона. Например, если делимое 6-ти разрядное, а делитель 1024-х разрядное число, то время реализации разработанного метода и алгоритма деления в сравнении с методом спуска Ферма сокращается в «138 раз.

155

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат физико-математических наук Лобес, Мария Владимировна, 2009 год

1. Акритас А. Основы компьютерной алгебры с приложениями: пер. с англ. М. : Мир, 1994. 544 с.

2. Акушский И. Я., Юдицкий Д. И. Машинная арифметика в остаточных классах. М. : Советское радио, 1968. 440 с.

3. Амербаев В. М. Теоретические основы машинной арифметики. Алма-Ата : Наука, 1976. 324 с.

4. Анохин М. И., Варновский Н. П., Сидельников В. М., Ященко В. В. Криптография в банковском деле. М. : МИФИ, 1997.

5. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М. : Мир, 1979. 536 с.

6. Болотов А. А., Гашков С. Б., Фролов А. Б. Элементарное введение в эллиптическую криптографию. Алгоритмические и алгебраические основы. М.: Комкнига URSS, 2006. 280 с.

7. Бухштаб А. А. Теория чисел. М. : Просвещение, 1966. 384 с.

8. Василенко О. Н. О некоторых свойствах чисел Ферма // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 1998. №5. С. 56-58.

9. Ю.Василенко О. Н. Современные способы проверки простоты чисел // Кибернетический сборник. Новая серия. 1988. Вып. 25. С. 162-187.

10. П.Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003.328 с.

11. Велигоша А. В., Великих С. А. Корректирующие особенности кодов СОК // Тематический сборник ВИПС. 1995. С. 37-38.

12. И.Виноградов И. М. Основы теории чисел. М.: Лань, 2004. 176 с.

13. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. Спб. : БХФ-Петербург, 2002. 608 с.

14. Волков Е. А. Численные методы: учеб. пособие для вузов. М.: Лань, 2004. 248 с.

15. Галушкин А. И., Червяков Н. И. Нейрокомпьютеры в остаточных классах. М.: Радиотехника, 2003. 270 с.

16. Гашков С. Б. Упрощенное обоснование вероятностного теста Миллера-Рабина для проверки простоты чисел // Дискретная математика. 1998. Т. 10(4). С. 35-38.

17. Гашков С. Б., Чубариков В. Н. Арифметика. Алгоритмы. Сложность вычислений : учеб. пособие для вузов. М. : Высшая школа, 2000. 320 с.

18. Грегори Р., Кришномурти Е. Безошибочные вычисления. Методы и приложения. М. : Мир, 1988. 207 с.

19. Гук М. Процессоры Intel. П. : Питер, 1997. 224 с.

20. Гундарь К. Ю., Гундарь А. Ю., Янишевский Д. А. Защита информации в компьютерных системах. К. : Корнейчук, 2000. 152 с.

21. Дадаев Ю. Г. Арифметические коды, исправляющие ошибки. М. : Советское радио, 1968. 168 с.

22. Дадаев Ю. Г. Теория арифметических кодов. М. : Радио и связь, 1981. 272 с.

23. Дженкинс У. К., Этцель X. Особые свойства дополнительных кодов для избыточных систем остаточных классов // ТИИЭР. 1986. Т. 69. № 1. С. 150-151.

24. Диффи У., Хеллман М.Э. Защищенность и криптостойкость: введение в криптографию // ТИИЭР. 1979. Т. 67. №3. С. 71-109.

25. Забродин А. В., Луцкий А. Б., Марбашев К. X., Чернов Л. Г. Численное обследование обтекания летательных аппаратов и их элементов в реальных полетных режимах // Общероссийский научно-технический журнал "Полет". 2001. №7. С. 21-29.

26. Инютин С. А. Модулярные вычисления в сверхбольших компьютерных диапазонах//Известия вузов. Электроника. 2001. №6. С. 34-39.

27. Карацуба А. А., Офман Ю. П. Умножение многоразрядных чисел на автоматах // ДАН СССР. 1961. Т. 145 (2). С. 293-294.

28. Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение. М. : Мир, 2001. 575 с.

29. Клеллан Дж. Применение теории чисел в цифровой обработке сигналов. М. : Радио и связь, 1985. 234 с.

30. Клязник В. В., Ласкеев С. Н. Применение системы остаточных классов для построения цифровых фильтров // Вычислительные средства в технике и системах связи. 1978. №3. С. 75-80.

31. Кнут Д. Искусство программирования. Получисленные алгоритмы. М. и др. : Вильяме, 2004. Ч. 2. 828 с.

32. Коблиц Н. Курс теории чисел и криптографии. М. : ТВП, 2001. 254 с.

33. Коляда А. А. Модулярные структуры конвейерной экспресс-обработки цифровой информации в измерительно-вычислительных системах физического эксперимента : диссерт. на соиск. ученой степени д-ра техн. наук. Минск, 1991.

34. Коляда А. А., Пак И. Т. Модулярные структуры конвейерной обработки цифровой информации. Минск : Университетское, 1992. 256с.

35. Коляда А. А., Селянинов М. Ю., Чернявский А. Ф. Применение модулярной вычислительной технологии в системах защиты информации // Управление защитой информации. 2000. Т.4. №1. С. 2730.

36. Копыткова Л. Б. Математические модели нейросетевой реализации модулярных вычислительных структур для высокоскоростной цифровой фильтрации : диссерт. на соиск. ученой степени канд. физ.-мат. наук. Ставрополь, 2001. 264 с.

37. Коутинхо С. Введение в теорию чисел. Алгоритм RSA : пер. с англ. М.: Постмаркет, 2001. 328 с.

38. Лавриненко И. Н. Деление чисел, представленных в системе остаточных классов // Инфокомуникационные технологии. 2005. Т. 3. №3. С. 6-9.

39. Лавриненко И. Н. Разработка математических методов моделирования модулярного нейропроцессора цифровой обработки сигналов : диссерт. на соиск. ученой степени канд. физ.-мат. наук. Ставрополь, 2005. 207 с.

40. Лобес М. В. Дроби Фарея и некоторые их приложения // Труды участников Международной школы-семинара по геометрии и анализу памяти Н.В.Ефимова (5-11 сентября 2006). Ростов-на-Дону, 2006. С. 195-197.

41. Лобес М. В. Об одном недостатке системы остаточных классов и методах его преодоления // XIV Туполевские чтения : Материалы международной молодежной научной конференции (10-11 ноября 2006). Казань, 2006. Т. IV. С. 18-20.

42. Марковский А. Д. Структура вычислительных систем с точки зрения точности и алгебраических критериев качества вычислений : диссерт. на соиск. ученой степени канд. техн. наук. М., 1979.

43. Мельников В. В. Защита информации в компьютерных системах. М. : Финансы и статистика : Электроинформ, 1997. 368 с.

44. Михлин С. Г. Некоторые вопросы теории погрешностей. Л. : Изд-во Ленинградского университета, 1988. 333 с.

45. Нечаев В. И. Элементы криптографии (Основы теории защиты информации): учеб. пособие для вузов. М.: Высшая школа, 1999. 109 с.

46. Оцоков Ш. А. Нейронный алгоритм расширения диапазона представления результатов безошибочных вычислений // Нейрокомпьютеры : разработка, применение. 2004. №12. С. 33-34.

47. Оцоков Ш. А. Структурная организация нейропроцессора с использованием модели безошибочных вычислений // Нейрокомпьютеры: разработка и применение. 2004. №12. С. 31-32.

48. Прахар К. Распределение простых чисел. М. : Мир, 1977. 134 с.

49. Рибенбойм П. Рекорды простых чисел // Успехи математических наук. 1987. Вып. 5. Т. 42. С. 119-176.

50. Романец Ю. В., Тимофеев П. А., Шаньгин В. Ф. Защита информации в компьютерных системах и сетях. М. : Радио и связь, 1999. 328 с.

51. Саломаа А. Криптография с открытым ключом : пер. с англ. М. : Мир, 1996. 304 с.

52. Свобода А. Развитие вычислительной техники в Чехословакии. Система остаточных классов (СОК) // Кибернетический сборник. 1964. Вып. 8. С. 115-148.

53. Синьков М. В., Губарени Н. М. Непозиционные представления в многомерных числовых системах. Киев : Наукова думка, 1979. 137 с.

54. Соловьев Ю. П., Садовничий В. А. Эллиптические кривые и современные алгоритмы теории чисел. М. : Институт компьютерных исследований, 2003. 92 с.

55. Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. М.: Наука, 1986. 288 с.

56. Тоом A. JL О сложности схемы из функциональных элементов, реализующей умножение целых чисел // ДАН СССР. 1963. Т. 150 (3). С. 496-498.

57. Торгашев В. А. Система остаточных классов и надёжность ЦВМ. М. : Советское радио, 1973. 120 с.

58. Турчак JI. И., Плотников П. В. Основы численных методов. М. : Физматлит, 2002. 300 с.

59. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений : пер. с англ. М. : Мир, 1980. 280с.

60. Червяков Н. И., Кондратов А. В., Лавриненко С. В. Параллельный метод масштабирования модулярных чисел // Нейрокомпьютеры: разработка, применение. 2007. №5. С. 12-20.

61. Червяков Н. И., Копыткова Л. Б., Непретимова Е.Н., Сахнюк П. А., Шапошников А. В. Нейрокомпьютеры в системах обработки сигналов. Коллективная монография. М. : Радиотехника, 2003. 272 с.

62. Червяков Н. И., Копыткова Л. Б., Непретимова Е. Н., Хатамова М. X. Применение вычетов для представления и обработки данных // Вестник Ставропольского государственного университета. 1999. Вып. 18. С. 6472.

63. Червяков Н. И., Лобес М. В. Алгоритм целочисленного деления в системе остаточных классов // Инфокоммуникационные технологии. 2007. Том 5. №4. С. 8-13.

64. Червяков Н. И., Лобес М. В. Аппроксимация функций на основе методов безошибочных вычислений в системе остаточных классов // Вестн. Ставропольского гос. ун-та. Физико-математические науки. 2005. Вып. 43. С. 5-7.

65. Червяков Н. И. Методы и принципы построения модулярных нейрокомпьютеров // «50 лет модулярной арифметике». Юбилейная

66. Международная научно-техническая конференция (В рамках V Международной научно-технической конференции "Электроника и информатика 2005") : сб. науч. тр. (23-25 ноября 2005). 2006. С. 291310.

67. Червяков Н. И. Методы масштабирования модулярных чисел, используемые при цифровой обработке сигналов // Инфокоммуникационные технологии. 2006. Т.4. №3. С. 15-23.

68. Червяков Н. И. Нейронная сеть для расширения кортежа числовой системы вычетов. Патент RU 2256226 опубл. 10.07.2005, Бюл. №19.

69. Червяков Н. И., Сахнюк П. А. Применение нейроматематики для реализации модулярной арифметики при вычислениях в конечных кольцах //Нейрокомпьютер. 1999. № 1. С. 75-84.

70. Червяков Н. И., Сахнюк П. А., Шапошников А. В., Макоха А. Н. Нейрокомпьютеры в остаточных классах : учеб. пособие для вузов. М. : Радиотехника, 2003. 272 с.

71. Червяков Н. И., Сахнюк П. А., Шапошников А. В., Ряднов С. А. Модулярные параллельные вычислительные структуры нейропроцессорных систем. М. : Физматлит, 2002. 288 с.

72. Червяков Н. И., Тынчеров К. Т., Велигоша А. В. Высокоскоростная обработка сигналов с использованием непозиционной арифметики // Радиотехника. 1997. № 10. С. 23-27.

73. Червяков Н. И. Ускоренный алгоритм определения позиционных характеристик и его нейросетевая реализация // Нейрокомпьютеры: разработка и применение. 2001. № 10. С. 19-25.

74. Чернявский А. Ф., Данилевич В. В., Коляда А. А., Селянинов М. Ю. Высокоскоростные методы и системы цифровой обработки информации. Мн. : Белгосуниверситет, 1996. 376 с.

75. Ященко В. В., Варнавский Н. П., Нестеренко Ю. В. Введение в криптографию. М.: МЦНМО ЧеРо, 1998. 276 с.

76. Adleman L., Pomerance С., Rumely R. S. On distinguishing prime numbers from composite numbers // Ann. Math. 1988. Vol. 117. P. 173-206.

77. Alford W. R., Granville A., Pomerance C. There are infinitely many Carmichael numbers // Ann. Math. 1994. Vol. 140. P. 703-722.

78. Banerji D. K., Cheung T. Y., Ganesan V. A high-speed division method in residue arithmetic // Proc. 5-th. Symp. on Computer Arithmetic. 1981. P. 158-164.

79. Bayoumi M. A. Implementation of RNS multiplication in VLSI // Proc. 19-th. Asilomar Conf. Circuits. Syst. and Comput. (6-8 Nov. 1985). Conf. Washington D.C. New-York, 1985. Vol. 4. P. 1457-1460.

80. Bayoumi M. A., Jullien G. A., Miller W. C. AVLSI Implementation of RNS-Based Architectures // International Symposium on Circuits and Systems. Japan, 1985.

81. Bayoumi M. A., Jullien G. A., Miller W. C. Highly parallel architectures for DSP algorithmus using RNS // Proc. IEEE Jnt. Symp. Circuits and Syst. (5-7 June 1985). New-York, 1985. Vol. 3. P. 1395-1398.

82. Bayoumi M. A. VLSI PLA. Structures for residue number systems arithmetic implementation // Proc. IEEE Jnt. Symp. Circuits and Syst. (4-7 May 1987). New-York, 1987. Vol. 1. P. 132-135.

83. Blake I. F., Seroussi G., Smart N. P. Elliptic curves in cryptography. Cambridge University Press, 1999.

84. Bosselaerts A., Govaerts R., Vandewalle J. Comparison of three modular reduction functions // Advances in Cryptology — Crypto'93 ; Douglas R. Stinson, editor. Berlin : Springer-Verlag, 1993. Vol. 773. P. 175-186.

85. Brassard G., Monet S., Zuffelato D. Algorithmes pour I'arithmetique des tres grands entiers // Techniques and Science Informatique. 1986. Vol. 5. P. 89-102.

86. Chren W. A. A new residue number system division algorithm // Computers Math. Appl. 1990. Vol. 19. P. 13-29.

87. Cohen H., Lenstra W. Primality testing and Jacobi sums // Math. Сотр. 1984. Vol. 42 (165). P. 297-330.

88. Comba P. G. Experiments in fast multiplication of integers // Technical Report G320-2158, IBM. Cambridge Scientific Center, 1989.

89. Comba P. G. Exponentiation cryptosystems on IBM PC // IBM Systems. 1990. Vol. 29 (4). P. 29-37.

90. Contini S. Factoring integers with the self initializing quadratic sieve // Master's thesis. University Georgia, 1997.

91. Cook S. A. On the minimum computation time of functions : doctoral thesis. Harvard University, Cambridge. 1966.

92. Crandall R., Pomerance C. Prime numbers: a computational perspective. Springer-Verlag, 2001.

93. Davida G. I., Litov B. Fast parallel arithmetic via modular representaition // SIAM J. Comput. 1991. Vol. 20. P. 756-765.

94. Elkenbracht-Huizing M. An implementation of the number field sieve // Experimental Mathematics. 1996. Vol. 5. P. 231-253.

95. Ernvall R., Metsankyla T. On the p-divisibility of Fermat quotients // Math. Сотр. 1997. Vol. 66 (219). P. 1353-1365.

96. Estevez P. F., Paugam M. E., Puzenat D., Ugarte M. A scalable parallel algorithm for training a hierarchical mixture of neural experts // Parallel Comput. 2002. № 6. P. 861-891.

97. Hans R. Prime Numbers and Computer Methods for Factorization. Stuttgart Boston : Birhhauser, 1985. 452 p.

98. Koblitz N. Algebraic aspects of cryptography. Springer-Verlag, 1998.

99. Koblitz N. Elliptic curve cryptosystems // Math. Сотр. 1987. Vol. 48. P. 203-209.

100. Lenstra A. K., Lenstra H. W., Manasse M. S., Pollard J. M. The number field sieve // Proc. 22-th. ACM Symposium on Theory of Computing. 1990. P. 564-572.

101. Lenstra H. W., Tijdeman R. J. Computational Methods in Number Theory. Amsterdam: Math. Cent., 1982. 198 p.

102. Lu, Mi, Ching, Jen-Shiun. A novel division algorithm for the residue number system // IEEE Trans. Comput. 1992. Vol. 41. P. 1026-1032.

103. Markus A. H., Kaltofen E. Integer division in Residue Number Systems // IEEE Trans. Comput. 1995. Vol. 44(8). P. 983-989.

104. Menezer A., Van Oorschot P. C., Vanstone S. A. Handbook of applied cryptography. CRC Press, 1997.

105. Miller V. Use of elliptic curves in cryptography // Advances in cryptology Cryoto'85. 1986. Vol. 218. P. 417-426.

106. Monier L. Evaluation and comparison of two efficient probabilistic primality testing algorithms // Theor. Comput. Sci. 1980. Vol. 12. P. 97-108.

107. Montgomery P. L. Modular multiplication without trial division // Math. Сотр. 1985. Vol. 44 (170). P. 519-521.

108. Murphy B. A. Modelling the yield of number field sieve polynomials // Proceedings of ANTS -III. 1998. Vol. 1423. P. 137-150.

109. Orton G. A., Peppard L. E., Tovares S. E. New fauit tolerant techniges for residue number systems // IEEE Trans. Comput. 1992. Vol. CAS-41 (11). P. 1453-1464.

110. Plessmann К. A parallel highly modular object-oriented computer architecture // 10 юбилейный Международный Симпозиум по проблемам модулярных информационно-вычислительных систем и сетей (13-18 сентября 1993). М., 1996. С. 97-109.

111. Pollard J. М. Theorems on factorization and primality testing // Proc. Cambridge Phil. Soc. 1974. Vol. 76. P. 521-528.

112. Pomerance C. Factoring // Proc. of Symp. Appl. Math. 1990. Vol. 42. P. 24-47.

113. Pomerance C., Lenstra H. W., Tijdeman R. Analysis and comparision of some integer factoring algorithms // Computational methods in number theory. Amsterdam, 1982. Vol. 1. P. 89-139.

114. Pomerance C., Smith J. W., Tuler R. A pipeline architecture for factoring large integers with the quadratic sieve algorithm // SIAM J. Comput. 1988. Vol. 17(2). P. 387-403.

115. Pomerance C. The number field sieve // Proc. of Symp. Appl. Math. 1994. Vol. 48. P. 465-480.

116. Pomerance C. The quadratic sieve factoring algorithm // Advances in cryptology. Paris, 1985. Vol. 209. P. 169-183.

117. Pradhan D.K. Fault Tolerant Computing. Ney Jersey: Prentice - Hall, 1988. 367 p.

118. Ramirez J., Garsia A., Fernandez P. RNS-FPT nerget architectures for orthogonal DWT // Electron. Lett. 2000. № 4. P. 1198-1199.

119. Ribenboim P. The book of prime number records. Springer Veriag, 1988.

120. Ribenboim P. The new book of prime number records. Springer Veriag, 1996.

121. Rivest R. L., Shamir A., Adleman L. Some options in the design of a residue arithmetic // Communications of ACM. 1978. Vol. 21 (2). P. 120126.

122. Rubin M. Probabilistic algorithms for testing primality // J. Number Theory. 1980. Vol. 12. P. 128-138.

123. Shamir A. A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem // IEEE Trans. Inform. Theory. 1984. Vol. IT-30. P. 699-704.

124. Silverman J. H. The arithmetic of elliptic curves. Springer-Verlag, 1986.

125. Silverman R. D. The multiple polynomial quadratic sieve // Math. Сотр. 1987. Vol. 48 (177). P. 329-339.

126. Solovay R., Strassen V. A fast Monte-carlo test for primality // SI AM J. Comput. 1977. Vol. 6. P. 84-85.

127. Strassen V. Einige Resultate uber Berechnungskomplexitat // Jahresber. Deutsch. Math. Verein, 1976/77. Vol. 78. P. 1-8.

128. Szabo N., Tanaka R. Residue arithmetic and its applications to computertechnology. New-York, 1967. 156. Zhang D. Parallel designs for Chinese remainder conversion // Proc. Int. Conf. Parallel Process (17-21 Aug. 1987). 1987. P. 557 559.