NAU Harvester System
Approaches to performance increasing of extended Euclidean algorithm for double precision division on single precision large integers
Наукові журнали Національного Авіаційного Університету
View Archive Info| Field | Value | |
| Title |
Approaches to performance increasing of extended Euclidean algorithm for double precision division on single precision large integers
Подходы к повышению производительности расширенного алгоритма Евклида для деления больших чисел двойной точности на большие числа одинарной точности Підходи для підвищення продуктивності розширеного алгоритму Евкліда для ділення великих чисел подвійної точності на великі числа одинарної точності |
|
| Creator |
Гнатюк, Сергей Александрович; Национальный авиационный университет
Ковтун, Владислав Юрьевич; Национальный авиационный университет Бердник, Оксана Михайловна; Национальный авиационный университет Ковтун, Мария Григорьевна; Национальный авиационный университет |
|
| Subject |
Information Security
division; remainder in division; large integer’s modular reduction; extended Euclidean algorithm UDC 004.051(045) Информационная безопасность деление; остаток деления; большие целые числа; расширенный алгоритм Евклида УДК 004.051(045) Інформаційна безпека ділення; залишок від ділення; великі цілі числа; розширений алгоритм Евкліда УДК 004.051(045) |
|
| Description |
Public key cryptography has significant processing and spatial complexity. In this regard, relevant scientific and technical challenge is to improve the performance of such transformations. In this paper proposed approaches of large integer’s division operation with double precision on single precision based on the Extended Euclidean Algorithm. These approaches include handling non-zero machine words in the most frequently used operations; using an semi-exact comparison of large integer, without for-word comparison; knowledge of the of Bézout equation parameters changing. These approaches are implemented in the modified algorithm, which has been software implemented. In experiments were compared numbers with double binary size dividend and single binary size divider with ratios for various filled and total binary length. Modified algorithm showed higher performance in 1.5-3 times, with dividend and divisor increasing binary length.
Криптографические преобразования с открытым ключом обладают значительной вычислительной и пространственной сложностью. В связи с этим, актуальной научно-технической задачей является повышение производительности таких преобразований. В работе рассматриваются подходы к повышению производительности операции деления больших целых чисел двойной точности на большие числа одинарной точности на основе расширенного алгоритма Евклида. К таким походам относятся: оперирование отличными от нуля машинными словами в наиболее часто использующихся операциях (сдвиги влево и вправо, сложение и вычитание больших чисел); использование приближенного сравнения больших целых чисел, без необходимости пословного сравнения (сравнение номеров старших битов этих чисел); знание закона изменения параметров уравнения Безу (эксплуатируется в предыдущих двух подходах). Предложенные подходы успешно реализованы в модифицированном алгоритме, который был запрограммирован. Для сравнения проводились эксперименты над числами, с условием, что двоичная длина делимого в два раза превосходит двоичную длину делителя для различного соотношения заполненной и общей двоичной длины большого числа. Модифицированный алгоритм показал лучшую производительность в 1,5-3 раза, с ростом двоичной длины делимого и делителя. Криптографічні перетворення з відкритим ключем мають значну обчислювальну та просторову складність. У зв'язку з цим, актуальною науково-технічною задачею є підвищення продуктивності таких перетворень. У роботі розглядаються підходи до підвищення продуктивності операції ділення великих цілих чисел подвійної точності на великі цілі числа одинарної точності на основі розширеного алгоритму Евкліда. До таких походів відносяться: оперування відмінними від нуля машинними словами, які найбільш часто використовуються в операціях порівняння, зсуву вліво і вправо, додавання і віднімання великих чисел; використання наближеного порівняння великих цілих чисел, без необхідності послівного порівняння машинних слів за рахунок порівняння номерів старших бітів цих чисел; знання закону зміни параметрів рівняння Безу – використовується в попередніх двох підходах. Запропоновані підходи успішно реалізовані в модифікованому алгоритмі. Для порівняння проводилися експерименти над числами, за умови, що двійкова довжина діленого в два рази перевищує двійкову довжину дільника для різного співвідношення заповненої та загальної двійкової довжини великого числа. Модифікований алгоритм показав кращу продуктивність в 1,5-3 рази, з ростом двійкової довжини діленого і дільника. |
|
| Publisher |
National Aviation University
|
|
| Contributor |
—
— — |
|
| Date |
2015-04-20
|
|
| Type |
—
— — |
|
| Format |
application/pdf
|
|
| Identifier |
http://jrnl.nau.edu.ua/index.php/Infosecurity/article/view/8308
10.18372/2225-5036.21.8308 |
|
| Source |
Безпека інформації; Том 21, № 1 (2015); 40-51
Безопасность информации; Том 21, № 1 (2015); 40-51 Ukrainian Scientific Journal of Information Security; Том 21, № 1 (2015); 40-51 |
|
| Language |
uk
|
|