WWW.PDF.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Разные материалы
 

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

Авдошин С.М., Савельева А.А.

Алгоритм решения систем линейных уравнений

в кольцах вычетов

Разработан эффективный алгоритм решения систем линейных

уравнений в кольцах вычетов [1], эквивалентный по сложности известному

алгоритму решения систем в полях Галуа ([2], [4]). Приведены результаты

сравнительного анализа предложенного алгоритма и существующих аналогов

([3], [10], [8]) на основе асимптотической оценки их временной сложности.

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

Введение Объектом исследования данной работы являются методы решения систем линейных уравнений в кольцах вычетов. Такие системы возникают в алгоритмах факторизации и дискретного логарифмирования (см., например, метод Диксона, алгоритм Копперсмита-Одлыжко-Шреппеля «COS» и алгоритм решета числового поля в [3]).

Частным случаем колец вычетов являются поля Галуа, т.е. кольца вычетов по модулю простых чисел. Методы решения систем в таких полях известны (см., например, метод Гаусса (последовательного исключения) в [2, с.89], [4, с.42]). Модификацией метода Гаусса является метод Жордана. Однако для решения систем линейных уравнений в кольцах вычетов эти методы, вообще говоря, неприменимы.

Проиллюстрируем сказанное.

Рассмотрим систему линейных уравнений:

26 x + 3 y = 4 (1) 9 x + 34 y = 1 в поле Галуа Z 37и в кольце вычетов Z 36.



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

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

Обратный элемент по модулю p можно найти как решение уравнения:

ax 1(mod p) (2) Для его вычисления используется расширенный алгоритм Евклида (см.

[7, с. 744], [10, с.227]). На рис.1 приведено описание этого алгоритма. Если a и p - взаимно простые числа, т.е. НОД ( a, p ) = 1 = a x + p y, то коэффициент Безу x является решением уравнения ( 2 ) ; в противном случае уравнение ( 2 ) не имеет решения и элемент a необратим в кольце Z p.

Как показано в [7, с.743], время работы алгоритма Евклида при вычислении НОД ( a, b), где a b 0, составляет O (log b). Тогда сложность операции вычисления обратного элемента в кольце Z p можно оценить как O (log p ). Метод Жордана с учетом алгоритма Евклида имеет временную сложность O ( n ( n m + log p ) ) для системы n уравнений с m неизвестными в Z p.

Евклид( a, b)

1. d x y a

–  –  –

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

В монографии [3] задача сводится к решению систем линейных уравнений над полями Галуа. Пусть m

–  –  –

Рис.2 [5, с.127]). Тогда приведенному выше следствию соответствующие системы уравнений являются равносильными. Что и требовалось доказать.

–  –  –

1. Авдошин С.М., Савельева А.А. Свидетельство об официальной регистрации программы для ЭВМ № 2005612258: «Программа решения систем линейных уравнений в кольцах вычетов». Зарегистрировано в Реестре программ для ЭВМ 02.09.2005.





2. Ван дер Варден Б.Л. Алгебра. - М.: Наука, 1976. - 623 с.

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

МЦНМО, 2004. - 328 с.

4. Гантмахер Ф.Р. Теория матриц. Гостехиздат, 1953. - 576 с.

5. Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра: Учебник. В 2-х т. Т. I М.: Гелиос АРВ, 2003. - 336с.

6. Джекобсон Н. Теория колец (Перевод с английского Н. Я. Виленкина). М.:

Государственное издательство иностранной литературы, 1947. - 287 с.

7. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.:

МЦНМО, 1999. - 960 с.

8. Кузнецов М.И., Бурланков Д.Е., Чирков А.Ю., Яковлев В.А.

Компьютерная алгебра: Учебник. Нижегородский Государственный Университет им. Н.И. Лобачевского.

http://www.itlab.unn.ru/archive/docs/coaBook.pdf, 2002. - 102 с.

