Acceleration of Algorithm for the Reduced Sum of Two Divisors of a Hyperelliptic Curve
| Autor: | Xiuhuan Ding |
|---|---|
| Rok vydání: | 2010 |
| Předmět: |
Discrete mathematics
Quadratic cost Mathematics::Number Theory Acceleration (differential geometry) Mathematics::Algebraic Geometry Quadratic equation ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Hyperelliptic curve cryptography Fraction (mathematics) Continued fraction Hyperelliptic curve Time complexity Algorithm Mathematics |
| Zdroj: | Communications in Computer and Information Science ISBN: 9783642163357 ICICA (1) |
| DOI: | 10.1007/978-3-642-16336-4_24 |
| Popis: | The reduced sum of two divisors is one of the fundamental operations in many problems and applications related to hyperelliptic curves. This paper investigated the operation of the reduced sum of two divisors implemented by M.J. Jacobson et al. That algorithm relied on two pivotal algorithms in terms of continued fraction expansions on the three different possible models of a hyperelliptic curve: imaginary, real, and unusual, and required quadratic cost. By applying Half-GCD algorithm, the pivotal algorithms decreases the time cost. Consequently, the algorithm for computing the reduced sum of two divisors of an arbitrary hyperelliptic curve is accelerated from quadratic to nearly linear time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|