In a previous joint article with Abu Salem, we gave efficient algorithms for Jacobian group arithmetic of “typical” divisor classes on $$C_{3,4}$$ C 3 , 4 curves, improving on similar results by other authors. At that time, we could only state that a general divisor was typical, and hence unlikely to be encountered if one implemented these algorithms over a very large finite field. This article pins down an explicit characterization of these typical divisors, for an arbitrary smooth projective curve of genus $$g ge 1$$ g ≥ 1 having at least one rational point. We give general algorithms for Jacobian group arithmetic with these typical divisors, and prove not only that the algorithms are correct if various divisors are typical, but also that the success of our algorithms provides a guarantee that the resulting output is correct and that the resulting input and/or output divisors are also typical. These results apply in particular to our earlier algorithms for $$C_{3,4}$$ C 3 , 4 curves. As a byproduct, we obtain a further speedup of approximately 15% on our previous algorithms for $$C_{3,4}$$ C 3 , 4 curves.
展开▼
机译:在先前与Abu Salem的联合文章中,我们为$$ C_ {3,4} $$ C 3,4曲线上的“典型”除数类的Jacobian群算术提供了有效的算法,对其他作者的类似结果进行了改进。那时,我们只能说一般的除数是典型的,因此如果在很大的有限域上实现这些算法,就不太可能遇到。本文确定了这些典型除数的显式特征,因为任意光滑的投影曲线为$$ g ge 1 $$ g≥1属,至少具有一个有理点。我们给出了具有这些典型除数的Jacobian群算术的通用算法,不仅证明了各种除数都是典型的,这些算法是正确的,而且证明了我们算法的成功提供了保证结果输出正确和结果输入的保证和/或输出除数也很典型。这些结果尤其适用于我们针对$$ C_ {3,4} $$ C 3,4曲线的早期算法。作为副产品,对于$$ C_ {3,4} $$ C 3,4曲线,我们在以前的算法中进一步提高了约15%的速度。
展开▼