Арифметика з відкладеним переносом для цілих чисел
DOI:
https://doi.org/10.18372/2410-7840.16.6932Ключові слова:
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.
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:- Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
- Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
- Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
