The average complexity of the Euclidean algorithm and hyperelliptic cryptography

This thesis deals with the average complexity of the Euclidean algorithm and hyperelliptic cryptography. The Euclidean algorithm is used to find the greatest common divisor as well as algebraic inverses. Hyperelliptic cryptography is a generalization of elliptic curve cryptography, which has come to the forefront of encryption technologies in recent years.;The most costly operation for hyperelliptic cryptography is the use of the extended Euclidean algorithm. We first use known results to establish the expected number of field operations for this algorithm when classical arithmetic is employed. This leads to the computations for the average complexity of hyperelliptic cryptography.;To improve the exact and asymptotic analysis, Karatsuba multiplication is considered and analyzed. This analysis is then used to improve the complexity of the extended Euclidean algorithm.