Improvements to Jacobian Arithmetic in Global Function Fields

Michael Jacobson Jr.; Renate Scheidler; Vincent Macri

arxiv: 2605.15323 · v1 · pith:7GTJUIRQnew · submitted 2026-05-14 · 🧮 math.NT

Improvements to Jacobian Arithmetic in Global Function Fields

Vincent Macri , Michael Jacobson Jr. , Renate Scheidler This is my paper

Pith reviewed 2026-05-19 16:00 UTC · model grok-4.3

classification 🧮 math.NT

keywords global function fieldsJacobian arithmeticdivisor classesreduction stepscachingarithmetic algorithmsfunction field arithmetic

0 comments

The pith

Two optimizations to Jacobian arithmetic in global function fields cut reduction steps for typical inputs and cache intermediates to achieve faster practical performance.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces two changes to arithmetic in the Jacobian of global function fields. The first change assumes the field has a degree-one place and reduces the number of expensive reduction steps by targeting typical cases rather than the worst case. The second change trades memory for time by storing frequently used intermediate results. Asymptotic analysis and experiments indicate these changes yield significantly faster runtimes than earlier methods, and the accompanying software is presented as the first to handle unique representatives of divisor classes.

Core claim

We present two improvements to arithmetic in the Jacobian of global function fields. 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. 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 the 1

What carries the argument

Optimized reduction procedure for typical inputs together with caching of intermediate results in divisor-class arithmetic.

Load-bearing premise

The global function field contains a degree-one place, which enables the reduction-step optimization for typical rather than worst-case inputs.

What would settle it

A runtime benchmark on multiple global function fields that measures divisor-class arithmetic with the new algorithms against prior methods and finds no consistent speedup for typical inputs.

Figures

Figures reproduced from arXiv: 2605.15323 by Michael Jacobson Jr., Renate Scheidler, Vincent Macri.

**Figure 1.** Figure 1: Addition performance for 4 ≤ g ≤ 55, n = 3, p = 32771 4 7 13 19 22 25 28 31 34 37 40 43 46 49 55 0 100 200 300 400 500 600 Genus Average CPU time (milliseconds) Linear search without caching Linear search without caching complexity Linear search with caching Linear search with caching complexity Binary search without caching Binary search without caching complexity Binary search with caching Binary search … view at source ↗

**Figure 2.** Figure 2: Addition performance for 3 ≤ n ≤ 8, g = 15, p = 32771 3 4 5 6 7 8 0 100 200 300 400 500 600 700 Degree Average CPU time (milliseconds) Linear search without caching Linear search without caching complexity Linear search with caching Linear search with caching complexity Binary search without caching Binary search without caching complexity Binary search with caching Binary search with caching complexity 7 … view at source ↗

read the original abstract

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. 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper adds two practical tweaks to Hess's Jacobian arithmetic plus a software release, but the headline speedups hinge on fields having a degree-one place.

read the letter

The core contribution is a pair of targeted changes to the Hess reduction process for divisor class arithmetic in global function fields. One change trims expensive reduction steps by handling common inputs more efficiently when a degree-one place exists; the other adds a caching layer that trades memory for fewer recomputations. They also ship the first public implementation that returns unique representatives for classes. The asymptotic claims and the reported timing experiments are the main evidence offered for the practical gains over earlier published methods. That combination of incremental algorithm work and working code is the part worth noting. The caching improvement stands on its own and should apply more broadly. The reduction optimization is narrower because it explicitly requires a degree-one place; without it the algorithm falls back to standard Hess steps and the measured speedups shrink. The abstract flags this assumption, and the stress-test note is right that the overall performance story is therefore conditional on the fields people actually use. The experiments are described only at a high level here, so it is hard to judge how representative the test cases are or whether error bars or multiple runs are included. Still, the work is internally consistent and the implementation claim is a concrete, verifiable addition rather than just another complexity bound. This is aimed at people who need fast Jacobian arithmetic for function-field cryptography or coding-theory constructions. A reader already working in that niche will get immediate value from the code and the concrete timing numbers. The paper is coherent enough and grounded enough in prior work to deserve a serious referee rather than a desk rejection; the implementation and the empirical side are the parts that need checking.

Referee Report

2 major / 2 minor

Summary. The manuscript presents two improvements to Jacobian arithmetic in global function fields following the approach of Hess. The first reduces the number of expensive reduction steps by optimizing for typical inputs rather than worst-case behavior, under the assumption that the function field contains a degree-one place. The second introduces a caching mechanism for frequently used intermediate results to achieve a memory-time trade-off. Asymptotic analysis and empirical experiments are invoked to claim that the improved algorithms are significantly faster in practice than prior methods, and the accompanying publicly available software is asserted to be the first implementation supporting unique representatives of divisor classes.

