Mathematics – Number Theory
Scientific paper
2001-05-22
Math. Comp. 73 (2004), no. 245, 333--357
Mathematics
Number Theory
25 pages, version submitted for publication. Minor editorial corrections from version 2, after referee's report
Scientific paper
We use an embedding of the symmetric $d$th power of any algebraic curve $C$ of genus $g$ into a Grassmannian space to give algorithms for working with divisors on $C$, using only linear algebra in vector spaces of dimension $O(g)$, and matrices of size $O(g^2)\times O(g)$. When the base field $k$ is finite, or if $C$ has a rational point over $k$, these give algorithms for working on the Jacobian of $C$ that require $O(g^4)$ field operations, arising from the Gaussian elimination. Our point of view is strongly geometric, and our representation of points on the Jacobian is fairly simple to work with; in particular, none of our algorithms involves arithmetic with polynomials. We note that our algorithms have the same asymptotic complexity for general curves as the more algebraic algorithms in Hess' 1999 Ph.D. thesis, which works with function fields as extensions of $k[x]$. However, for special classes of curves, Hess' algorithms are asymptotically more efficient than ours, generalizing other known efficient algorithms for special classes of curves, such as hyperelliptic curves (Cantor), superelliptic curves (Galbraith, Paulus, and Smart), and $C_{ab}$ curves (Harasawa and Suzuki); in all those cases, one can attain a complexity of $O(g^2)$.
No associations
LandOfFree
Linear algebra algorithms for divisors on an algebraic curve does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Linear algebra algorithms for divisors on an algebraic curve, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear algebra algorithms for divisors on an algebraic curve will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-354160