NAU Harvester System
Performance increasing methods for binary field inversion
Наукові журнали Національного Авіаційного Університету
View Archive Info| Field | Value | |
| Title |
Performance increasing methods for binary field inversion
Методы повышения производительности операции инвертирования в двоичном поле Методи підвищення продуктивності операції інвертування у двійковому полі |
|
| Creator |
Ковтун, Владислав Юрійович; Национальный авиационный университет
Булах, Марія Григорівна; Национальный авиационный университет |
|
| Subject |
Information Security
asymmetric cryptography transformation; multiplicative inversion; Extended Euclidean Algorithm; binary field; polynomial UDC 004.051/056(045) Информационная безопасность асимметрические криптографические преобразования; мультипликативное инвертирование; расширенный алгоритм Эвклида; двоичное поле; полином УДК 004.051/056(045) Інформаційна безпека асиметричні криптографічні перетворення; мультиплікативне інвертування; розширений алгоритм Евкліда; двійкове поле; поліном УДК 004.051/056(045) |
|
| Description |
Authors propose several methods for increasing performance of multiplicative inversion algorithm in binary fields based on Extended Euclidean Algorithm. First method is based on Extended Euclidean Algorithm specific: either invariant polynomial is a same or swaps with invariant polynomial u. Thus, it does not necessary to compute degree of polynomial . Next method is based on «next fit element» in polynomial degree computation: on each iteration of Extended Euclidean Algorithm execution, degree of invariant polynomial decreases at list one. On next iteration Extended Euclidean Algorithm degree searches from where it left off the previous time. Proposed methods allow to increase performance of software implementation of inversion in binary field for 32-bit architectures on 15-20%.
Авторы предлагают ряд методов к увеличению производительности алгоритма мультипликативного инвертирования в двоичном поле на основе расширенного алгоритма Эвклида (РАЭ). Первый метод основывается на специфике самого РАЭ: инвариантный полином , либо остается без изменений, либо обменивается содержимым с инвариантным полиномом u, это позволяет избежать необходимости вычисления степени полинома . Второй метод основан на поиске «следующего подходящего индекса» при вычислении степени полинома, т.к. степень инвариантного полинома уменьшается хотя бы на 1, то при дальнейшем вычисление степени полинома, можно учитывать текущее значение. Основываясь на втором методе, при модификации инвариантов, авторы предлагают использовать в вычислениях лишь значимые слагаемые, учитывая текущие степени пар полиномов и . Предложенные методы позволяют увеличить производительность программной реализации инвертирования, для 32-х разрядных платформ, на 15-20%. Автори пропонують ряд методів збільшення продуктивності алгоритму мультиплікативного інвертування у двійковому полі на основі розширеного алгоритму Евкліда. Перший метод ґрунтується на специфіці самого розширеного алгоритму Евкліда: інваріантний поліном або залишається без змін, або обмінюється вмістом з інваріантним поліномом u, це дозволяє уникнути необхідності обчислення ступеня полінома. Наступний метод заснований на методі «наступного підходящого індексу» при обчисленні ступеня полінома: враховуючи той факт, що в процесі роботи розширеного алгоритму Евкліда, ступінь інваріантного полінома зменшується хоча б на 1, то при подальшому обчисленні ступеня полінома можна враховувати поточне значення ступеня. Запропоновані методи дозволяють збільшити продуктивність програмної реалізації інвертування для 32-х розрядних платформ на 15-20%. |
|
| Publisher |
National Aviation University
|
|
| Contributor |
—
— — |
|
| Date |
2014-06-11
|
|
| Type |
—
— — |
|
| Format |
application/pdf
|
|
| Identifier |
http://jrnl.nau.edu.ua/index.php/Infosecurity/article/view/6575
10.18372/2225-5036.20.6575 |
|
| Source |
Безпека інформації; Том 20, № 1 (2014); 55-61
Безопасность информации; Том 20, № 1 (2014); 55-61 Ukrainian Scientific Journal of Information Security; Том 20, № 1 (2014); 55-61 |
|
| Language |
uk
|
|