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

Лобес Мария Владимировна

РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ МОДУЛЯРНЫХ ВЫЧИСЛЕНИЙ ДЛЯ ЗАДАЧ

_БОЛЬШОЙ АЛГОРИТМИЧЕСКОЙ

СЛОЖНОСТИ

05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

2 8 май 2009

Ставрополь - 2009

003471251

Работа выполнена на кафедре высшей алгебры и геометрии ГОУ ВПО «Ставропольский государственный университет»

Научный руководитель: Официальные оппоненты:

Ведущая организация:

доктор технических наук, профессор Червяков Николай Иванович

доктор физико-математических наук, профессор Наац Игорь Эдуардович

доктор технических наук, профессор Мочалов Валерий Петрович

Белгородский государственный университет (г. Белгород)

Защита состоится «11» июня 2009 г. в 15 часов 00 минут на заседании совета по защите докторских и кандидатских диссертаций Д 212.256.08 при ГОУ ВПО «Ставропольский государственный университет» по адресу: 355009, г.Ставрополь, ул. Пушкина 1, ауд. 214.

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

Автореферат разослан « % » мая 2009 г.

Ученый секретарь

совета по защите докторских

и кандидатских диссертаций Д 212256.08 /

канд. физ.-мат. наук, доцент ^/Ьм^кШ^-— Копыткова Л.Б.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Выполнено компьютерное моделирование в среде МАТЬАВ, на основе которого проведена сравнительная оценка эффективности предло-

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

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

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

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

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

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

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

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

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

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

Результат модульного умножения после применения алгоритма получается в виде Sm+] = ABR~l mod М . Чтобы привести его к нормальному

виду нужно применить преобразование Монтгомери.

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

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

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

С Конец )

Рисунок 1- Алгоритм Монтгомери для двоичной системы счисления

Пусть - основания системы остаточных классов и

Я - Р\ ■ Рг ■ — ■ Рк ' Диапазон.

Алгоритм Монтгомери, адаптированный для системы остаточных классов, вычисляет значение S так что

S з ABR~X то&М , где S < 2М . На каждом этапе алгоритма вычисляется цифра обобщенной позицион-

1

ной системы q.

Sj+arbi |

Pi

Pi ~mi

и цифры представления в сис-

Р>

теме остаточных классов s, =

