Арифметика з відкладеним переносом для цілих чисел

Андрей Александрович Охрименко

Анотація


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

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


DCF представлення; відкладене перенесення; цілі числа; цілочисельна арифметика; програмна реалізація; розпаралелювання

Посилання


Умножения целых чисел с использованием отложеного переноса для криптосистем с открытым ключом / В.Ю.Ковтун, А.А.Охрименко [и др.] // Информационные технологи и системы в управлении, образовании, науке: Монография / Под ред. проф. В.С. Пономаренко. – Х.: Цифрова друкарня №1. – 2013. – С. 69-82.

Richard P. Brent and Paul Zimmermann. Modern Computer Arithmetic // Cambridge Monographs on Computational and Applied Mathematics (No. 18), Cambridge University Press, November 2010. 239 p.

Brumnik R., Kovtun V., Okhrimenko A. and Kavun S. Techniques For Performance Increasing Of Integer Multiplications In Cryptographic Application. – Mathematical Problems in Engineering. – vol. 2014. – 2014. – p.7. – doi:10.1155/2014/863617

Cohen H. and Frey G., editors. Handbook of Elliptic and Hyperelliptic Curve Cryptography. Discrete Mathematics and its Applications. – Chapman & Hall/CRC. – 2006. – p. 848.

Hankerson D., Menezes A., and Vanstone S.A. Guide to Elliptic Curve Cryptography, Springer- Verlag, – 2004. – p. 332.

Marc Joyel, Christophe Tymen. Compact Encoding of Non-Adjacent Forms with Applications to Elliptic Curve Cryptography // Published In K.Kim, Ed., Public Key Cryptography, vol. 1992 of LNCS, – Springer-Verlag. – 2001. – pp. 353-364.

Intel® 64 and IA-32 Architectures Optimization Reference Manual, available at: http://www.intel.com/content/www/us/en/architecture-andtechnology/64-ia-32-architectures-optimizationmanual.html (accessed 15 May 2014)

Knuth, Donald E. The Art of Computer Programming. Third edn. Vol.2 : Seminumerical Algorithms. - Addison-Wesley. – 1998. – 762p.

Patrick Longa, Ali Miri New Multibase Non- Adjacent Form Scalar Multiplication and its Application to Elliptic Curve Cryptosystems (extended version) // Cryptological ePrint Archive. – Report 2008/52. – 2008. – p.39. – URL: http://eprint.iacr.org/2008/052.pdf

Franco P. Preparata. On the Representation of Integers in Nonadjacent Form // SIAM Journal on Applied Mathematics. – Vol. 21. – No. 4. – 1971. – pp. 630-635.

Yanik T., Savas E., and Koc C. K. Incomplete Reduction in Modular Arithmetic. – IEEE Proceedings – Computers and Digital Techniques. – 149(2). – 2002. – pp. 46-52.


Повний текст: 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