Підходи для підвищення продуктивності розширеного алгоритму Евкліда для ділення великих чисел подвійної точності на великі числа одинарної точності
DOI:
https://doi.org/10.18372/2225-5036.21.8308Ключові слова:
ділення, залишок від ділення, великі цілі числа, розширений алгоритм ЕвклідаАнотація
Криптографічні перетворення з відкритим ключем мають значну обчислювальну та просторову складність. У зв'язку з цим, актуальною науково-технічною задачею є підвищення продуктивності таких перетворень. У роботі розглядаються підходи до підвищення продуктивності операції ділення великих цілих чисел подвійної точності на великі цілі числа одинарної точності на основі розширеного алгоритму Евкліда. До таких походів відносяться: оперування відмінними від нуля машинними словами, які найбільш часто використовуються в операціях порівняння, зсуву вліво і вправо, додавання і віднімання великих чисел; використання наближеного порівняння великих цілих чисел, без необхідності послівного порівняння машинних слів за рахунок порівняння номерів старших бітів цих чисел; знання закону зміни параметрів рівняння Безу – використовується в попередніх двох підходах. Запропоновані підходи успішно реалізовані в модифікованому алгоритмі. Для порівняння проводилися експерименти над числами, за умови, що двійкова довжина діленого в два рази перевищує двійкову довжину дільника для різного співвідношення заповненої та загальної двійкової довжини великого числа. Модифікований алгоритм показав кращу продуктивність в 1,5-3 рази, з ростом двійкової довжини діленого і дільника.Посилання
Библиотека многократной точности GMP. URL: https://gmplib.org
Bhattacharya J.: Rudiments of computer science. Kolkata.2010.ISBN: 978-93-80599-02-1
Stehle, P.Zimmermann: A Binary Recursive Gcd Algorithm. Algorithmic Number Theory. LNCS Volume 3076, 2004, pp 411-425. [4] L.Lhote, B.Vallée: Sharp Estimates for the Main Parameters of the Euclid Algorithm. LATIN 2006: Theoretical Informatics. LNCS Volume 3887, 2006, pp 689-702.
V. Dupaquis, A. Venelli: Redundant Modular Reduction Algorithms. Smart Card Research and Advanced Applications. LNCS Volume 7079, 2011, pp 102-114.
Уоррен Генри С. Алгоритмические трюки для программистов: Пер. с анг. – М.: Издательский дом «Вильямс» 2003. – 288 с.: ил. – Парал. тит. англ.
ДСТУ 4145–2002. Інформаційні технології. Криптографічний захист інформації. Цифровий підпис, що ґрунтується на еліптичних кривих. Формування та перевірка. – К.: Держстандарт України, 2002. –40с.
IEEE P1363–2000: Standard Specifications for Public Key Cryptography. – 2000. – 206 p. URL: http://www.ieee.org
P. Barrett. Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor. Proceedings CRYPTO'86, pp. 311-323.
L. Hars. Long Modular Multiplication for Cryptographic Applications.//Cryptographic Hardware and Embedded Systems - CHES 2004.//LNCS Volume 3156, 2004, pp 45-61
Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. - CRC Press; First edition (December 16, 1996), Fifth Printing. - 2001. –780 p.
P. Montgomery. Modular multiplication without trial division. Mathematics of Computation, 44(170):519–521, 1985.
Ковтун В.Ю., Охрименко А.А. Метод повышения производительности операции приве-дения по простому модулю. – Информационные технологи и системы в управлении, образовании, науке: Монография / Под ред.. проф. В.С. Пономаренко. – Х.: Вид-во ТОВ «Щедра садиба плюс», 2014.– С. 204-220.
J.-C. Bajard, S. Duquesne, M. Ercegovac. Combining leak–resistant arithmetic for elliptic curves defined over Fp and RNS representation. Publications Mathématiques de Besançon : Algèbre et Théorie des Nombres, 2013, pp.67-87. URL: http://pmb.univ-fcomte.fr
M. Taschwer. Modular multiplication using special prime moduli. Kommunikationssicherheit im Zeichen des Internet. DuD-Fachbeiträge 2001, pp 346-371.
N. Guillermin. A compressor for secure and high speed modular arithetic. Technical Report 354, Cryptology ePrint Archive (2011). URL: https://eprint.iacr.org/2015/193.pdf.
W. Hasenplaugh, G. Gaubatz, V. Gopal. Fast Modular Reduction. Proceedings of the 18th IEEE Symposium on Computer Arithmetic, pp 225-229 . IEEE Computer Society Washington, DC, USA 2007.
P. Giorgi, L. Imbert, T. Izard. Multipartite Modular Multiplication. RR-11024, 2011, pp.25.
J. Guajardo, R. Blumel, U. Krieger, C. Paar: Efficient Implementation of Elliptic Curve Crypto systems on the TI MSP430x33x Family of Microcontrollers. Public Key Cryptography. LNCS Volume 1992, 2001, pp. 365-382.
D. Hankerson, A. Menezes, and S.A. Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag, 2004. p. 98.
Chae Ho on Lim, Hyo Sun Hwang. Fast Modular Reduction With Precomputation. In Proceedings of Korea-Japan Joint Workshop on Information Security and Cryptology, Lecture.
Z. Cao, R. Wei, Xiao dong Lin. A Fast Modular Reduction Method. IACR Cryptology ePrint Archive, 2014. URL: https://eprint.iacr.org/2014/040.pdf
A. Bosselaers, R Govaerts, J Vandewalle. Comparions of three modular reduction functions. Advances in Cryptology—CRYPTO’93, 175-186.
Jerome A. Solinas. Generalized Mersenne Numbers. http://cacr.uwaterloo.ca/techreports/1999/ corr99-39.pdf
D. E. Knuth. The Art of Computer Programming: Seminumerical Algorithms. Addison-Wesley Publishing Company, Reading, MA, 1981.
H. Wu On Computation of Polynomial Modular Reduction, Tech. Rep., Centre of Applied Cryptographic Research, University of Waterloo, June 2000.
D. Takahashi. A Parallel Algorithm for Multiple-Precision Division by a Single-Precision Integer. Large-Scale Scientific Computing. LNCS Volume 4818, 2008, pp 729-736.
H.-Y. Lo, T.-Y. Chang, M.-C. Lee. Parallel Unidirectional Division Algorithms and Implementations. Journal of the Chinese Institute of Engineers, Taylor & Francis, Volume 24, Issue 4, July 2001, Pages 487-496.
Comba, P. G. Exponentiation cryptosystems on the IBM PC, IBM Systems Journal, Vol. 29, No. 4, December 1990. http://eprint.iacr.org/2012/482.pdf, http://eprint.iacr.org/2012/170.pdf
Карацуба А., Офман Ю. Умножение многозначных чисел на автоматах // Доклады Академии Наук СССР. — 1962. — Т. 145. — № 2.
M. Johnson, B. Phung, T. Shackelford, S. Rueangvivatanakij. Modular Reduction of Large Integers Using Classical, Barrett, Montgomery Algorithms. URL: http://teal.gmu.edu/courses/ECE646/project/reports_2002/IP-1_report.pdf [32] S. Gueron. Enhanced Montgomery Multi-plication. Cryptographic Hardware and Embedded Systems — CHES 2002. Lecture Notes in Computer Science Volume 2523, 2003, pp 46-56.
N. Emmart, C.-C. Weems: Parallel multiple precision division by a single precision divisor. HiPC 2011: 1-9.
Алгоритмы деления Теодора Джебелина URL: https://gmplib.org/manual/Exact-Division.html, https://gmplib.org/manual/References.html#References.
T. Jebelean. Using the Parallel Karatsuba Algorithmfor Long Integer Multiplication and Division. Euro-Par'97 Parallel Processing. LNCS Volume 1300, 1997, pp 1169-1172. URL: http://web-ng.info.uvt.ro/~tudor/Literature-Parallel/97-08.pdf.
K. Hasselström. (2003). Fast Division of Large Integers A Comparison of Algorithm. Master’s Thesis in Computer Science at the School of Computer Science and Engineering, Royal Institute of Technology, February. URL: http://www.treskal.com/kalle/exjobb/original-report.pdf.
Задірака В.К. Комп’ютерна арифметика багаторозрядних чисел // В.К. Задірака, О.С. Олексюк. — К.: 2003. — 264.
Задирака В.К., Кудин А.М. Анализ стойкости криптографических и стегано-графических систем на основе общей теории оптимальных алгоритмов, Journal of Qafgaz University. — N 30. —2010. —С. 49–58.