Significance. If the performance claims hold under the stated conditions, the work could improve practical efficiency of Jacobian computations in function fields, with relevance to cryptographic protocols and algebraic geometry over finite fields. The caching improvement appears broadly applicable, while the unique-representatives feature in the software adds a concrete implementation contribution. The primary optimization's dependence on a degree-one place, however, narrows the scope of the headline speed-up claim.

major comments (2)

[Abstract; §3 (first improvement)] Abstract and the description of the first improvement: the optimization that reduces reduction steps for typical inputs explicitly requires a degree-one place; without it the algorithm reverts to standard Hess reduction. This makes the combined asymptotic and practical speedup claims conditional rather than general, and the manuscript should quantify how often global function fields of interest satisfy the assumption or provide fallback performance data.
[Empirical experiments (presumably §5 or §6)] Empirical validation section: the abstract states that experiments support 'significantly faster in practice,' yet the reader's assessment notes moderate evidence due to lack of access to full methods, data, and error analysis. If the test fields all contain degree-one places, the results do not demonstrate robustness for the general case; explicit reporting of field degrees, place degrees, and timing breakdowns with/without the first optimization is needed to substantiate the central claim.

minor comments (2)

[Software implementation description] Clarify the precise definition of 'unique representatives of divisor classes' and how the software enforces them, as this is presented as a novel feature.
[Asymptotic analysis] Ensure all asymptotic statements distinguish between the caching improvement (general) and the reduction optimization (conditional on degree-one place).

Simulated Author's Rebuttal

2 responses · 0 unresolved

We are grateful to the referee for the detailed and constructive report. Below we respond to each of the major comments in turn, indicating the changes we plan to make in the revised version of the manuscript.

read point-by-point responses

Referee: [Abstract; §3 (first improvement)] Abstract and the description of the first improvement: the optimization that reduces reduction steps for typical inputs explicitly requires a degree-one place; without it the algorithm reverts to standard Hess reduction. This makes the combined asymptotic and practical speedup claims conditional rather than general, and the manuscript should quantify how often global function fields of interest satisfy the assumption or provide fallback performance data.

Authors: We agree that the first improvement is predicated on the presence of a degree-one place, as already stated in the manuscript. This assumption holds in many settings of practical interest, such as cryptographic applications involving curves with rational points. In the revision we will make the conditional nature more prominent in the abstract and Section 3, add a short discussion of the prevalence of degree-one places in function fields arising in applications, and explicitly note that the algorithm reverts to standard Hess reduction (with no extra cost) when the assumption fails. revision: yes
Referee: [Empirical experiments (presumably §5 or §6)] Empirical validation section: the abstract states that experiments support 'significantly faster in practice,' yet the reader's assessment notes moderate evidence due to lack of access to full methods, data, and error analysis. If the test fields all contain degree-one places, the results do not demonstrate robustness for the general case; explicit reporting of field degrees, place degrees, and timing breakdowns with/without the first optimization is needed to substantiate the central claim.

Authors: We accept that additional detail in the experimental section would strengthen the presentation. The revised manuscript will include a table listing the degrees of the tested function fields, the degrees of the places employed, and explicit timing comparisons run both with and without the first optimization. We will also report basic variability measures (e.g., standard deviations over repeated trials) to address concerns about error analysis. revision: yes

Circularity Check

0 steps flagged

No circularity in algorithmic improvements or empirical claims

full rationale

The paper presents two explicit algorithmic improvements to Hess-style Jacobian arithmetic in global function fields: one that optimizes reduction steps for typical inputs under the stated assumption of a degree-one place, and a second that introduces caching for a memory-time tradeoff. These are described as direct modifications to existing reduction procedures rather than derivations that redefine inputs as outputs. Asymptotic analysis and separate empirical experiments are invoked to support practical speedups, with no evidence of self-definitional steps, fitted parameters renamed as predictions, or load-bearing self-citations that reduce the central claims to unverified prior results by the same authors. The assumption of a degree-one place is presented as a precondition limiting applicability for the first improvement, not as a derived or smuggled-in result. The overall derivation chain remains self-contained against external benchmarks and falsifiable experiments.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based solely on the abstract, no free parameters, axioms, or invented entities are explicitly introduced; the work relies on standard properties of global function fields and the existing Hess framework.

