Обчислення дивiзорiв на гiперелiптичнiй кривiй та їхнє прикладне застосування на мовi Python
Loading...
Date
2020
Authors
Бойко, Денис
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
В роботi розглядаються гiперелiптичнi кривi роду g > 1, дивiзори на них та їхнє прикладне
застосування на мовi програмування Python. Наведено основнi необхiднi означення та вiдомi властивостi про гiперелiптичнi кривi, представлено поняття полiномiальної функцiї, переведення
його у єдину форму, а також поняття рацiональної функцiї, норми, степеня та спряженого
до многочлена. Цi факти потрiбнi для обчислення порядку точок функцiй, тим самим i для
швидкого та ефективного обчислення дивiзорiв. Продемонстровано означення дивiзора на гiперелiптичнiй кривiй, наведено основнi вiдомi властивостi дивiзора. Наведено приклад обчислення
дивiзора полiномiальної функцiї, описано зведенi та напiвзведенi дивiзори, доведено теореми про
iснування такого напiвзведеного дивiзора, котрий не є єдиним, а також iснування єдиного зведеного дивiзора, який еквiвалентний початковому. Зокрема, напiвзведений дивiзор може бути
зображений у виглядi НСД дивiзорiв двох полiномiальних функцiй. Також продемонстрований
факт, що кожний зведений дивiзор можна єдиним способом зобразити у виглядi пари многочленiв [a(x), b(x)], це i є зображенням Мамфорда, наведено декiлька прикладiв його обчислення.
Описано алгоритм Кантора обчислення суми двох дивiзорiв, його «композицiйної» частини,
за допомогою якого утворюється напiвзведений дивiзор (який не є єдиним), а також редукцiйної частини, котра зводить напiвзведений дивiзор у єдиний зведений. Описано особливий випадок
"композицiйної" частини: подвоєння дивiзора, що суттєво зменшує час роботи алгоритму. Доведено коректнiсть алгоритмiв, наведено приклади застосувань.
Основним результатом роботи є розробка обчислення дивiзора полiномiальної функцiї, зображення Мамфорда, алгоритму Кантора у виглядi програмного коду на мовi програмування
Python.
Таким чином, метою роботи є демонстрацiя можливостi легко та ефективно використовувати описанi алгоритми для подальшої роботи з дивiзорами на гiперелiптичнiй кривiй, в тому
числi для розробки криптосистеми, цифрового пiдпису на основi гiперелiптичних кривих, атаки
на таку криптосистему.
The paper studies hyperelliptic curves of the genus g > 1, divisors on them and their applications in Python programming language. The basic necessary definitions and known properties of hyperelliptic curves are demonstrated, as well as the notion of polynomial function, its representation in unique form, also the notion of rational function, norm, degree and conjugate to a polynomial are presented. These facts are needed to calculate the order of points of desirable functions, and thus to quickly and eciently calculate divisors. The definition of a divisor on a hyperelliptic curve is shown, and the main known properties of a divisor are given. There are also an example of calculating a divisor of a polynomial function, reduced and semi-reduced divisors are described, theorem of the existence of such a not unique semi-reduced divisor, and theorem of the existence of a unique reduced divisor, which is equivalent to the initial one, are proved. In particular, a semi-reduced divisor can be represented as an GCD of divisors of two polynomial functions. It is also demonstrated that each reduced divisor can be represented in unique form by pair of polynomials [a(x), b(x)], which is called Mumford representation, and several examples of its representation calculation are given. There are shown Cantor’s algorithms for calculating the sum of two divisors: its compositional part, by means of which a not unique semireduced divisor is formed, and the reduction part, which gives us a unique reduced divisor. In particular, special case of the compositional part of Cantor’s algorithm, doubling of the divisor, is described: it significantly reduces algorithm time complexity. Also the correctness of the algorithms are proved, examples of applications are given. The main result of the work is the implementation of the divisor calculation of a polynomial function, its Mumford representation, and Cantor’s algorithm in Python programming language. Thus, the aim of the work is to demonstrate the possibility of e↵ective use of described algorithms for further work with divisors on the hyperelliptic curve, including the development of cryptosystem, digital signature based on hyperelliptic curves, attacks on such cryptosystems.
The paper studies hyperelliptic curves of the genus g > 1, divisors on them and their applications in Python programming language. The basic necessary definitions and known properties of hyperelliptic curves are demonstrated, as well as the notion of polynomial function, its representation in unique form, also the notion of rational function, norm, degree and conjugate to a polynomial are presented. These facts are needed to calculate the order of points of desirable functions, and thus to quickly and eciently calculate divisors. The definition of a divisor on a hyperelliptic curve is shown, and the main known properties of a divisor are given. There are also an example of calculating a divisor of a polynomial function, reduced and semi-reduced divisors are described, theorem of the existence of such a not unique semi-reduced divisor, and theorem of the existence of a unique reduced divisor, which is equivalent to the initial one, are proved. In particular, a semi-reduced divisor can be represented as an GCD of divisors of two polynomial functions. It is also demonstrated that each reduced divisor can be represented in unique form by pair of polynomials [a(x), b(x)], which is called Mumford representation, and several examples of its representation calculation are given. There are shown Cantor’s algorithms for calculating the sum of two divisors: its compositional part, by means of which a not unique semireduced divisor is formed, and the reduction part, which gives us a unique reduced divisor. In particular, special case of the compositional part of Cantor’s algorithm, doubling of the divisor, is described: it significantly reduces algorithm time complexity. Also the correctness of the algorithms are proved, examples of applications are given. The main result of the work is the implementation of the divisor calculation of a polynomial function, its Mumford representation, and Cantor’s algorithm in Python programming language. Thus, the aim of the work is to demonstrate the possibility of e↵ective use of described algorithms for further work with divisors on the hyperelliptic curve, including the development of cryptosystem, digital signature based on hyperelliptic curves, attacks on such cryptosystems.
Description
Keywords
гiперелiптична крива, дивiзор, зображення Мамфорда, стаття, hyperelliptic curve, divisor, Mumford representation
Citation
Бойко Д. А. Обчислення дивiзорiв на гiперелiптичнiй кривiй та їхнє прикладне застосування на мовi Python / Бойко Д. А. // Могилянський математичний журнал. - 2020. - Т. 3. - С. 11-24.