350 руб
Журнал «Нейрокомпьютеры: разработка, применение» №9 за 2014 г.
Статья в номере:
Реализация алгоритма Монтгомери в системе остаточных классов на основе эффективного алгоритма расширения системы оснований
Ключевые слова: модулярная арифметика арифметика произвольной точности система остаточных классов обобщенная позиционная система счисления метод умножения Монтгомери модульное возведение в степень
Авторы:
Н.И. Червяков - д.т.н., профессор, зав. кафедрой «Прикладная математика и математическое моделирование», Северо-Кавказский федеральный университет (г. Ставрополь). E-mail: k-fmf-primath@stavsu.ru М.А. Дерябин - аспирант, мл. науч. сотрудник, управление организации научных исследований, Северо-Кавказский федеральный университет (г. Ставрополь). E-mail: maxim.deryabin@gmail.com И.Н. Лавриненко - к.ф.-м.н., доцент, кафедра «Высшая алгебра и геометрия», Северо-Кавказский федеральный университет (г. Ставрополь). E-mail: k-fmf-primath@stavsu.ru
Аннотация:
Рассмотрен метод модулярного возведения в степень, основанный на умножении Монтгомери в системе остаточных классов. Непозиционное умножение Монтгомери позволяет уйти от необходимости применения алгоритмов длинной арифметики. Приведены способы реализации основных арифметических операций для чисел, представленных в длинной арифметике и в системе остаточных классов. Проведенный сравнительный анализ умножения и возведения в степень Монтгомери в традиционной позиционной арифметике и в системе остаточных классов показал высокую эффективность применения модулярной арифметики для решения данной задачи.
Страницы: 37-45
Список источников

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