pith-pipeline@v0.9.0 · 5615 in / 1051 out tokens · 37537 ms · 2026-05-19T16:00:20.165481+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

[1]

Bauch, J.D.: Lattices over Polynomial Rings and Applications to Function Fields. Ph.D. thesis, Universitat Autònoma de Barcelona, Bellaterra (Jul 2014)

work page 2014
[2]

Bosma, J

Bosma, W., Cannon, J., Playoust, C.: The Magma Algebra System I: The User Language. Journal of Symbolic Computation24(3-4), 235–265 (Sep 1997). https: //doi.org/10.1006/jsco.1996.0125

work page doi:10.1006/jsco.1996.0125 1997
[3]

Galbraith, S.D.: Mathematics of Public Key Cryptography. 2 edn. (Oct 2018)

work page 2018
[4]

In: van der Poorten, A.J., Stein, A

Galbraith, S.D., Harrison, M., Mireles Morales, D.J.: Efficient Hyperelliptic Arith- metic Using Balanced Representation for Divisors. In: van der Poorten, A.J., Stein, A. (eds.) Algorithmic Number Theory. pp. 342–356. Lecture Notes in Computer Science, Springer, Berlin, Heidelberg (2008). https://doi.org/10.1007/978-3-540-7 9456-1_23

work page doi:10.1007/978-3-540-7 2008
[5]

Free Software Foundation, Inc

Granlund, T., et al.: GNU multiple precision arithmetic library. Free Software Foundation, Inc. (2023)

work page 2023
[6]

Harris, K

Harris, C.R., Millman, K.J., Van Der Walt, S.J., Gommers, R., Virtanen, P., Cour- napeau,D.,Wieser,E.,Taylor,J.,Berg,S.,Smith,N.J.,Kern,R.,Picus,M.,Hoyer, S., Van Kerkwijk, M.H., Brett, M., Haldane, A., Del Río, J.F., Wiebe, M., Peter- son, P., Gérard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., Oliphant, T.E.: Array progr...

work page doi:10.1038/s41586-020-2649-2 2020
[7]

Hess, F.: Computing Riemann-Roch spaces in algebraic function fields and related topics. J. Symb. Comput.33(4), 425–445 (Apr 2002). https://doi.org/10.1006/js co.2001.0513

work page doi:10.1006/js 2002
[8]

In: Arithmetic, Geometry and Coding Theory (AGCT 2003)

Howe, E., Lauter, K.E., Top, J.: Pointless curves of genus three and four. In: Arithmetic, Geometry and Coding Theory (AGCT 2003). Séminaires et Congrès, vol. 11, pp. 125–141. Société Mathématique de France, Paris (2005)

work page 2003
[9]

In: Algorithmic number theory (Sydney, 2002), Lecture Notes in Comput

Jacobson, Jr., M.J., van der Poorten, A.J.: Computational aspects of NUCOMP. In: Algorithmic number theory (Sydney, 2002), Lecture Notes in Comput. Sci., vol. 2369, pp. 120–133. Springer, Berlin (2002). https://doi.org/10.1007/3-540-4 5455-1_10, https://doi-org.ezproxy.lib.ucalgary.ca/10.1007/3-540-45455-1_10

work page doi:10.1007/3-540-4 2002
[10]

Junge, M.: Asymptotically Fast Arithmetic in the Picard Group of Algebraic Curves & Related Topics. Ph.D. thesis, Universität Oldenburg (2022)

work page 2022
[11]

Mathematics of Computation73(245), 333–357 (2004)

Khuri-Makdisi, K.: Linear algebra algorithms for divisors on an algebraic curve. Mathematics of Computation73(245), 333–357 (2004). https://doi.org/10.1090/ S0025-5718-03-01567-9

work page 2004
[12]

Mathematics of Computation76(260), 2213–2239 (Oct 2007)

Khuri-Makdisi, K.: Asymptotically fast group operations on Jacobians of general curves. Mathematics of Computation76(260), 2213–2239 (Oct 2007). https://doi. org/10.1090/S0025-5718-07-01989-8

work page doi:10.1090/s0025-5718-07-01989-8 2007
[13]

In: Boulier, F., England, M., Sadykov, T.M., Vorozhtsov, E.V

Lindner, S., Imbert, L., Jacobson, Jr., M.J.: Balanced NUCOMP. In: Boulier, F., England, M., Sadykov, T.M., Vorozhtsov, E.V. (eds.) Computer Algebra in Sci- entific Computing. Lecture Notes in Computer Science, vol. 12291, pp. 402–420. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-60026-6_23

