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

Анотація

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