Методи обчислення кореня із залишком з багаторозрядних чисел для рішення задач асиметричної криптографії

Автор(и)

  • Степан Дмитриевич Винничук Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
  • Александр Васильевич Корнейко Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
  • Евгений Васильевич Максименко Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України

DOI:

https://doi.org/10.18372/2410-7840.18.11095

Ключові слова:

факторизація, асиметрична криптографія, квадратний корінь, ділення з залишком, діагональний метод, метод «в стовпчик», модифікований метод, багаторозрядні числа

Анотація

На даний момент асимптотично найшвидшими методами факторизації багаторозрядних послідовностей є методи, побудовані на фундаментальних співвідношеннях алгоритму Ферма. Однією з найбільш складних операцій в методі факторизації Ферма є процедура обчислення квадратного кореня. Існуючі методи обчислення коренів відносяться до числа ітераційних і вимагають виконання досить великої кількості трудомістких арифметичних операцій множення і ділення, що в свою чергу суттєво впливає на їх тимчасову оцінку. Одним із способів підвищення продуктивності існуючих методів обчислення квадратних коренів може бути використання процедури прямого визначення кореня, що не використовує операції множення або ділення великих чисел. Запропоновано новий метод обчислення квадратного кореня без використання операцій множення і ділення великих чисел, що є модифікацією методу вилучення кореня «в стовпчик». Проведено порівняльний аналіз описаного модифікованого методу «в стовпчик» з існуючим діагональним методом (методом Терещенко). Пропонується використання даного методу в процедурах аналізу асиметричних криптоалгоритмів

Біографії авторів

Степан Дмитриевич Винничук, Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України

доктор технічних наук, с.н.с., завідувач відділу Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України

Александр Васильевич Корнейко, Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України

кандидат технічних наук, професор, в.о. вченого секретаря Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України

Евгений Васильевич Максименко, Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України

аспірант Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України

Посилання

Корнейко А.В. Анализ известных вычислительных методов факторизации многоразрядных чисел / А.В. Корнейко, А.В. Жилин // Моделювання та інформаційні технології: Збірник наукових праць. – Вип. 61. – К.: ІПМЕ, 2011. – С. 3-13

Ишмухаметов Ш.Т. Методы факторизации натуральных чисел: учебное пособие / Ш.Т. Ишмухаметов. – Казань: Казан. ун-т, 2011. – 190 с.

Нестеренко А.Ю. Теоретико-числовые методы в криптографии: учебное пособие / А.Ю. Нестеренко. – М.: МГИЭМ, 2012. – 224 с.

Горбенко І.Д. Прикладна криптологія : монографія / І.Д. Горбенко, Ю.І. Горбенко. Видання 2-ге. – Харків: Форт, 2012. – 878 с.

Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. – 2-е. – М.: Вильямс, 2005. – 1296 с.

Дональд Э. Кнут Искусство программирования. Том 2. – М.: Мир, 1979. – 727 c.

Square Root algorithm for C. [Электронный ресурс]. – Режим доступа: http://www. codeproject.com/Articles/570700/ SquareplusRootplusalgorithmplusforplusC.

Best Square Root Method. Algorithm. Function. [Электронный ресурс]. – Режим доступа: http://www.codeproject.com/Articles/69941/ Best-Square-Root-Method-Algorithm-Function-Precisi.

Терещенко А.Н. Быстрое вычисление квадратного и кубического корней без использования операций умножения и деления // Искусственный интеллект. – 2006. – Вып. 3. – С. 670-680.

##submission.downloads##

Опубліковано

2016-12-12

Номер

Том 18 № 4 (2016)

Розділ

Статті

Ліцензія

Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:

  1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.

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

  3. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).