Разработка методов и алгоритмов модулярных вычислений для задач большой алгоритмической сложности
Диссертация
Выполнено компьютерное моделирование в среде MATLAB и сравнительная оценка разработанных алгоритмов. Сравнительная оценка по общему количеству битовых операций, выполняемых в алгоритмах, в зависимости от разрядностей операндов показала, что основной алгоритм Монтгомери содержит в среднем в 1.2 раза меньше битовых операций в сравнении с алгоритмом Монтгомери, адаптированным для СОК. Однако оценка… Читать ещё >
Содержание
- Основные обозначения и сокращения
- Раздел 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. Компьютерное моделирование и сравнительная оценка разработанного метода и алгоритма деления многоразрядных чисел, представленных в системе остаточных классов
- Выводы по третьему разделу
Список литературы
- Акритас А. Основы компьютерной алгебры с приложениями: пер. с англ. М.: Мир, 1994. 544 с.
- Акушский И. Я., Юдицкий Д. И. Машинная арифметика в остаточных классах. М.: Советское радио, 1968. 440 с.
- Амербаев В. М. Теоретические основы машинной арифметики. Алма-Ата: Наука, 1976. 324 с.
- Анохин М. И., Варновский Н. П., Сидельников В. М., Ященко В. В. Криптография в банковском деле. М.: МИФИ, 1997.
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536 с.
- Болотов А. А., Гашков С. Б., Фролов А. Б. Элементарное введение в эллиптическую криптографию. Алгоритмические и алгебраические основы. М.: Комкнига URSS, 2006. 280 с.
- Бухштаб А. А. Теория чисел. М.: Просвещение, 1966. 384 с.
- Василенко О. Н. О некоторых свойствах чисел Ферма // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 1998. № 5. С. 56−58.
- Ю.Василенко О. Н. Современные способы проверки простоты чисел // Кибернетический сборник. Новая серия. 1988. Вып. 25. С. 162−187.
- П.Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003.328 с.
- Велигоша А. В., Великих С. А. Корректирующие особенности кодов СОК // Тематический сборник ВИПС. 1995. С. 37−38.
- И.Виноградов И. М. Основы теории чисел. М.: Лань, 2004. 176 с.
- Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. Спб.: БХФ-Петербург, 2002. 608 с.
- Волков Е. А. Численные методы: учеб. пособие для вузов. М.: Лань, 2004. 248 с.
- Галушкин А. И., Червяков Н. И. Нейрокомпьютеры в остаточных классах. М.: Радиотехника, 2003. 270 с.
- Гашков С. Б. Упрощенное обоснование вероятностного теста Миллера-Рабина для проверки простоты чисел // Дискретная математика. 1998. Т. 10(4). С. 35−38.
- Гашков С. Б., Чубариков В. Н. Арифметика. Алгоритмы. Сложность вычислений: учеб. пособие для вузов. М.: Высшая школа, 2000. 320 с.
- Грегори Р., Кришномурти Е. Безошибочные вычисления. Методы и приложения. М.: Мир, 1988. 207 с.
- Гук М. Процессоры Intel. П.: Питер, 1997. 224 с.
- Гундарь К. Ю., Гундарь А. Ю., Янишевский Д. А. Защита информации в компьютерных системах. К.: Корнейчук, 2000. 152 с.
- Дадаев Ю. Г. Арифметические коды, исправляющие ошибки. М.: Советское радио, 1968. 168 с.
- Дадаев Ю. Г. Теория арифметических кодов. М.: Радио и связь, 1981. 272 с.
- Дженкинс У. К., Этцель X. Особые свойства дополнительных кодов для избыточных систем остаточных классов // ТИИЭР. 1986. Т. 69. № 1. С. 150−151.
- Диффи У., Хеллман М. Э. Защищенность и криптостойкость: введение в криптографию // ТИИЭР. 1979. Т. 67. № 3. С. 71−109.
- Забродин А. В., Луцкий А. Б., Марбашев К. X., Чернов Л. Г. Численное обследование обтекания летательных аппаратов и их элементов в реальных полетных режимах // Общероссийский научно-технический журнал «Полет». 2001. № 7. С. 21−29.
- Инютин С. А. Модулярные вычисления в сверхбольших компьютерных диапазонах//Известия вузов. Электроника. 2001. № 6. С. 34−39.
- Карацуба А. А., Офман Ю. П. Умножение многоразрядных чисел на автоматах // ДАН СССР. 1961. Т. 145 (2). С. 293−294.
- Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение. М.: Мир, 2001. 575 с.
- Клеллан Дж. Применение теории чисел в цифровой обработке сигналов. М.: Радио и связь, 1985. 234 с.
- Клязник В. В., Ласкеев С. Н. Применение системы остаточных классов для построения цифровых фильтров // Вычислительные средства в технике и системах связи. 1978. № 3. С. 75−80.
- Кнут Д. Искусство программирования. Получисленные алгоритмы. М. и др.: Вильяме, 2004. Ч. 2. 828 с.
- Коблиц Н. Курс теории чисел и криптографии. М.: ТВП, 2001. 254 с.
- Коляда А. А. Модулярные структуры конвейерной экспресс-обработки цифровой информации в измерительно-вычислительных системах физического эксперимента : диссерт. на соиск. ученой степени д-ра техн. наук. Минск, 1991.
- Коляда А. А., Пак И. Т. Модулярные структуры конвейерной обработки цифровой информации. Минск: Университетское, 1992. 256с.
- Коляда А. А., Селянинов М. Ю., Чернявский А. Ф. Применение модулярной вычислительной технологии в системах защиты информации // Управление защитой информации. 2000. Т.4. № 1. С. 2730.
- Копыткова Л. Б. Математические модели нейросетевой реализации модулярных вычислительных структур для высокоскоростной цифровой фильтрации : диссерт. на соиск. ученой степени канд. физ.-мат. наук. Ставрополь, 2001. 264 с.
- Коутинхо С. Введение в теорию чисел. Алгоритм RSA: пер. с англ. М.: Постмаркет, 2001. 328 с.
- Лавриненко И. Н. Деление чисел, представленных в системе остаточных классов // Инфокомуникационные технологии. 2005. Т. 3. № 3. С. 6−9.
- Лавриненко И. Н. Разработка математических методов моделирования модулярного нейропроцессора цифровой обработки сигналов : диссерт. на соиск. ученой степени канд. физ.-мат. наук. Ставрополь, 2005. 207 с.
- Лобес М. В. Дроби Фарея и некоторые их приложения // Труды участников Международной школы-семинара по геометрии и анализу памяти Н. В. Ефимова (5−11 сентября 2006). Ростов-на-Дону, 2006. С. 195−197.
- Лобес М. В. Об одном недостатке системы остаточных классов и методах его преодоления // XIV Туполевские чтения: Материалы международной молодежной научной конференции (10−11 ноября 2006). Казань, 2006. Т. IV. С. 18−20.
- Марковский А. Д. Структура вычислительных систем с точки зрения точности и алгебраических критериев качества вычислений : диссерт. на соиск. ученой степени канд. техн. наук. М., 1979.
- Мельников В. В. Защита информации в компьютерных системах. М.: Финансы и статистика: Электроинформ, 1997. 368 с.
- Михлин С. Г. Некоторые вопросы теории погрешностей. Л.: Изд-во Ленинградского университета, 1988. 333 с.
- Нечаев В. И. Элементы криптографии (Основы теории защиты информации): учеб. пособие для вузов. М.: Высшая школа, 1999. 109 с.
- Оцоков Ш. А. Нейронный алгоритм расширения диапазона представления результатов безошибочных вычислений // Нейрокомпьютеры: разработка, применение. 2004. № 12. С. 33−34.
- Оцоков Ш. А. Структурная организация нейропроцессора с использованием модели безошибочных вычислений // Нейрокомпьютеры: разработка и применение. 2004. № 12. С. 31−32.
- Прахар К. Распределение простых чисел. М.: Мир, 1977. 134 с.
- Рибенбойм П. Рекорды простых чисел // Успехи математических наук. 1987. Вып. 5. Т. 42. С. 119−176.
- Романец Ю. В., Тимофеев П. А., Шаньгин В. Ф. Защита информации в компьютерных системах и сетях. М.: Радио и связь, 1999. 328 с.
- Саломаа А. Криптография с открытым ключом : пер. с англ. М.: Мир, 1996. 304 с.
- Свобода А. Развитие вычислительной техники в Чехословакии. Система остаточных классов (СОК) // Кибернетический сборник. 1964. Вып. 8. С. 115−148.
- Синьков М. В., Губарени Н. М. Непозиционные представления в многомерных числовых системах. Киев: Наукова думка, 1979. 137 с.
- Соловьев Ю. П., Садовничий В. А. Эллиптические кривые и современные алгоритмы теории чисел. М.: Институт компьютерных исследований, 2003. 92 с.
- Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. М.: Наука, 1986. 288 с.
- Тоом A. JL О сложности схемы из функциональных элементов, реализующей умножение целых чисел // ДАН СССР. 1963. Т. 150 (3). С. 496−498.
- Торгашев В. А. Система остаточных классов и надёжность ЦВМ. М.: Советское радио, 1973. 120 с.
- Турчак JI. И., Плотников П. В. Основы численных методов. М.: Физматлит, 2002. 300 с.
- Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений : пер. с англ. М.: Мир, 1980. 280с.
- Червяков Н. И., Кондратов А. В., Лавриненко С. В. Параллельный метод масштабирования модулярных чисел // Нейрокомпьютеры: разработка, применение. 2007. № 5. С. 12−20.
- Червяков Н. И., Копыткова Л. Б., Непретимова Е. Н., Сахнюк П. А., Шапошников А. В. Нейрокомпьютеры в системах обработки сигналов. Коллективная монография. М.: Радиотехника, 2003. 272 с.
- Червяков Н. И., Копыткова Л. Б., Непретимова Е. Н., Хатамова М. X. Применение вычетов для представления и обработки данных // Вестник Ставропольского государственного университета. 1999. Вып. 18. С. 6472.
- Червяков Н. И., Лобес М. В. Алгоритм целочисленного деления в системе остаточных классов // Инфокоммуникационные технологии. 2007. Том 5. № 4. С. 8−13.
- Червяков Н. И., Лобес М. В. Аппроксимация функций на основе методов безошибочных вычислений в системе остаточных классов // Вестн. Ставропольского гос. ун-та. Физико-математические науки. 2005. Вып. 43. С. 5−7.
- Червяков Н. И. Методы и принципы построения модулярных нейрокомпьютеров // «50 лет модулярной арифметике». Юбилейная
- Международная научно-техническая конференция (В рамках V Международной научно-технической конференции «Электроника и информатика 2005»): сб. науч. тр. (23−25 ноября 2005). 2006. С. 291 310.
- Червяков Н. И. Методы масштабирования модулярных чисел, используемые при цифровой обработке сигналов // Инфокоммуникационные технологии. 2006. Т.4. № 3. С. 15−23.
- Червяков Н. И. Нейронная сеть для расширения кортежа числовой системы вычетов. Патент RU 2 256 226 опубл. 10.07.2005, Бюл. № 19.
- Червяков Н. И., Сахнюк П. А. Применение нейроматематики для реализации модулярной арифметики при вычислениях в конечных кольцах //Нейрокомпьютер. 1999. № 1. С. 75−84.
- Червяков Н. И., Сахнюк П. А., Шапошников А. В., Макоха А. Н. Нейрокомпьютеры в остаточных классах : учеб. пособие для вузов. М.: Радиотехника, 2003. 272 с.
- Червяков Н. И., Сахнюк П. А., Шапошников А. В., Ряднов С. А. Модулярные параллельные вычислительные структуры нейропроцессорных систем. М.: Физматлит, 2002. 288 с.
- Червяков Н. И., Тынчеров К. Т., Велигоша А. В. Высокоскоростная обработка сигналов с использованием непозиционной арифметики // Радиотехника. 1997. № 10. С. 23−27.
- Червяков Н. И. Ускоренный алгоритм определения позиционных характеристик и его нейросетевая реализация // Нейрокомпьютеры: разработка и применение. 2001. № 10. С. 19−25.
- Чернявский А. Ф., Данилевич В. В., Коляда А. А., Селянинов М. Ю. Высокоскоростные методы и системы цифровой обработки информации. Мн.: Белгосуниверситет, 1996. 376 с.
- Ященко В. В., Варнавский Н. П., Нестеренко Ю. В. Введение в криптографию. М.: МЦНМО ЧеРо, 1998. 276 с.
- Adleman L., Pomerance С., Rumely R. S. On distinguishing prime numbers from composite numbers // Ann. Math. 1988. Vol. 117. P. 173−206.
- Alford W. R., Granville A., Pomerance C. There are infinitely many Carmichael numbers // Ann. Math. 1994. Vol. 140. P. 703−722.
- 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.
- 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.
- Bayoumi M. A., Jullien G. A., Miller W. C. AVLSI Implementation of RNS-Based Architectures // International Symposium on Circuits and Systems. Japan, 1985.
- 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.
- 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.
- Blake I. F., Seroussi G., Smart N. P. Elliptic curves in cryptography. Cambridge University Press, 1999.
- 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.
- Brassard G., Monet S., Zuffelato D. Algorithmes pour I’arithmetique des tres grands entiers // Techniques and Science Informatique. 1986. Vol. 5. P. 89−102.
- Chren W. A. A new residue number system division algorithm // Computers Math. Appl. 1990. Vol. 19. P. 13−29.
- Cohen H., Lenstra W. Primality testing and Jacobi sums // Math. Сотр. 1984. Vol. 42 (165). P. 297−330.
- Comba P. G. Experiments in fast multiplication of integers // Technical Report G320−2158, IBM. Cambridge Scientific Center, 1989.
- Comba P. G. Exponentiation cryptosystems on IBM PC // IBM Systems. 1990. Vol. 29 (4). P. 29−37.
- Contini S. Factoring integers with the self initializing quadratic sieve // Master’s thesis. University Georgia, 1997.
- Cook S. A. On the minimum computation time of functions: doctoral thesis. Harvard University, Cambridge. 1966.
- Crandall R., Pomerance C. Prime numbers: a computational perspective. Springer-Verlag, 2001.
- Davida G. I., Litov B. Fast parallel arithmetic via modular representaition // SIAM J. Comput. 1991. Vol. 20. P. 756−765.
- Elkenbracht-Huizing M. An implementation of the number field sieve // Experimental Mathematics. 1996. Vol. 5. P. 231−253.
- Ernvall R., Metsankyla T. On the p-divisibility of Fermat quotients // Math. Сотр. 1997. Vol. 66 (219). P. 1353−1365.
- 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.
- Hans R. Prime Numbers and Computer Methods for Factorization. Stuttgart Boston: Birhhauser, 1985. 452 p.
- Koblitz N. Algebraic aspects of cryptography. Springer-Verlag, 1998.
- Koblitz N. Elliptic curve cryptosystems // Math. Сотр. 1987. Vol. 48. P. 203−209.
- 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.
- Lenstra H. W., Tijdeman R. J. Computational Methods in Number Theory. Amsterdam: Math. Cent., 1982. 198 p.
- Lu, Mi, Ching, Jen-Shiun. A novel division algorithm for the residue number system // IEEE Trans. Comput. 1992. Vol. 41. P. 1026−1032.
- Markus A. H., Kaltofen E. Integer division in Residue Number Systems // IEEE Trans. Comput. 1995. Vol. 44(8). P. 983−989.
- Menezer A., Van Oorschot P. C., Vanstone S. A. Handbook of applied cryptography. CRC Press, 1997.
- Miller V. Use of elliptic curves in cryptography // Advances in cryptology Cryoto'85. 1986. Vol. 218. P. 417−426.
- Monier L. Evaluation and comparison of two efficient probabilistic primality testing algorithms // Theor. Comput. Sci. 1980. Vol. 12. P. 97−108.
- Montgomery P. L. Modular multiplication without trial division // Math. Сотр. 1985. Vol. 44 (170). P. 519−521.
- Murphy B. A. Modelling the yield of number field sieve polynomials // Proceedings of ANTS -III. 1998. Vol. 1423. P. 137−150.
- 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.
- Plessmann К. A parallel highly modular object-oriented computer architecture // 10 юбилейный Международный Симпозиум по проблемам модулярных информационно-вычислительных систем и сетей (13−18 сентября 1993). М., 1996. С. 97−109.
- Pollard J. М. Theorems on factorization and primality testing // Proc. Cambridge Phil. Soc. 1974. Vol. 76. P. 521−528.
- Pomerance C. Factoring // Proc. of Symp. Appl. Math. 1990. Vol. 42. P. 24−47.
- 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.
- 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.
- Pomerance C. The number field sieve // Proc. of Symp. Appl. Math. 1994. Vol. 48. P. 465−480.
- Pomerance C. The quadratic sieve factoring algorithm // Advances in cryptology. Paris, 1985. Vol. 209. P. 169−183.
- Pradhan D.K. Fault Tolerant Computing. Ney Jersey: Prentice — Hall, 1988. 367 p.
- Ramirez J., Garsia A., Fernandez P. RNS-FPT nerget architectures for orthogonal DWT // Electron. Lett. 2000. № 4. P. 1198−1199.
- Ribenboim P. The book of prime number records. Springer Veriag, 1988.
- Ribenboim P. The new book of prime number records. Springer Veriag, 1996.
- Rivest R. L., Shamir A., Adleman L. Some options in the design of a residue arithmetic // Communications of ACM. 1978. Vol. 21 (2). P. 120 126.
- Rubin M. Probabilistic algorithms for testing primality // J. Number Theory. 1980. Vol. 12. P. 128−138.
- Shamir A. A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem // IEEE Trans. Inform. Theory. 1984. Vol. IT-30. P. 699−704.
- Silverman J. H. The arithmetic of elliptic curves. Springer-Verlag, 1986.
- Silverman R. D. The multiple polynomial quadratic sieve // Math. Сотр. 1987. Vol. 48 (177). P. 329−339.
- Solovay R., Strassen V. A fast Monte-carlo test for primality // SI AM J. Comput. 1977. Vol. 6. P. 84−85.
- Strassen V. Einige Resultate uber Berechnungskomplexitat // Jahresber. Deutsch. Math. Verein, 1976/77. Vol. 78. P. 1−8.
- 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.