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

Степан Дмитриевич Винничук, Александр Васильевич Корнейко, Евгений Васильевич Максименко

Анотація


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

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


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

Посилання


Корнейко А.В. Анализ известных вычислительных методов факторизации многоразрядных чисел / А.В. Корнейко, А.В. Жилин // Моделювання та інформаційні технології: Збірник наукових праць. – Вип. 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.


Повний текст: PDF

Посилання

  • Поки немає зовнішніх посилань.


ISSN 2410-7840 (Online), ISSN 2221-5212 (Print)

Ліцензія Creative Commons
Цей твір ліцензовано за ліцензією Creative Commons Із зазначенням авторства - Некомерційна - Без похідних творів 3.0 Неадаптована

РИНЦ SSM WorldCat BASE Національна бібліотека ім. Вернадського Науково-технічна бібліотека НАУ Ulrich's Periodicals Directory

Ulrich's Periodicals Directory