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.

Downloads

Published

2016-12-12

Issue

Vol. 18 No. 4 (2016)

Section

Articles

License

Authors who publish with this journal agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).