Реализация алгоритма Монтгомери в системе остаточных классов на основе эффективного алгоритма расширения системы оснований
- 1 д.т.н., профессор, зав. кафедрой «Прикладная математика и математическое моделирование», Северо-Кавказский федеральный университет (г. Ставрополь)
- 2 аспирант, мл. науч. сотрудник, управление организации научных исследований, Северо-Кавказский федеральный университет (г. Ставрополь)
- 3 к.ф.-м.н., доцент, кафедра «Высшая алгебра и геометрия», Северо-Кавказский федеральный университет (г. Ставрополь)
Аннотация
Рассмотрен метод модулярного возведения в степень, основанный на умножении Монтгомери в системе остаточных классов. Непозиционное умножение Монтгомери позволяет уйти от необходимости применения алгоритмов длинной арифметики. Приведены способы реализации основных арифметических операций для чисел, представленных в длинной арифметике и в системе остаточных классов. Проведенный сравнительный анализ умножения и возведения в степень Монтгомери в традиционной позиционной арифметике и в системе остаточных классов показал высокую эффективность применения модулярной арифметики для решения данной задачи.
Для цитирования
Червяков Н.И., Дерябин М.А., Лавриненко И.Н. Реализация алгоритма Монтгомери в системе остаточных классов на основе эффективного алгоритма расширения системы оснований // Нейрокомпьютеры: разработка, применение. 2014. № 9. С. 37–45.
Список источников
- Montgomery P.L. Modular Multiplication Without Trial Division. Mathematics of Computation. 1985. V. 44. № 170. Р. 519-521.
- Omondi A., Premkumar B. Residue number systems. Theory and Implementation. London. Imperial College Press. 2007. 295 p.
- Червяков Н.И., Евдокимов А.А., Галушкин А.И., Лавриенко И.Н., Лавриенко А.В. Применение искусственных нейронных сетей и системы остаточных классов в криптографии. М.: ФИЗМАТЛИТ. 2012. 280 с.
- Schinianakis D. and Stouraitis T. A RNS Montgomery multiplication architecture // Circuits and Systems (ISCAS). 2011. IEEE International Symposium on, May 2011. Р. 1167-1170.
- Червяков Н.И., Сахнюк П.А., Шапошников А.В., Макоха А.Н.Нейрокомпьютеры в остаточных классах. М.: Радиотехника. 2003. 272 с.
- Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition (2nd ed.). Wiley. 1996.
- Knuth D.E. The Art of Computer Programming. V. 2. Seminumerical Algorithms. Third Edition. Addison-Wesley. 1998.
- Червяков Н.И. Реализация высокоэффективной модулярной цифровой обработки сигналов на основе программируемых логических интегральных схем // Нейрокомпьютеры: разработка и применение. 2006. № 10. С. 24-36.
- Червяков Н.И., Бабенко М.Г., Ляхов П.А., Лавриненко И.Н. Эффективный алгоритм точного определения универсальной позиционной характеристики модулярных чисел и его применение для вычисления основных проблемных операций в системе остаточных классов // Инфокоммуникационные технологии. 2014. Т. 12. № 1. С. 4-18.