Optimization of the Multiply Function of Polynomials for General and Product Forms of the Representation of one Polynomial
The research was carried out and the development of an effective practical algorithm for multiplying ternary polynomials in a ring was performed taking into account their structure. Variants for polynomials with a normal structure with a fixed number of nonzero elements and in the PRODUCT-form in w...
Gespeichert in:
| Datum: | 2019 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Кам'янець-Подільський національний університет імені Івана Огієнка
2019
|
| Online Zugang: | http://mcm-math.kpnu.edu.ua/article/view/174158 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Mathematical and computer modelling. Series: Physical and mathematical sciences |
Institution
Mathematical and computer modelling. Series: Physical and mathematical sciences| Zusammenfassung: | The research was carried out and the development of an effective practical algorithm for multiplying ternary polynomials in a ring was performed taking into account their structure. Variants for polynomials with a normal structure with a fixed number of nonzero elements and in the PRODUCT-form in which the polynomial is the result of the calculation , where and have elements with values «1» and «–1» respectively, were considered. The results of optimization are given using vectorized instructions (AVX2 instructions), parallelization and special tools to minimize and compensate for the use of unbalanced memory. The critical code was written on the assembler under the microprocessor architecture x86-64, which is one of the most widely spread for today. Optimized version’s time values for the parameter sets for 256, 384 and 512 bit classical of security were obtained and a comparison of the efficiency with the polynomial multiplication algorithm, which was proposed in an asymmetric post-quantum cryptosystem on algebraic NTRU Prime grids, was proposed. Testing was done on the Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz processor and on operating system Linux 4.15.0-44-generic #47-Ubuntu SMP x86-64. The results obtained in this paper are extremely relevant. They can be useful for cryptologists and other professionals involved in the development of new, effective cryptographic scheme and protocols for the post-quantum period, because for cryptosystem classes that use the modification in polynomial rings as basic operations, multiplication operation is operation that takes most of the time and requires significant optimization. The biggest advantage of the developed algorithm is the possibility of its parallelization on multiprocessor systems, which is a significant advantage over the algorithm presented in NTRU Prime |
|---|