We present two improvements to arithmetic in the Jacobian of global function fields based on the approach of Hess. The first reduces the number of expensive reduction steps by optimizing for typical inputs rather than worst-case behavior, assuming the function field contains a degree-one place. This results in an expected asymptotic speed-up by a factor that is logarithmic in the genus. The second introduces a memory–time trade-off that speeds up computations by caching frequently used intermediate results. Our asymptotic analysis and empirical experiments show that our improved algorithms are significantly faster in practice than previously published methods. To the best of our knowledge, our publicly-available software implementation of Jacobian arithmetic is the first to support unique representatives of divisor classes.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Improvements to Jacobian Arithmetic in Global Function Fields

  • Vincent Macri,
  • Michael Jacobson,
  • Renate Scheidler

摘要

We present two improvements to arithmetic in the Jacobian of global function fields based on the approach of Hess. The first reduces the number of expensive reduction steps by optimizing for typical inputs rather than worst-case behavior, assuming the function field contains a degree-one place. This results in an expected asymptotic speed-up by a factor that is logarithmic in the genus. The second introduces a memory–time trade-off that speeds up computations by caching frequently used intermediate results. Our asymptotic analysis and empirical experiments show that our improved algorithms are significantly faster in practice than previously published methods. To the best of our knowledge, our publicly-available software implementation of Jacobian arithmetic is the first to support unique representatives of divisor classes.