Sj +а, -bj +(/, -т\ -|1/Л|

При этом

значения ,sJ вычисляются таким образом, что они являются кратными Ру. Следовательно, если основания системы являются взаимно про-

стыми числами, то деление

на р. заменяется умножением на

мультипликативную обратную величину.

( Начало ) у

ввод: А и В - операнды модульного умножения; ' р1,р1г..,р1 -основанияеистемыостаточных классов, Л = А ■ А '■■■'Р/,—диапазон Л = а, + дг ■р1 +о5 • р, ■ р2 + ... + 0, • р[ ■ р2 •...■ - представшие в обобщенной погыционнк системесчислениц

- представлвшев систгмеостаточных

классов,

М - модуль, (М,И)=1,0 < М < Л/3 • л;

М =(т1,т1г..,тк\т< =|м| ,/е{|,2 г..,к}~ представлвше в системе

оста то чных классов

5:=0

. Г~

_I...

Определение остатка расшиением системы оснований

/ ВывоЭгв / 1 ч/--

( Конец )

Рисунок 2 - Алгоритм Монтгомери, адаптированный для системы остаточных классов Тогда го алгоритма имеем

5 =

+а2В+д2М

/р1+'-.+ак_]В+дк^М

IРк~\ • (О

Г *

После приведения к общему знаменателю и группировки равенство (1) может быть преобразовано следующим образом

+-+акР\-Рк-\\в + {ч\ +-ЯгР1+"+ЧкР1-Рк-1)-м)

или 5= — -(а-В+(2-м). Следовательно, так как £> • М шос! М = 0, то Р.

Б = ЛВ{ГХ тосШ . Кроме этого на каждом этапе алгоритма с помощью операции расширения системы оснований вычисляется остаток si по основанию р,.

Для определения цифры по основанию р: пред ложен метод расширения системы оснований на основе представления ортогональных базисов в обобщенной позиционной системе. Его суть состоит в следующем. Пусть Р1,Р2,—,Р„ - основания системы остаточных классов, Р - р\ ■ р2 ■...■ рп -диапазон, Вх,В2,...,Вп - ортогональные базисы, т1,т2,—,тп - их веса, которые определяются из сравнения «,/'/р, = 1 то(1 р,, причем Я, = т1 ■ Р/р1 , г = 1, и . Добавим основание р„+\, тогда Р = р„+\-Р - новый диапазон, В1,В2,...,Вп+1 -ортогональные базисы и т\, т2,..., от„+1 - их веса, причем В, - т, ■ р/р, ,

/ = 1, п +1. Представим ортогональные базисы В1 в обобщенной позиционной системе счисления, тогда

В^Ьл+Ьарх+Ъвр1р2+...+Ьыр1р2...рп, /,/ = 1,и. (2)

Любое число а из диапазона [о, р) в обобщенной позиционной системе можно представить в виде

а = ап+1Р1Р2-Рп +апР1Р2 -Рп-\ +- + агр1р1+а2р1+а]. (3) Коэффициенты числа а , представленного в обобщенной позиционной системе могут быть определены по формуле

л+1 _

а, = гшх!/;, , (4)

'=1,7=1 _

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

В формуле (4) цифры а1 получаются суммированием по модулю р1

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

Пусть число а имело представление (а^,а2,...,ап) по основаниям р), р2,..., рп ■ Тогда после добавления нового основания рп+1 его новое представ-

лениея = (а|= ал+1)' где а0+) =|а| - неизвестная цифра по новому

РпА

основанию. Для определения этой цифры используется формула (4). При этом будут получены цифры а1,а2,—,ап и выражение для цифры а„+].

Если число а будет лежать в первоначальном диапазоне [(), р), то в обобщенной позиционной системе счисления ап+х = 0.

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

На основе алгоритма Монтгомери, адаптированного для системы ос-_таточных_классов_и_классического„алгоритма_модульного_возведения в степень разработан алгоритм модульного возведения в степень многоразрядных чисел. В этом алгоритме результат каждого модульного умножения используется как один или оба (в случае возведения в квадрат) операнда последующего модульного умножения.

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

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

Оценка общего количества битовых операций, выполняемых в алгоритмах в зависимости от разрядностей операндов (табл.1) показала, что основной алгоритм Монтгомери содержит в среднем в 1.2 раза меньше битовых операций в сравнении с алгоритмом Монтгомери, адаптированным для системы остаточных классов (СОК).

Таблица 1 - Оценка общего количества битовых операций алгоритмов

Разрядность операндов Общее количество битовых операций, выполняемых в алгоритме 1 °м )

Монтгомери (.Ом) Монтгомери + СОК (ои+с)

8 208 310 1,5

16 800 1128 1,4

32 3136 3896 1,2

64 12416 13640 и

128 49408 54928 1,1

256 197120 217964 1,1

512 787456 856304 1,1

1024 3147776 3374377 1,1

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

Таблица 2 - Оценка количества битовых операций, определяющих время реализации алгоритмов__

Разрядность операндов Количество бит( ляющих время эвых операций опреде-реализации алгоритма ( ом \

Монтгомери (Ом) Монтгомери + СОК (0'м+с) и Л/

8 208 256 0,8

16 800 739 1,1

32 3136 1658 1,9

64 12416 3839 3,2

128 49408 10852 4,6

256 197120 31167 6,3

512 787456 89572 8,8

1024 3147776 269236 11,7

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

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

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

Метод спуска Ферма заключается в выполнении следующей последовательности шагов:

1. Перевод делителя Ь в обобщенную позиционную систему, то есть пред-

п п-1

ставление его в виде b = 6„+i + ¿„]~]а +...+b3pip2+b2pl+t>iai, где

i=1 м

Pi, pi,..., p„ - основания системы и определение наиболее значимой ненулевой цифры Ьр этого представления (на основе представления ортогональных базисов в обобщенной позиционной системе).

2. Определение приблизительного делителя Ъ =<2 рург-■■■■ Рк-\ > где к - номер наиболее значимой ненулевой цифры представления делителя в ОПСС, Q определяется из таблицы (хранимой в памяти) при условии, что

Ьр =Ьк и 6, ф 0 или 6, = 0, г = к +1,п, /е 7 .

3. Вычисляется начальное приближение частного 171=[ао/б], где а0-делимое и значения О] = а0 - Ъ ■ .

4. Цикл из г итераций, в процессе которых вычисляются значения д, =[а;_]/б] и а, = а,^ при ¡'=2,3,..,/-. Выполнение итераций продолжается пока не будет выполнено условие <7, = 0, либо до а1 = 0.

5. Определяется частное от деления Ч = Я\'Я2'—'1г~\+ч'г ■> где _ дг, ес.т____дг ? и аг = 0_______

<7>

1, если qr = 0и ar_-¡ > b для любых b Ф 0 . О, во всех остальных случаях

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

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

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

Для его реализации необходимо использование расширенной системы остаточных классов, которая определяет вычислительный диапазон для промежуточных значений, равный приблизительно квадрату от соответствующего нормального диапазона. Для этого система оснований выбирается специальным образом. Пусть í/], <72 ,•■•, Я2п' взаимно простые числа, для которых

