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...
Saved in:
| Date: | 2019 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Кам'янець-Подільський національний університет імені Івана Огієнка
2019
|
| Online Access: | http://mcm-math.kpnu.edu.ua/article/view/174158 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Mathematical and computer modelling. Series: Physical and mathematical sciences |
Institution
Mathematical and computer modelling. Series: Physical and mathematical sciences| _version_ | 1856543229826039808 |
|---|---|
| author | Качко, Олена Григорівна Кандій, Сергій Олегович Острянська, Єлізавета Вадимівна |
| author_facet | Качко, Олена Григорівна Кандій, Сергій Олегович Острянська, Єлізавета Вадимівна |
| author_sort | Качко, Олена Григорівна |
| baseUrl_str | |
| collection | OJS |
| datestamp_date | 2020-01-20T08:43:19Z |
| description | 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 |
| first_indexed | 2025-07-17T10:43:11Z |
| format | Article |
| id | mcm-mathkpnueduua-article-174158 |
| institution | Mathematical and computer modelling. Series: Physical and mathematical sciences |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:43:11Z |
| publishDate | 2019 |
| publisher | Кам'янець-Подільський національний університет імені Івана Огієнка |
| record_format | ojs |
| spelling | mcm-mathkpnueduua-article-1741582020-01-20T08:43:19Z Optimization of the Multiply Function of Polynomials for General and Product Forms of the Representation of one Polynomial Оптимізація функції множення поліномів для звичайної та product форми задання одного з поліномів Качко, Олена Григорівна Кандій, Сергій Олегович Острянська, Єлізавета Вадимівна 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 У роботі проведено дослідження та виконано розробку ефективного алгоритму множення тернарного полінома у кільці з урахуванням його структури. Розглядаються варіанти для поліномів із звичайною структурою з фіксованою кількістю ненульових елементів «1» («–1») та у PRODUCT-формі, у якій поліном є результатом обчислення , де та мають відповідно елементів із значеннями «1» та «–1». Приводяться результати оптимізації за допомогою векторизованих наборів інструкцій (а саме, набір інструкцій AVX2), розпаралелювання та спеціальних засобів для мінімізації та компенсування використання не вирівняної пам’яті. Критичний код написано на асемблері під мікропроцесорну архітектуру x86-64, яка є однією з найрозповсюдженіших на сьогоднішній день. Отримані часові показники оптимізованої реалізації алгоритму для наборів параметрів для 256, 384 та 512 біт класичної безпеки та зроблено порівняння ефективності з алгоритмом множення поліномів, що був запропонований у асиметричній постквантовій криптосистемі на алгебраїчних решітках NTRU Prime. Тестування здійснено на процесорі Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz на операційній системі Linux 4.15.0-44-generic #47-Ubuntu SMP x86-64. Результати, що отримані, на наш погляд — надзвичайно актуальні. Вони можуть бути корисними для криптологів та інших фахівців, що займаються розробкою нових, ефективних криптографічних алгоритмів та протоколів для постквантового періоду. Це пояснюється тим, що для класів криптосистем, у яких використовуються перетворення у кільцях поліномів, як базові операції, а саме операцій множення, займає найбільше часу та тому потребує значної оптимізації. Значна перевага розробленого алгоритму — можливість його розпаралелювання на багатопроцесорних системах, що є значною перевагою порівняно з алгоритмом, що представлені в NTRU Prime. Кам'янець-Подільський національний університет імені Івана Огієнка 2019-02-12 Article Article Рецензована Стаття application/pdf http://mcm-math.kpnu.edu.ua/article/view/174158 10.32626/2308-5878.2019-19.28-34 Mathematical and computer modelling. Series: Physical and mathematical sciences; 2019: Mathematical and computer modelling. Series: Physical and mathematical sciences. Issue 19; 28-34 Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки; 2019: Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки. Випуск 19; 28-34 2308-5878 10.32626/2308-5878.2019-19 uk http://mcm-math.kpnu.edu.ua/article/view/174158/174124 Авторське право (c) 2021 Олена Григорівна Качко, Сергій Олегович Кандій, Єлізавета Вадимівна Острянська |
| spellingShingle | Качко, Олена Григорівна Кандій, Сергій Олегович Острянська, Єлізавета Вадимівна Optimization of the Multiply Function of Polynomials for General and Product Forms of the Representation of one Polynomial |
| title | Optimization of the Multiply Function of Polynomials for General and Product Forms of the Representation of one Polynomial |
| title_alt | Оптимізація функції множення поліномів для звичайної та product форми задання одного з поліномів |
| title_full | Optimization of the Multiply Function of Polynomials for General and Product Forms of the Representation of one Polynomial |
| title_fullStr | Optimization of the Multiply Function of Polynomials for General and Product Forms of the Representation of one Polynomial |
| title_full_unstemmed | Optimization of the Multiply Function of Polynomials for General and Product Forms of the Representation of one Polynomial |
| title_short | Optimization of the Multiply Function of Polynomials for General and Product Forms of the Representation of one Polynomial |
| title_sort | optimization of the multiply function of polynomials for general and product forms of the representation of one polynomial |
| url | http://mcm-math.kpnu.edu.ua/article/view/174158 |
| work_keys_str_mv | AT kačkoolenagrigorívna optimizationofthemultiplyfunctionofpolynomialsforgeneralandproductformsoftherepresentationofonepolynomial AT kandíjsergíjolegovič optimizationofthemultiplyfunctionofpolynomialsforgeneralandproductformsoftherepresentationofonepolynomial AT ostrânsʹkaêlízavetavadimívna optimizationofthemultiplyfunctionofpolynomialsforgeneralandproductformsoftherepresentationofonepolynomial AT kačkoolenagrigorívna optimízacíâfunkcíímnožennâpolínomívdlâzvičajnoítaproductformizadannâodnogozpolínomív AT kandíjsergíjolegovič optimízacíâfunkcíímnožennâpolínomívdlâzvičajnoítaproductformizadannâodnogozpolínomív AT ostrânsʹkaêlízavetavadimívna optimízacíâfunkcíímnožennâpolínomívdlâzvičajnoítaproductformizadannâodnogozpolínomív |