9. Курош А.Г. Теория групп (Издание третье, дополненное). М.: «НАУКА», Главная редакция физико-математической литературы, 1967. - 648 с.

10. Ноден П., Китте К. Алгебраическая алгоритмика. Пер. с франц. - М.: Мир,

Похожие работы:

«Пояснительная записка Рабочая программа по изобразительному искусству для VII класса составлена на основе: Примерной программы основного общего образования по изобразительному искусству (приложение к письму Департамента государственной политики в образовании Министерства образования и науки РФ от 7 июля 2005 г. N 03-1263 «О...»

«МОЗГ ЧЕЛОВЕКА СВЕРХВОЗМОЖНОСТИ И ЗАПРЕТЫ Академик Н. Бехтерева Humans.ru Обучение online МАГИЯ ТВОРЧЕСТВА Возможности сознания и гениальность МОЗГ ЧЕЛОВЕКА СВЕРХВОЗМОЖНОСТИ И ЗАПРЕТЫ Академик Н. Бехтерева МОЗГ ЧЕЛОВЕКА СВЕРХВОЗМОЖНОСТИ И ЗАПРЕТЫ Крамольные идеи, изложенные в этой статье, они и ес...»

«УДК: 800 ЭМОЦИОНАЛЬНО-ВОЛЕВАЯ СФЕРА ЯЗЫКА: ИМПЕРАТИВ И ВОКАТИВ В СВЕТЕ ПРАГМАТИЧЕСКОГО АСПЕКТА. Давыденко О.В. ассистент кафедры английского языка e-mail: s_siyanije@mail.ru Курский государственный университет Прагматический подход к анализу единиц эмоционально –волевого компонента речевой коммуникации позволяет выявить ряд...»

«Приложение 3 ТО У Роспотребнадзора по Нижегородской области в Лысковском, _ Воротынском, Княгининском, Спасском районах_ 24 марта 20 14 г. (место составления акта) (дата составления акта) 11 Ч. 00 мин_ (вр...»

«РУБИНА Наталия Викторовна Диагностика развития изобретательского мышления на основе методов ТРИЗ. Диссертационная работа на соискание звания Мастер ТРИЗ Научный руководитель: Мастер ТРИЗ Федосов Юрий Игорьевич Санкт-Петербург 2013 Диагностика ра...»

«Теория. Методология © 2003 г. Б.С. СИВИРИНОВ СОЦИАЛЬНАЯ РАЦИОНАЛЬНОСТЬ КАК КОМПОНЕНТ СОЦИАЛЬНОЙ ПЕРСПЕКТИВЫ СИВИРИНОВ Борис Сергеевич кандидат философских наук, доцент Сибирской академии государственной службы (Новосибирск). Социальная рациональность, как компонент социаль...»

«Ф.Равдоникас. Логарифмический счёт в традиционной нотации // Серия Проблемы музыкознания, вып. 2; Аспекты теоретического музыкознания. Сборник научных трудов, Л., 1989, с. 44-50. Наша музыкальная офрография основана на пифагоровой шкале, от любой из ступе...»

«Лекция №1 Понятие информации Учебные вопросы: 1. Возникновение и развитие теории информации 2. Понятие информации и этапы ее обращения Теория информации является одним из курсов при подготовке инженеров, специализирующихся в области автоматизированных систем управления и обработ...»

«РЕ П О ЗИ ТО РИ Й БГ П У ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Учебно-методический комплекс по учебной дисциплине «Прикладные исследования в социальной сфере» предназначен для научно-методического обеспечения профессион...»

«Свердловская областная научная библиотека Отдел краеведческой литературы Литература о Свердловской области 1998 год Июль Сентябрь I кагеринбур! ^ 0 ', Свердловская областная научная библиотека Отдел краеведческ...»








 
2017 www.pdf.knigi-x.ru - «Бесплатная электронная библиотека - разные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.