1<91 <92 <-<Я2п-\ <Я2п' (5)

где neZ, п> 1. Разобьем эти числа на две группы следующим образом

Pl=9b />2=9з, Рз=<15>......>Рп=Ч2п-\ (6)

и

Рп+1 = 42. Рп+2 = Я4 » Рл+3 = Я6 ........ Р2п =42п- (7)

Тогда р\,р2Р2П- основания расширенной системы, а р\,р2,—,рп -основания базовой системы, , рп+2 Р2п - основания расширения базо-

2 я « _ 2л

вой системы до расширенной; Р = 11 р,- , Л/ = | | р, , М = /з, -

1=1 ¡=1 /=и+1

соответствующие диапазоны.

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

Для вычисления обратной величины \м Iь] используется метод итераций Ньютона. Применяя схему итераций Ньютона

(8)

для /(?,)= M|zi -Ъ и /'(г,)=-Л/Д2 , получаем следующую рекурсию

2м = 2г + ((^• г,- -6• г}Ум)= 21 ■ (2М-b■zi)/М . В системе остаточных классов используется только целочисленное деление, поэтому окончательная версия примет вид

2,41 -

-22,-

Ъ22

М

(9)

М

В качестве начального приближения можно выбрать 2| = 2 и продолжать вычисления до тех пор, пока выполняется условие гм Ф . При = вычисления прекращаются, и проверяется условие

¡ = М-Ь-гм-Ь<0. (10)

Если это условие верное, то обратная величина будет равна \_М 1Ь\- гм , иначе \_М/Ь\ = гм +1.

