Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/poncelet/2015arithm/abs/junge.pdf Дата изменения: Tue Nov 24 06:40:26 2015 Дата индексирования: Sun Apr 10 13:13:50 2016 Кодировка: Поисковые слова: http astrokuban.info astrokuban

Asymptotic fast arithmetic in the divisor class group of function fields with large genus
Matthias Junge Department of Mathematics Carl von Ossietzky University Oldenburg, 26111 Germany November 23, 2015

Abstract Let F /K be an algebraic function field over the finite field K = Fq . We propose algorithms for the arithmetic in the degree zero divisor class group of F /K which only use fast linear algebra over the polynomial ring K [x] to cope with the arithmetic operations in an asymptotic running time of O (n-1 g ) where g tends to infinity and n O(g ). The basis for the algorithms is the connection between divisors (class representatives) and tuples of fractional ideals of subrings of F . With this connection and assuming that the representatives are always given in a specific form, which we prove to always exist, we can use the vector space structure of those fractional ideals as K [x]-modules. The latter is reflected by the fact that those fractional ideals can be represented by polynomial matrices. Altogether we have the correspondence between divisor class representatives and polynomial matrices which makes it possible to use nothing but fast linear algebra algorithms to implement the arithmetic operations. The basic idea, given by Florian Heъ in 2005 (Copenhagen, Arithmetic on general curves and applications ), assumes a special ramification behaviour of the infinite place. We generalise this approach to the arbitrary ramification behaviour.



with the great help of Florian Heъ

1