Methods of extracting root with the residues from multi-bit numbers to meet the challenges of asymmetric cryptography

Authors

  • Степан Дмитриевич Винничук The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine
  • Александр Васильевич Корнейко The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine
  • Евгений Васильевич Максименко The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine

DOI:

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

Keywords:

factorization, asymmetric cryptography, square root, division with remainder, diagonal method, method "in the column", modified method, multi-bit numbers

Abstract

Currently asymptotically the fastest factorization methods of multi-bit sequences are methods based on the fundamental ratios of Fermat algorithm. One of the most complex operations in the factorization method of Fermat is a procedure of extracting the square root. Existing methods of extracting the roots are refer to the number of iterative and require the implementation the quite large number the most complex arithmetic operations of multiplication and division. This in turn significantly affects on their temporal assessment. One of the ways of improving the productivity of existing methods for extracting the square root would be using a direct calculation of root without using operations of multiplication or division large numbers. Offered a new method for calculating the square root without using multiplication and division large numbers, which is a modification of the method of extracting roots "in the column." Made a comparative analysis of the described modified method "in a column" with the existing diagonal method (method of Tereshchenko). Offered to use this method in the procedures for analysis of asymmetric cryptographic algorithms

Author Biographies

Степан Дмитриевич Винничук, The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine

Dr. Science in Eng., Head of Science Department of The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine

Александр Васильевич Корнейко, The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine

Ph.D. in Eng., Professor, Scientific Secretary of The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine

Евгений Васильевич Максименко, The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine

Doctoral Student of The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine

References

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

Published

2016-12-12

Issue

Section

Articles