Методи та засоби підвищення ефективності реалізації обчислювальних операцій у скінченних полях

Скорочена інформація про документ
dc.contributor.authorОнай, Микола Володимирович
dc.date.accessioned2017-11-03T13:12:58Z
dc.date.available2017-11-03T13:12:58Z
dc.date.issued2017
dc.description.abstractenThe thesis is devoted to the problem of increasing the efficiency of computations in finite fields. The proposed solution to this problem is to develop methods and means for performing operations on elements of finite fields GF(p) or GF(2m). The analysis of the current state of the development of methods of operations in finite fields is carried out and priority points are highlighted. It is best to classify them on the basis of the distinguished features. The classification of the methods of performing the most computational expensive operations (the calculation of the multiplicative inverse element and the exponentiation) in the finite fields was performed. It enables to conduct thorough research and form the directions of development for these methods. The method of high-speed implementation of additive and multiplicative operations on elements of GF(2m) and corresponding hardware structures for its implemen-tation are proposed. Additive operations include addition and subtraction. Multiplica-tive operations include multiplication, exponentiation, multiplicative inverse element calculation, and division. The research has shown that table storage of elements of the GF(2m) in their polynomial and power representation ensures the maximum speed and versatility of the arithmetic logic unit. With the use of long integer operands, the sparse formation of the table of field elements is proposed. It enables reducing the memory consumption for its storage in several times. The algorithms for converting power representa-tion into polynomial one and polynomial representation in power one with the use of a sparse table are constructed. The developed method provides a 15% increase in per-formance comparing with the existing method. Experimental researches were performed to determine the best sparse ratio of the elements table of the GF(2m). It has been discovered that for a value of m < 21, the best sparse ratio is equal to 8. For the exponentiation, it is desirable to increase the sparse ratio to 16. The algorithms for converting the power representation into polynomial one and polynomial representation into power one with the use of a sparse table are devel-oped. The modification of the method of exponentiation elements GF(p) with sliding window and the corresponding hardware structures for its implementation are pro-posed. The difference from the existing methods is that when forming a precomputation table, the exponents are prime numbers, and when analyzing the binary represen-tation of the exponent, blocks of bits forming a prime number are allocated. To achieve high performance, when constructing a precomputation table, it is recom-mended to use pre-calculated additive chains to minimize the number of multiplica-tion operations, which allows each of the following table items to be obtained in one or two modular multiplication operations. With the help of the developed computational model, it has been found out that the proposed modification of the exponentiation method of elements GF(p) with a sliding window provides an increase in speed by 7-9%. The modification of the ex-ponentiation method of elements GF(p) with a sliding window can be used in elliptic-curve cryptography to improve the time characteristics of the scalar multiplication on elliptic curve. The model of the computational process of execution of operations in finite fields is developed, which enables comparison of methods on the basis of given sets of input data and the execution of the optimal choice of parameters and forms of presentation of operands, which ensure an increase in speed for the implementation of computing operations on the FPGA. The research methodologies of new methods hardware implementation of calculations in Galois fields are developed on the basis of the proposed model. Simulation in the development environment of Xilinx ISE and using the Mentor Graphics Precision software showed that the developed hardware structures are characterized by minimal hardware complexity and high performance. A Verilog code generator for FPGA synthesis of a ROM element containing a sparse table of GF(2m) field elements in a polynomial and power representation is created which automatically generates a Verilog code for a given irreducible polyno-mial and a sparse ratio of the table. The architecture and the command system of the specialized Galois processor, focused on operations in finite fields, has been developed. The Galois processor can be used in a universal computing system as a coprocessor, complementing the com-mand system of the central processor unit, or as a special device based on the FPGA, which increases the efficiency of processing information in real time in comparison with the universal computing means. The architecture feature of the developed processor is that a user can change the arithmetic logic unit (ALU) to make the transition to the GF(p) or GF(2m) without changing the processor interface. The research of the developed Galois processor has been carried out, which showed that this processor provides an increase in the productivity of computing by 27% compared with the universal computing means. A program model of the Galois processor is constructed, which allows the user to create software of arbitrary complexity in Assembler of the Galois processor.en
dc.description.abstractruВ диссертационной работе решена актуальная научно-прикладная задача – повышение производительности систем цифровой обработки данных и крипто-графических преобразований, обеспечение помехоустойчивости хранения и передачи данных за счет создания эффективных технических средств для выполнения вычислений в конечных полях путем структурно-логической оптимизации архитектур аппаратных средств, реализующих процессы выполнения операций в полях Галуа. Предложен метод выполнения операций над элементами поля GF(2m). Особенностью данного метода, в отличие от существующих, является применение табличного хранения элементов поля в многочленном и степенном их представлении с возможностью разреженного формирования таблицы элементов поля, что уменьшает затраты памяти для ее хранения. Разработанный метод обеспечивает прирост производительности на 15% по сравнению с существующим методом. Предложена модификация метода возведения в степень элементов поля GF(p) со скользящим окном, обеспечивающая прирост быстродействия на 7-9%. Спроектирован на ПЛИС фирмы Xilinx процессор Галуа, ориентированный на выполнение операций в конечных полях вида GF(p) и GF(2m). Предложена программистская модель процессора Галуа, позволяющая разрабатывать программное обеспечение любой сложности на языке ассемблера процессора Галуа.ru
dc.description.abstractukУ дисертаційній роботі вирішено актуальну науково-прикладну задачу – підвищення продуктивності систем цифрової обробки даних та криптографічних перетворень, забезпечення завадостійкості зберігання і передачі даних за рахунок створення ефективних технічних засобів для виконання обчислень у скінченних полях шляхом структурно-логічної оптимізації архітектур апаратних засобів, що реалізують процеси виконання операцій у полях Галуа. Запропоновано метод виконання операцій над елементами поля GF(2m). Особливістю даного методу, на відміну від існуючих, є застосування табличного зберігання елементів поля у многочленному та степеневому їх поданні з можливістю розрідженого формування таблиці елементів поля, що зменшує витрати пам’яті для її зберігання. Розроблений метод забезпечує зростання швидкодії на 15% порівняно з існуючим методом. Запропоновано модифікацію методу піднесення до степеня елементів поля GF(p) з ковзним вікном, яка забезпечує приріст швидкодії на 7-9 %. Спроектовано на ПЛІС фірми Xilinx процесор Галуа, що орієнтований на виконання операцій у скінченних полях виду GF(p) та GF(2m). Запропоновано програмістську модель процесора Галуа, яка дозволяє розробляти програмне забезпечення довільної складності мовою Асемблера процесора Галуа.uk
dc.format.pagerange28 с.uk
dc.identifier.citationОнай, М. В. Методи та засоби підвищення ефективності реалізації обчислювальних операцій у скінченних полях : автореф. дис. … канд. техн. наук. : 05.13.05 – комп'ютерні системи та компоненти / Онай Микола Володимирович. – Київ, 2017. – 28 с.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/20969
dc.language.isoukuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.subjectполе Галуаuk
dc.subjectскінченне полеuk
dc.subjectмультиплікативно обернений елементuk
dc.subjectпіднесення до степеняuk
dc.subjectнезвідний многочленuk
dc.subjectАсемблер Галуаuk
dc.subjectпроцесор Галуаuk
dc.subjectПЛІСuk
dc.subjectGalois fielden
dc.subjectfinite fielden
dc.subjectmultiplicative inverse elementen
dc.subjectexponentiationen
dc.subjectirreducible polynomialen
dc.subjectGalois Assembleren
dc.subjectGalois processoren
dc.subjectFPGAen
dc.subjectполе Галуаru
dc.subjectконечное полеru
dc.subjectмультипликативно обратный элементru
dc.subjectвозведение в степеньru
dc.subjectнеприводимый многочленru
dc.subjectАссемблер Галуаru
dc.subjectпроцессор Галуаru
dc.subjectПЛИСru
dc.subject.udc004.31:004.27](043.3)uk
dc.titleМетоди та засоби підвищення ефективності реалізації обчислювальних операцій у скінченних поляхuk
dc.typeThesisuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
aref_Onai.pdf
Розмір:
614.72 KB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
7.74 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Автореферати (ПЗКС)
Автореферати (вільний доступ)