Второй этап деления а на Ь состоит в нахождении частного из равенства ц = [(а • 2М )/М _|.

Если g = r-b>0, то \а/ь\=ц + \, иначе \ а/Ь\-д. Для того, чтобы обосновать сходимость процесса нахождения обратной величины [л//б] , нужно сначала доказать вспомогательное неравенство

ь/м-(м/ь-г,)2 <м/ь-гм <ь/м(м/ь-/ч)2 +1. (П)

Оно следует из определения оператора (наименьшее целое число превосходящее X , то есть X < [х] < X+1):

М/Ь - = М/Ь - 22, + \ы}/м\ М/Ь - 22, + ¿7,2 /м +1 = = Ь/м{м/Ь-7.$ +\

Аналогично доказывается левая часть выражения (11).

Алгоритм нахождения обратной величины [л1/ь\ конечен для любого

значения Ь, удовлетворяющего условию I <Ь<М .

При = 2 и Ь>\ъМ/а\ итерации останавливаются на значениях 22 = 2Ъ - 0.

При условии [м/2]<Ь<\зм/4\ алгоритм останавливается на

Z2=Zi—\.

При условии \<Ь< \_М/2\< Л//2 методом математической индукции можно показать, что Л///>-2, > 0: для / = I => М/Ь-2у>М/М/2-2 = 0; для />1 с учетом левой части выражения (И)

м/ь-гм >ь/м{м/ь-2,)2 >о,___________

Следовательно, выполняются неравенства Ь'А, < М , —- < 1,

М

—'- ■ 2, < 2,. Из которых следует справедливость оценки М

ZM = 2 Z,-

22}

^2Z,-Z,=Z,. (12)

М

Это означает, что последовательность монотонно возрастает и условие ос-

тановки алгоритма Z/+1 = 2Z, -

ЬУ-1

м

будет в итоге достигало.

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

На первом этапе алгоритма деления условие остановки алгоритма zM = Zj. Два целых числа а и Ъ представленные в системе остаточных классов равны тогда и только тогда, когда равны их соответствующие компоненты: а, = Ь,. При реализации в ЭВМ проверка на равенство для каждой компоненты может быть выполнена в двоичном коде с помощью логической операции AND.

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

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

может быть выполнено на основе представления ортогональных базисов в обобщенной позиционной системе. При этом если выбрать основания, удовлетворяющие условию Р| > р2 > •■■ > р„ , рп=2, тогда старший коэффициент представления разности в обобщенной позиционной системе ап может принимать два значения: 0 и 1. При этом ап = 0 - число положительное, а„ = 1 - число отрицательное.

Разработанный параллельный алгоритм сравнения чисел по величине является универсальным, так как он позволяет различать равенство двух чисел, знак числа, абсолютное значение чисел и переполнение разрядной сетки ЭВМ. Этот алгоритм является полностью параллельным и позволяет выполняй, операцию сравнения путем выполнения модульных операций по модулю р,, что выгодно отличает его от других алгоритмов. Необходимо отметить, что время сравнения чисел, представленных в системе остаточных классов, на основе разработанного метода, соизмеримо с выполнением этой операции в позиционной системе счисления.

Для того чтобы ускорить процесс нахождения обратной величины М /Ь нужно в качестве начального приближения вместо значения 2] =2

выбрать ближайшую степень двойки. То есть выбрать начальное значение в виде 2| = 2к, где К определяется из условия

Проведена сравнительная оценка разработанного метода деления на основе итераций Ньютона с методом деления на основе спуска Ферма.

Так как методы Ферма и Ньютона являются итерационными, то их сравнение проводилось по общему количеству выполняемых итераций.

Сравнительная оценка общего количества итераций выполняемых в алгоритмах Ферма и Ньютона приведена на рисунках 3 и 4.

Ферма

жтГ

15 аи"

10 ^ а"

'Ч, аз 1 2 1 2 2ц е* Рисунок 3 - Оценка количества итераций методов Ферма и Ньютона в зависимости от разрядности делимого

Эта оценка проводилась на основе компьютерного моделирования в среде МАТЬАВ. В первом случае (рис. 3) значение делителя фиксировалось, а значение делимого менялось.

Рисунок 4 - Оценка количества итераций методов Ферма и Ньютона в зависимости от разрядности делителя

Во втором случае (рис. 4) наоборот неизменным оставалось значение делимого, делитель принимал различные значения.

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

В таблице 3 приведена оценка количества итераций методов Ферма и Ньютона доя случая, когда делимое является фиксированным ( Ь = 37 ), а разрядность

делимого изменяется (28 : 21024 ). Оценка выполнена с помощью программ, разработанных в среде МАТЬАВ, реализующих методы Ферма и Ньютона

Таблица 3 — Оценка количества итераций методов деления Ферма и Ньютона

Разрядность делимого Количество итераций метода * Г/Ы

Ферма (Н) Ньютона(Ы)

8 5 6 0,8

16 12 6 2

32 25 6 4.2

64 53 6 8,8

128 105 6 17,5

256 203 6 33,8

512 411 6 68,5

1024 829 6 138,2

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Выполнено компьютерное моделирование в среде МАТЪАВ, на основе которого проведена сравнительная оценка предложенных методов и алгоритмов модульного умножения и модульного возведения в степень. Оценка показала, что их применение позволяет значительно сократить время реализации соответствующих операций. Например, если операндами являются 1024-х разрядные числа, то применение предложенных методов и алгоритмов сокращает время выполнения операции модульного умножения в 11,7 раз, операции модульного возведения в степень в 17,5 раз.

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

5. Выполнено компьютерное моделирование в среде МАТЬАВ и проведена сравнительная оценка разработанного алгоритма деления многоразрядных чисел на основе итераций Ньютона с алгоритмом деления на основе спуска Ферма. Оценка показала, что если выполняется деление чисел одинаковой разрядности или если их разрядность отличается незначительно, то метод Ферма реализуется быстрее. Если разрядности делимого и делителя отличаются значительно, то огромное преимущество по количеству выполняемых итераций дает применение метода Ньютона. Так если делимое 6-ти разрядное, а делитель 1024-х разрядное число, то время реализации в сравнении с методом спуска Ферма сокращается примерно в 138 раз.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

-Статьи в ведущих рецензируемых, научных журналах, из перечня.

журналов, рекомендованных ВАК Минобрнауки России для защиты докторских и кандидатских диссертаций:

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

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

Статьи в сборниках по итогам проведения международных конференций:

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

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

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

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

7. Червяков Н. И., Лобес М. В. Модульное возведение в степень // Инфокоммуникационные технологии в науке, производстве и образовании : Материалы Третьей Международной научно-технической конференции (1-5 мая 2008). Ставрополь : изд-во СевКавГТУ, 2008. Ч. Ш. С. 204-210.

8. Червяков H. И., Лобес M. В. Реализация метода безошибочных вычислений на базе дробей Фарея // Материалы Восьмой Международной научно-технической конференции «Проблемы техники и технологии телекоммуникаций» и Пятой Международной научно-технической конференции «Оптические технологии в телекоммуникациях» (26-28 ноября 2007). Уфа: Изд-во УГАТУ, 2007. С. 142-144.

9. Червяков Н. И., Лобес М. В. Целочисленное деление в системе остаточных классов // Инфокоммуникационные технологии в науке, производстве и образовании : Материалы Третьей Международной научно-технической конференции (1-5 мая 2008). Ставрополь: Изд-во СевКавГТУ, 2008. Часть III. С. 198-204.

Статьи в сборниках по итогам проведения региональных конференций:

10. Лобес М. В. Задачи, определяющие необходимость перехода к безошибочным вычислениям // Физико-математические науки на современном этапе развития Ставропольского государственного университета: Материалы 51-й научно-методической конференции преподавателей и студентов Ставропольского государственного университета «Университетская наука - региону» (3-24 апреля 2006). Ставрополь, 2006. С. 105-108.

11. Лобес М. В. Криптографические методы и средства защиты информации. Значение и возможности криптосистемы с открытым ключом RSA // Научно-инновационные достижения ФМФ в области физико-математических и технических дисциплин : Материалы 53-й научно-методической конференции преподавателей и студентов Ставропольского государственного университета «Университетская наука - региону» (8-30 апреля 2008). Ставрополь, 2008. С. 237-240.

12. Лобес М. В. Направления усовершенствования высокопроизводительных ЭВМ // Физико-математические науки на современном этапе развития Ставропольского государственного университета : Материалы 51-й научно-методической конференции преподавателей и студентов Ставропольского государственного университета «Университетская наука - региону» (3-24 апреля 2006). Ставрополь, 2006. С. 108-111.

Подписано в печать 5.05.09 Формат 60x84 1/16 Усл.печ.л. 1,22 Уч.-шд.л. 1,06 Бумага офсетная_Тираж 100 экз._Заказ 153

Отпечатано в Издательско-полиграфическом комплексе Ставропольского государственного университета. 355009, Ставрополь, ул.Пушкина, 1.

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

Введение.

Раздел 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

ЗАКЛЮЧЕНИЕ

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.