Обчислення дивiзорiв на гiперелiптичнiй кривiй та їхнє прикладне застосування на мовi Python

Автор(и)

  • Denys Boiko Київський національний університет імені Тараса Шевченка

DOI:

https://doi.org/10.18523/2617-70803202011-24

Ключові слова:

гiперелiптична крива, дивiзор, зображення Мамфорда

Анотація

В робот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птичних кривих, атаки на таку криптосистему.

Біографія автора

Denys Boiko, Київський національний університет імені Тараса Шевченка

Студент другого курсу магiстратури (освiтня програма «Математика») механiко-математичного факультету Київського нацiонального унiверситету iменi Тараса Шевченка. Сфера наукових iнтересiв — криптологiя, алгебраїчна геометрiя.

Посилання

Alfred J. Menezes, Yi-Hong Wu and Robert J. Zuccherato, An elementary introduction to hyperelliptic curves (1996).

Neal Koblitz, “Hyperelliptic Cryptosystems”, Journal of Cryptology. 1, 139–150 (1989).

David G. Cantor, “Computing in the Jacobian of a Hyperelliptic Curve”, Mathematics of computation. 48 (177), 95–101 (1987).

Steven D. Galbraith, Michael Harrison, David J. Mireles Morales. Efficient Hyperelliptic Arithmetic using Balanced Representation for Divisors, 2008.

Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman. An Introduction to Mathematical Cryptography (2008), pp. 317–318.

Izuru Kitamura, Masanobu Katagi and Tsuyoshi Takagi. A Complete Divisor Class Halving Algorithm for Hyperelliptic Curve Cryptosystems of Genus Two (2005).

##submission.downloads##

Опубліковано

2021-02-24