work page doi:10.1007/978-3-030-60026-6_23 2020
[14]

Master’s thesis, University of Calgary (Sep 2025)

Macri, V.: Comparison of and Improvements to Degree Zero Divisor Class Group Arithmetic in Algebraic Function Fields. Master’s thesis, University of Calgary (Sep 2025). https://doi.org/10.11575/PRISM/50422

work page doi:10.11575/prism/50422 2025
[15]

Mireles Morales, D.J.: Efficient Arithmetic on Hyperelliptic Curves with Real Rep- resentation. Ph.D. thesis, The University of London (2008)

work page 2008
[16]

Mathematics of Computation68(227), 1233–1241 (Feb 1999)

Paulus, S., Rück, H.G.: Real and imaginary quadratic representations of hyperel- liptic function fields. Mathematics of Computation68(227), 1233–1241 (Feb 1999). https://doi.org/10.1090/S0025-5718-99-01066-2

work page doi:10.1090/s0025-5718-99-01066-2 1999
[17]

Stichtenoth, H.: Algebraic Function Fields and Codes, Graduate Texts in Mathe- matics, vol. 254. Springer, Berlin, Heidelberg, 2 edn. (2009). https://doi.org/10.1 007/978-3-540-76878-4

work page 2009
[18]

The Open Book Series2(1), 425–442 (Jan 2019)

Sutherland, A.V.: Fast Jacobian arithmetic for hyperelliptic curves of genus 3. The Open Book Series2(1), 425–442 (Jan 2019). https://doi.org/10.2140/obs.2019.2.4 25

work page doi:10.2140/obs.2019.2.4 2019
[19]

Tang, A.: Infrastructure of Function Fields of Unit Rank One. Ph.D. thesis, Uni- versity of Calgary (2011)

work page 2011
[20]

The FLINT team: FLINT: Fast Library for Number Theory (2025)

work page 2025
[21]

The Sage Developers: SageMath, the Sage Mathematics Software System (2026)

work page 2026
[22]

Wiles, A.: The Birch and Swinnerton-Dyer Conjecture

work page
[23]

Wolfram, D., Greuel, G.M., Pfister, G., Schönemann, H.:Singular4-4-1 — A computer algebra system for polynomial computations (2025)

work page 2025

[1] [1]

Bauch, J.D.: Lattices over Polynomial Rings and Applications to Function Fields. Ph.D. thesis, Universitat Autònoma de Barcelona, Bellaterra (Jul 2014)

work page 2014

[2] [2]

Bosma, J

Bosma, W., Cannon, J., Playoust, C.: The Magma Algebra System I: The User Language. Journal of Symbolic Computation24(3-4), 235–265 (Sep 1997). https: //doi.org/10.1006/jsco.1996.0125

work page doi:10.1006/jsco.1996.0125 1997

[3] [3]

Galbraith, S.D.: Mathematics of Public Key Cryptography. 2 edn. (Oct 2018)

work page 2018

[4] [4]

In: van der Poorten, A.J., Stein, A

Galbraith, S.D., Harrison, M., Mireles Morales, D.J.: Efficient Hyperelliptic Arith- metic Using Balanced Representation for Divisors. In: van der Poorten, A.J., Stein, A. (eds.) Algorithmic Number Theory. pp. 342–356. Lecture Notes in Computer Science, Springer, Berlin, Heidelberg (2008). https://doi.org/10.1007/978-3-540-7 9456-1_23

work page doi:10.1007/978-3-540-7 2008

[5] [5]

Free Software Foundation, Inc

Granlund, T., et al.: GNU multiple precision arithmetic library. Free Software Foundation, Inc. (2023)

work page 2023

[6] [6]

Harris, K

Harris, C.R., Millman, K.J., Van Der Walt, S.J., Gommers, R., Virtanen, P., Cour- napeau,D.,Wieser,E.,Taylor,J.,Berg,S.,Smith,N.J.,Kern,R.,Picus,M.,Hoyer, S., Van Kerkwijk, M.H., Brett, M., Haldane, A., Del Río, J.F., Wiebe, M., Peter- son, P., Gérard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., Oliphant, T.E.: Array progr...

work page doi:10.1038/s41586-020-2649-2 2020

[7] [7]

Hess, F.: Computing Riemann-Roch spaces in algebraic function fields and related topics. J. Symb. Comput.33(4), 425–445 (Apr 2002). https://doi.org/10.1006/js co.2001.0513

work page doi:10.1006/js 2002

[8] [8]

In: Arithmetic, Geometry and Coding Theory (AGCT 2003)

Howe, E., Lauter, K.E., Top, J.: Pointless curves of genus three and four. In: Arithmetic, Geometry and Coding Theory (AGCT 2003). Séminaires et Congrès, vol. 11, pp. 125–141. Société Mathématique de France, Paris (2005)

work page 2003

[9] [9]

In: Algorithmic number theory (Sydney, 2002), Lecture Notes in Comput

Jacobson, Jr., M.J., van der Poorten, A.J.: Computational aspects of NUCOMP. In: Algorithmic number theory (Sydney, 2002), Lecture Notes in Comput. Sci., vol. 2369, pp. 120–133. Springer, Berlin (2002). https://doi.org/10.1007/3-540-4 5455-1_10, https://doi-org.ezproxy.lib.ucalgary.ca/10.1007/3-540-45455-1_10

work page doi:10.1007/3-540-4 2002

[10] [10]

Junge, M.: Asymptotically Fast Arithmetic in the Picard Group of Algebraic Curves & Related Topics. Ph.D. thesis, Universität Oldenburg (2022)

work page 2022

[11] [11]

Mathematics of Computation73(245), 333–357 (2004)

Khuri-Makdisi, K.: Linear algebra algorithms for divisors on an algebraic curve. Mathematics of Computation73(245), 333–357 (2004). https://doi.org/10.1090/ S0025-5718-03-01567-9

work page 2004

[12] [12]

Mathematics of Computation76(260), 2213–2239 (Oct 2007)

Khuri-Makdisi, K.: Asymptotically fast group operations on Jacobians of general curves. Mathematics of Computation76(260), 2213–2239 (Oct 2007). https://doi. org/10.1090/S0025-5718-07-01989-8

work page doi:10.1090/s0025-5718-07-01989-8 2007

[13] [13]

In: Boulier, F., England, M., Sadykov, T.M., Vorozhtsov, E.V

Lindner, S., Imbert, L., Jacobson, Jr., M.J.: Balanced NUCOMP. In: Boulier, F., England, M., Sadykov, T.M., Vorozhtsov, E.V. (eds.) Computer Algebra in Sci- entific Computing. Lecture Notes in Computer Science, vol. 12291, pp. 402–420. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-60026-6_23

work page doi:10.1007/978-3-030-60026-6_23 2020

[14] [14]

Master’s thesis, University of Calgary (Sep 2025)

Macri, V.: Comparison of and Improvements to Degree Zero Divisor Class Group Arithmetic in Algebraic Function Fields. Master’s thesis, University of Calgary (Sep 2025). https://doi.org/10.11575/PRISM/50422

work page doi:10.11575/prism/50422 2025

[15] [15]

Mireles Morales, D.J.: Efficient Arithmetic on Hyperelliptic Curves with Real Rep- resentation. Ph.D. thesis, The University of London (2008)

work page 2008

[16] [16]

Mathematics of Computation68(227), 1233–1241 (Feb 1999)

Paulus, S., Rück, H.G.: Real and imaginary quadratic representations of hyperel- liptic function fields. Mathematics of Computation68(227), 1233–1241 (Feb 1999). https://doi.org/10.1090/S0025-5718-99-01066-2

work page doi:10.1090/s0025-5718-99-01066-2 1999

[17] [17]

Stichtenoth, H.: Algebraic Function Fields and Codes, Graduate Texts in Mathe- matics, vol. 254. Springer, Berlin, Heidelberg, 2 edn. (2009). https://doi.org/10.1 007/978-3-540-76878-4

work page 2009

[18] [18]

The Open Book Series2(1), 425–442 (Jan 2019)

Sutherland, A.V.: Fast Jacobian arithmetic for hyperelliptic curves of genus 3. The Open Book Series2(1), 425–442 (Jan 2019). https://doi.org/10.2140/obs.2019.2.4 25

work page doi:10.2140/obs.2019.2.4 2019

[19] [19]

Tang, A.: Infrastructure of Function Fields of Unit Rank One. Ph.D. thesis, Uni- versity of Calgary (2011)

work page 2011

[20] [20]

The FLINT team: FLINT: Fast Library for Number Theory (2025)

work page 2025

[21] [21]

The Sage Developers: SageMath, the Sage Mathematics Software System (2026)

work page 2026

[22] [22]

Wiles, A.: The Birch and Swinnerton-Dyer Conjecture

work page

[23] [23]

Wolfram, D., Greuel, G.M., Pfister, G., Schönemann, H.:Singular4-4-1 — A computer algebra system for polynomial computations (2025)

work page 2025