divisorArithmetic

Magma explicit formulas for divisor class arithmetic on hyperelliptic curves of genus 2 and 3.

Sebastian Lindner. Companion code to Explicit Formulas for Hyperelliptic Curve Arithmetic (University of Calgary, 2020), built as ucalgary_2020_lindner_sebastian.pdf in this directory.

Twelve families: addition and doubling for each characteristic class {arb, nch2, ch2}, in the ramified (imaginary, deg f = 2g+1) and balanced split (real, deg f = 2g+2) models, at genus 2 and genus 3. Every case is explicit with no Cantor fallback and costs exactly one inversion. The split model requires a choice of reduced basis: positive reduced at genus 2, negative reduced at genus 3. Genus 2 ships both. See Reduced basis.

Also included: generic-genus Cantor and NUCOMP reference implementations, a Python verification framework that runs in CI, Magma whitebox and random testers for every family, timing experiments, a LaTeX table generator, and a Rust port. See Repository layout.

Last updated: 2026-08-26.

---

Typical Case Operation Counts

The frequent case of the highest-degree operation in each family. "Frequent" means the non-degenerate path, trivial gcd and full-degree result. There is exactly one inversion per operation.

family	addition				doubling
	M	S	A	C	M	S	A	C
g2 ramified arb	21	2	31	0	22	4	42	2
g2 ramified nch2	21	2	23	0	21	5	25	0
g2 ramified ch2	20	3	26	0	21	4	24	0
g2 split arb	27	1	37	3	30	2	44	8
g2 split nch2	26	2	36	0	29	3	39	0
g2 split ch2	27	1	34	0	29	2	31	0
g3 ramified arb	53	3	71	1	54	4	80	4
g3 ramified nch2	53	3	59	0	53	5	61	0
g3 ramified ch2	51	3	62	0	51	4	55	2
g3 split arb	66	3	75	12	74	3	89	19
g3 split nch2	66	3	73	0	73	4	85	0
g3 split ch2	66	3	68	0	72	4	74	1

Every figure is measured. python3 verification/opcount.py --family <name> executes the formulas over a real field, identifies the frequent case by observing which branch is taken, and cross-checks each contributing call against the Cantor reference implementation. All fifteen families measure, the twelve above plus genus-2 split negative reduced.

Where the thesis publishes a cell, measurement reproduces it exactly: the genus-2 ramified rows against tab:ramfcosts, and 168 split shapes against tab:splitfcosts and tab:g3splitfcosts{ADD,DBL}, every one at exactly one inversion. Two of those cells have since moved by design: the genus-3 split 33ADD n=0,0 and 3DBL n=0 each trade one multiplication for twelve additions, so measurement and the published table differ there deliberately, recorded in Thesis/ERRATA.md. One systematic divergence turned up during the original check and was the tool's rather than the thesis's, a flat +2A on every split row, because a divisor's balancing weight is a small integer and n := n1 + n2 - 2 is bookkeeping rather than field arithmetic. See NEW_WORK.md N31.

The genus-2 split figures are positive reduced, the basis of record. Negative reduced is a different algorithm and differs by an operation or two on several rows.

Each specialisation is cheaper than the arb it specialises on every shared shape, which verification/selftest.py asserts rather than assumes. See Operation-count tables for the counter of record and the one known misclassification in it, and Related work for how these compare against prior art.

---

Related Work

Two kinds of comparison. For genus-2 ramified and both split families the previous best is the thesis itself, since genus-2 ramified and the split model are its own contribution, and the rows are reproduced here so the repository tells the whole story in one place. Genus-3 ramified is the exception: the thesis defers it (chapter6.tex:15, "ramified models are developed by another student"), so the published state of the art there is other people's. That family now lives here and is complete. Randall Apperley wrote an initial version of the arbitrary characteristic addition and doubling and Amir Abbas Asgari wrote an initial specialisation of the odd characteristic addition; this work reworked those three and derived the other three to the current state of the art.

Every "this work" figure below is re-derived from verification/opcount.py and matches the published table exactly. RELATED_WORK.md carries the full survey, the per-lane detail and an access table for each source.

Genus 2, ramified

Against Lange 2005, the standard reference, in the 4 coordinate affine setting.

operation	Lange 2005				this work
	M	S	A	C	M	S	A	C
2DBL	22	6	56	3	22	4	42	2
12ADD	10	1	25	0	9	1	22	0
2ADD	22	3	40	0	21	2	31	0

Genus 2, split

Against Erickson, Jacobson and Stein 2011.

operation	EJS 2011				this work
	M	S	A	C	M	S	A	C
2DBL	30	2	50	10	30	2	44	8
2ADD	27	1	37	3	27	1	37	3
12ADD	17	2	30	6	14	2	26	3
1ADD	3	0	5	0	3	0	5	0

Two cells tie exactly and the rest are ahead on additions and constant products. The larger gains are in the adjustment operations, which this summary omits and the thesis table carries in full: EJS need two inversions for several of them where this work needs one.

Genus 3, ramified

Prior work reports combined M+S and no additions, so the columns differ from the families above, and both sides cost exactly 1I. † marks A counts we derived rather than figures the authors published: where a paper prints its formulas step by step the count is recoverable and is marked, and where the paper is closed it is not quoted. The derivation rules are in RELATED_WORK.md.

cell	Nyukai 2006			GKP 2004			this work
	M+S	C	A	M+S	C	A	M+S	C	A
odd char, addition	67	0	105†	70	0	105†	56	0	59
odd char, doubling	68	0	93†	70	0	90†	58	0	61
char 2, addition	n/a			67	0	100†	54	0	62
char 2, doubling	n/a			69	0	107†	55	2	55
arbitrary, addition	n/a			n/a			56	1	71
arbitrary, doubling	n/a			n/a			58	4	80

The characteristic 2 rows quote whichever GKP variant is cheaper for that operation, their h₂ = 0 form for the addition and their f₆ = 0 form for the doubling. Against the variant not shown the margin is wider: 68 M+S and 105A for the addition, 72 M+S and 113 to 114A for the doubling.

Genus 3, split

Against Rezai Rad et al. 2019 and Sutherland 2019.

operation	Rezai Rad et al. 2019				Sutherland 2019				this work
	M	S	A	C	M	S	A	C	M	S	A	C
3DBL odd	85	2	163	0	74	8	127	0	73	4	85	0
3ADD odd	75	2	138	0	73	6	127	0	66	3	73	0
3DBL char 2	89	1	116	0	n/a				72	4	74	1
3ADD char 2	81	0	118	0	n/a				66	3	68	0

Reading these tables

• C is zero in every previous best cell because those normal forms leave no curve coefficient to multiply by. It is non-zero only here and only in the arb families, which by definition cannot normalise, so those cells are the cost of generality rather than an oversight.
• The genus-3 ramified characteristic 2 rows are quoted at deg h = 3, this repository's target shape. Cheaper char 2 numbers exist at other h shapes and are not comparable, Birkner's h = 1 doubling being 21 M+S and 20A because a constant h collapses most of the work.
• The genus-2 ramified and both split comparisons are as the thesis published them in 2020. The genus-3 ramified survey was compiled in 2026 and is current.

---

Current and planned work

What is missing, in progress, or knowingly deferred. Verification figures are under Testing; this section is about what is not done.

• The characteristic 2 genus-3 formulas have no published comparison, and one is not planned here. Three normal forms differ: ours (any degree-3 h, f₆ = 0), Birkner's Type Ia (h irreducible, f₆ ∈ F₂, f₇ non-monic) and GKP's two variants. RELATED_WORK.md carries the forms and the counts with citations.
• Two known savings in the split model are unapplied, both with their identities already proved: the adjugate trade (+1M −12A, six sites) and a redundant 2×2 system (11M 6A deletable). Their prerequisite is discharged, since verification/opcount.py measures the split families now and a per-branch delta can be demonstrated, but they edit published formulas, so each moved cell owes a hand count and a Thesis/ERRATA.md entry.
• Detectability is 85.4%, not 100%. The whitebox corpus holds two cases per computation path per characteristic class from different fields, and 14.6% of the assignments in the formula bodies can still be perturbed without changing the returned divisor. Some of that is structural, a branch guarded on d = 0 needing d = 0 to be reached at all, so 100% is not the target. verification/detect.py reports it per family.
• One branch is exempt from coverage, ADD227 of ch2_splitG3_ADD, and it carries a proof of unreachability in characteristic 2 rather than a search budget excuse. Everything else is covered, 1,928 of 1,929.
• latexTables/latexConverter.py is not runnable; its input paths are stale. It has been demoted to a LaTeX renderer, counting having moved to verification/opcount.py, so the committed .tex tables cannot be regenerated, and nothing else depends on it.
• Errata are recorded before they are fixed, deliberately. A defect goes into ERRATA.md with a reproducer and waits for a gate that can see the fix. Entries whose reproducer already runs get fixed; the rest name the tooling they wait on.

---

Reduced basis

The split model represents a divisor class with v normalised against one of the two polynomials at infinity: positive reduced uses Vp, negative reduced uses Vn. Both represent the same class. The choice dictates the direction of any adjustment step, so it changes the formulas rather than the mathematics.

	basis	reason
genus 2	positive reduced	Addition and doubling have equal net cost in either basis, so there is no efficiency argument. Positive reduced matches the basis used by Erickson, Jacobson and Stein (2011), which makes the operation cost comparisons directly readable.
genus 3	negative reduced	Negative reduced is genuinely cheaper here. It absorbs one adjustment into the continued-fraction steps of Balanced NUCOMP, removing the need for any further adjustment in the frequent cases, and it lowers the degree of the k = f - v(v+h) polynomial through cancellations.

The published operation cost tables follow that choice, and the thesis contrasts the two bases explicitly in chapter 5 for genus 2 and chapter 6 for genus 3.

Genus 2 ships both, under g2/splitModel/posReduced/ and g2/splitModel/negReduced/. Genus 3 ships negative reduced only; there is no positive reduced basis at genus 3.

---

Running Magma

Magma is required and is not in this repository. It is commercial, licensed software. Place your tarball as magma.tar.xz at the repository root. It is gitignored, must never be committed, and an image built from it must never be pushed to any registry.

docker build -f tools/magma-docker/Dockerfile -t magma-qemufix .
MAGMA=tools/magma-docker/magma.sh ./test_all.sh

That runs 30 testers and exits 0, in a little over five minutes, essentially all of it Magma: 297 s of reported Magma time, across 62,944 divisor comparisons summed over the fifteen random testers. Every family has a whitebox tester, so nothing is skipped. See Testing.

Use tools/magma-docker/ rather than a plain docker build. On Apple Silicon a plain image cannot run most of this repository.

Why the container needs a patched emulator

magma.exe is a statically linked 32-bit i386 binary from 2015. Apple Silicon cannot run it natively and Rosetta translates x86-64 only, so Docker routes it through qemu-i386, QEMU's user-mode emulator. QEMU relocates a mapping whenever the guest passes MREMAP_MAYMOVE, including when the guest is shrinking it, where Linux would have kept the address. Magma checks that its blocks stay put, so it aborts:

memi_reduce_block_mmap: block moved
Magma: Internal error

With a stock emulator only the six genus-2 ramified testers load, and every other tester aborts here. It presents as a size limit, because whether Magma needs a shrink correlates with function length, which is why it was long mistaken for the formulas being too large for an old Magma.

tools/magma-docker/ builds a qemu-i386 with a one-line fix, after which the whole suite passes. The full diagnosis and the list of approaches that do not work are in tools/magma-docker/README.md.

---

Repository layout

path	contents
g2/ramifiedModel/	genus 2 ramified formulas, testers, shared utilities
g3/ramifiedModel/	genus 3 ramified formulas, testers, shared utilities
g2/splitModel/posReduced/	genus 2 balanced split, positive reduced
g2/splitModel/negReduced/	genus 2 balanced split, negative reduced
g3/splitModel/negReduced/	genus 3 balanced split, negative reduced
g2/timings/	genus 2 timing experiments, prior work formulas, results (47 files)
g3/timings/	genus 3 timing experiments and results (18 files)
generic/	generic-genus Cantor and NUCOMP reference implementations, and timings
whitebox/	whitebox test-case generator and its outputs
latexTables/	operation cost table generator and generated .tex
Thesis/	thesis LaTeX sources, corrections applied, see Thesis
ThesisPublished/	the same sources frozen as published, never edited, see FROZEN.md
test_all.sh	test entrypoint
1024bit_primes.mag	pre-generated 1024-bit primes for the timing experiments
rust/	Rust port, a git submodule, see Rust implementation
ucalgary_2020_lindner_sebastian.pdf	the built thesis

Formula files live in a g2Formulas/ or g3Formulas/ subdirectory of each model directory, for example g2/ramifiedModel/g2Formulas/ and g3/splitModel/negReduced/g3Formulas/. Testers sit one level up.

---

Naming convention

{arb,nch2,ch2}_{ramified,split}G{2,3}_{ADD,DBL,UTL}.mag

token	meaning
arb	arbitrary characteristic, no assumption on the field
nch2	odd characteristic, so h = 0, plus the f depression its genus allows: genus 2 f4 = 0 (needs char != 5), genus 3 f6 = 0 (needs char != 7)
ch2	characteristic 2
ADD / DBL	divisor addition / doubling
UTL	utilities, split model only, for the two places at infinity

Tester filenames are inconsistently cased, historically: genus 2 uses *_whiteBox_tester.mag with a capital B, genus 3 uses *_whitebox_tester.mag.

Deg<i><j>ADD names the degrees of the two input divisors, and one family disagrees about the order, so check before comparing.

The digits are positional: the smaller-degree divisor arrives first, in every family. Coefficients within an operand descend.

	example
genus 2 ramified	Deg12ADD(u0, v0, up1, up0, vp1, vp0, …)
genus 2 split, both bases	Deg12ADD(u0, v0, up1, up0, vp1, vp0, ccs)
genus 3 ramified	Deg23ADD(u1, u0, v1, v0, up2, up1, up0, vp2, vp1, vp0, …)
genus 3 split	Deg23ADD(u1, u0, v1, v0, up2, up1, up0, vp2, vp1, vp0, ccs)

So reading a name tells you what the inputs are, and the two Deg12ADD forms above differ only in their curve-constant tail. Genus-3 split was the last family to bind the larger divisor first, and genus-2 split the last to write coefficients ascending; both were aligned together, the second having contradicted its own Deg2DBL in the same file.

Same-degree cases are spelled with a single digit throughout: Deg1ADD for 1+1, Deg2ADD for 2+2, Deg3ADD for 3+3. The genus-3 models spelled the middle one Deg22ADD until it was collapsed with the reorder above. Doubling matches: Deg1DBL, Deg2DBL, Deg3DBL.

The reference implementation is duplicated. reduced_basis_arithmetic.mag exists in 8 copies across the tree in 5 byte-distinct versions, and genus 3 additionally has a separate 730-line poly_balanced_arithmetic.mag. The copy under g2/splitModel/negReduced/ is what the genus-2 testers assert against. Which copy is authoritative for a given consumer is currently implicit, so check before trusting any cross-comparison.

---

Testing

./test_all.sh

runs 30 testers across genus 2 and genus 3, fifteen whitebox and fifteen random, in a little over five minutes.

Where the project stands, each figure reproduced by the command beside it:

gate	result	command
Magma suite	30 testers, 0 failures, 0 skips	./test_all.sh
frozen case corpus	7,043 cases replayed, 7,043 matched	python3 verification/whitebox.py
branch coverage	1,928 of 1,929 labelled branches, 99.9%	as above
corpus detectability	85.4% of formula-body assignments observable	python3 verification/detect.py
differential tester	55,236 operations compared, 0 wrong	python3 verification/driver.py --strict
framework selftest	19 sections, 0 failures, 0 skips	python3 verification/selftest.py

The one uncovered branch is exempted with a written reason in verification/coverage_baseline.json: ch2_splitG3_ADD's ADD227 carries a proof that it is unreachable in characteristic 2.

Whitebox testers replay divisor operations found by coverage-guided search, two per computation path per characteristic class and drawn from different fields, asserting each result against the reference implementation. The cases are not hand-designed; what earns them a place in CI is that they are complete and deterministic.

Coverage and detectability answer different questions. Coverage asks whether every branch is reached. Detectability asks whether a change to the arithmetic would be noticed: every executed assignment is perturbed and the result compared, so an assignment whose perturbation changes nothing is invisible to the corpus however well covered its branch is. ERRATA.md E20 is that distinction costing a correct optimisation, and it is why each path carries two cases from different fields rather than one. 100% is neither reachable nor the target, some assignments being structurally invisible, such as a guard variable a branch requires to be zero. Per family the figures run from 69% to 96.5%.

The Python framework in verification/ is what runs in CI, since Magma is licensed and cannot. It interprets the real .mag source, so there is no transcription to drift:

python3 verification/whitebox.py                                  # frozen corpus, the CI gate
python3 verification/driver.py --curves 3 --pairs 3 --strict      # differential vs an independent reference, smoke volume
python3 verification/opcount.py --family ramified/g3/arb          # operation costs by execution
python3 verification/selftest.py                                  # the framework's own tests

It is pure standard library, so there is no install step and no lockfile.

Random testers compute random divisor additions and doublings over a fixed, enumerated list of small fields. The field list is not random; the curves and divisors drawn on each are. Exactly one curve is drawn per field in every tester, so the field list is the characteristic coverage, which is why the divisor volumes are small where the field lists are not.

tester	divisors per curve
genus 2 ramified, all three	500
genus 2 split, all six	250
genus 3 ramified, all three	50
genus 3 split, all three	25

Why these are enough, and what they are not for. The rare branches are proved by the whitebox testers deterministically, every case asserted against Magma's own Jacobian arithmetic at about a second per tester, so leaving a degenerate case to a one-in-q² dice roll here was never how it was covered. What the random testers uniquely add is within-branch input variation against fresh inputs, and for that volume was already far past the point of diminishing return: the one defect of that class this project ever found (E1) took 3,240,293 enumerated pairs, so 2500 per curve was three orders of magnitude short of catching it and 500 is no further away.

Replaying a failure. Magma does not seed deterministically, two runs of the same tester drawing different curves, so each of these testers prints its seed and the command to reuse it:

// - Random seed 1804224007, step 0. Replay this run with RND_SEED=1804224007

RND_SEED is forwarded into the container unconditionally by tools/magma-docker/magma.sh, so that line works as printed.

Not run by test_all.sh: generic/reduced_basis_tester.mag; generic/arbitrary/reduced_basis_tester.mag; and everything under g2/timings/ and g3/timings/.

---

Generic-genus algorithms

Reference implementations for arbitrary genus, used to validate the explicit formulas and to measure what the explicit formulas buy.

• generic/ is Cantor composition and reduction plus NUCOMP and NUDUPL for h = 0, characteristic not 2. 25 top-level routines.
• generic/arbitrary/ is the same for arbitrary characteristic, with 33 top-level routines, 8 more than the h = 0 version.

Each has ten timing drivers, timings_2bit.mag through timings_1024bit.mag:

magma timings_32bit.mag

generic/README.md has the routine index, and identifies which of the several results directories corresponds to which run.

---

Whitebox case generation

whitebox/whitebox_auto_NEG.py drives the case generators in whitebox/genFiles/ to emit a tester. Run it from the whitebox/ directory: the generators' load paths are relative to that, not to genFiles/.

cd whitebox
./whitebox_auto_NEG.py ch2 split 3 --trials 12000 --out ../g3/splitModel/negReduced/x.mag
./whitebox_auto_NEG.py ch2 split 3 --from-log logs/ch2_splitG3_log.txt   # reparse, no Magma

How a case is chosen. A generator loops over random curves and divisor pairs and prints a block for each operation whose result agrees with Magma's own Cantor arithmetic, letting the formula's own ADD_DEBUG/DBL_DEBUG label name the branch. The runner banks one block per label per field, then keeps --per-char of them per characteristic class, climbing the field ladder from the bottom, so a branch ends up with two cases from two different fields. Both halves of that are measured rather than preferred: two cases at one field leave more of the arithmetic invisible than one case at a larger field, because same-field failures are correlated, and the ladder is climbed from the bottom because the benefit saturates immediately while the cost does not. A whitebox tester is therefore the frozen output of a coverage-guided random search, complete and replayable, but not a set of hand-designed probes. Every case in the committed corpus is extracted from such a tester; verification/whitebox.py --harvest can search for cases directly, but nothing in the corpus comes from it today.

Three of the fifteen generators are unbounded, the genus-3 split ones. Their search loop is while true, so the run does not end on its own and the log grows without limit; the other twelve iterate a fixed field list and terminate. For those three, killing the container is not a substitute for finishing, because the runner sees the non-zero exit (magma exited 137) and refuses to write a tester. Let it run until the log holds every label, stop it, then re-parse with --from-log, which writes the tester without Magma. Check coverage first, since the log is the only thing that carries it:

grep -oE '^(ADD|DBL)[0-9]+$' logs/<family>_log.txt | sort -u | wc -l

Regeneration cannot always reproduce what is deployed, which is what --merge-tester is for. A fresh genus-3 split search reaches 403 of that family's 405 labels, and each label it misses is covered by exactly one deployed case, so discarding the existing tester would lose coverage. --merge-tester appends an existing tester's case blocks verbatim, which is regeneration rather than copying, since a tester is a header plus one self-contained block per case. The useful consequence is that a partial run pays: any second case found is additive and coverage cannot fall.

flag	effect
--trials	bounds the search
--per-char	cases kept per label per characteristic class, default 2
--basis	neg or pos, selecting the genus-2 split basis and the generator that matches it
--inherit-from FIELD:LOG	take an existing log's blocks as candidates, which is how arb carries its specialisations' cases
--merge-tester PATH	append an existing tester's case blocks verbatim
--from-log	re-parse a log without running Magma
--allow-incomplete	write a tester that misses a label, refused by default

Limitations:

• An unreached branch is reported, and writing a tester with a gap needs --allow-incomplete.
• whitebox/testerFiles/ is a staging directory, not the testers of record, and verification/whitebox.py deliberately excludes it. Its arb_splitG3_whiteBox_tester.mag is a two-case fragment from an aborted run; the deployed genus-3 split testers hold 1,979, 1,209 and 1,203 cases and live in g3/splitModel/negReduced/.
• whitebox/logs/ holds the residue of a pre-2025 orchestrator run alongside output from aborted ones. Two of the three original files begin mid-polynomial: that generation reset the log with truncate(0) while Magma still held it open at its own write offset. The runner now writes to a separate .new file and never truncates. Regeneration logs are gitignored, running to gigabytes where the committed ones are kilobytes.

---

Operation-count tables

verification/opcount.py is the counter of record. It measures by running the formulas over a real finite field, per branch, and identifies the frequent case by observing which branch is taken rather than inferring it from the source. It reports inversions, which the older static counter does not count at all. Every contributing execution is cross-checked against an independent Cantor implementation, so an input outside the formulas' domain shows up as a mismatch rather than as a plausible wrong count. Per-function figures for every family are in the appendix.

Conventions come from each formula file's own directives, never from a table here: //Constant: names the curve coefficients, so products with them count C rather than M; //Ignore: names coefficients whose products are free; //startIGNORE / //endIGNORE bracket the polynomial-level reference code kept beside each formula. Division by 2 counts as an addition, per the thesis.

One known misclassification, ERRATA.md E13. A product whose factor is a composite over curve coefficients, 2*f6*u1_0, is charged M although 2*f6 is fixed per curve. Six live sites, all in the genus-3 ramified arbitrary doubling, one of them on a frequent path. Totals are right; the M and C split is not.

latexTables/latexConverter.py is the older static counter, which scanned the source as text and emitted the thesis's LaTeX tables. The two agreed on all 208 published own-work quadruples, two methods sharing no code, but it is now demoted to a renderer: it does not run today, its input paths being stale, several counting faults are recorded in ERRATA.md, and nothing depends on it except regenerating .tex.

How the genus-3 ramified figures compare to the published literature, with every prior source's curve assumptions and the normalisation arithmetic stated, is in RELATED_WORK.md.

Efficiency findings for the arbitrary-characteristic genus-3 ramified formulas, each located, measured and adversarially verified, are in EFFICIENCY_ARB_G3.md. That document changes no formula; it was the input to the implementation work, which is complete.

What this project contributes beyond the published thesis, every correction, completion and result with the argument for why it is right and the measurement that establishes it, is in NEW_WORK.md. It is written to be lifted into the next publication and kept current as the work proceeds rather than reconstructed afterwards. Its Part I gives one account of the curve normal forms, uniform in the genus, producing all six ramified forms, and all six now have a formula banner declaring exactly that form. verification/normal_form.py reproduces every claim in it.

---

Timing experiments

g2/timings/ and g3/timings/ hold the drivers, the prior work formulas compared against, the raw results and the plots.

prior work	genus
lange_2005.mag, inf_2010.mag, geo_2011.mag, geo_noTrade_2011.mag	2
rad_2019.mag, sutherland_2019.mag	3

The formula copies under timings/*/ramFormulas/ and timings/*/splitFormulas/ are deliberate variants rather than duplicates: function names carry a _RAM or split suffix so both models can coexist in one Magma session, returns are tuples, and debug output is commented out to keep I/O out of the timed loop. They are hand-maintained and can drift from the canonical formulas.

g2/timings/arbitrary_implementation/ is a superseded fork that no longer runs.

A defect affecting the published negative reduced generic timings is recorded in ERRATA.md.

---

Rust implementation

rust/ is a git submodule pointing at github.com/salindne/divisor-arithmetic, a Rust port with its own tests and CI. Nothing in this repository builds or tests it.

git submodule update --init --recursive

The recorded pointer may lag the submodule's main.

---

Thesis

ucalgary_2020_lindner_sebastian.pdf at the repository root is the built document, as published and never modified.

The source exists in two copies, deliberately:

ThesisPublished/	frozen. Byte-exact as submitted; never edited
Thesis/	evolving. Corrections land here, each logged in Thesis/ERRATA.md

Both hold frontmatter.tex, chapter1.tex through chapter7.tex and appendix.tex, but not the master document that includes them. No .tex file has a \documentclass, so the thesis cannot be rebuilt from either directory as it stands.

Corrections are made only where they are justified, and Thesis/ERRATA.md says for each one whether it was verified by measurement or rests on a structural argument. diff -r ThesisPublished Thesis shows the current divergence.

---

Licence and citation

Code here is MIT licensed, see LICENSE. The licence covers the code only. ucalgary_2020_lindner_sebastian.pdf and the university thesis class and templates under Thesis/ are not covered and retain their own terms.

To cite:

S. Lindner. Explicit Formulas for Hyperelliptic Curve Arithmetic. PhD thesis, University of Calgary, 2020.

---

Appendix: operation costs by function

Operation costs for every non-degenerate function, measured as in Typical Case Operation Counts and reported per characteristic class. Each figure is the frequent branch of that operation. Ramified rows are function names; split rows carry the input balancing weights, because at split the weight is what selects which published row an operation belongs to. Shapes the dispatcher answers without arithmetic are omitted, five at genus 2 split and thirteen at genus 3 split. Genus-2 split negative reduced is omitted, positive reduced being the basis of record. Measured over GF(31) for arb and nch2, GF(32) for ch2.

Genus 2, ramified

operation	arb				nch2				ch2
	M	S	A	C	M	S	A	C	M	S	A	C
11ADD	3	0	4	0	3	0	4	0	3	0	4	0
12ADD	9	1	22	0	8	2	15	0	8	1	19	0
22ADD	21	2	31	0	21	2	23	0	20	3	26	0
1DBL	4	1	15	3	3	1	9	1	2	2	5	2
2DBL	22	4	42	2	21	5	25	0	21	4	24	0

Genus 3, ramified

operation	arb				nch2				ch2
	M	S	A	C	M	S	A	C	M	S	A	C
11ADD	3	0	4	0	3	0	4	0	3	0	3	0
12ADD	6	1	8	0	6	1	8	0	6	1	7	0
13ADD	18	1	39	0	16	3	28	0	15	2	33	0
22ADD	25	1	41	0	24	2	33	0	23	2	35	0
23ADD	36	3	55	0	35	4	45	0	34	4	46	1
33ADD	53	3	71	1	53	3	59	0	51	3	62	0
1DBL	7	1	24	4	5	1	15	1	4	2	7	2
2DBL	28	4	70	9	25	4	44	0	21	4	38	5
3DBL	54	4	80	4	53	5	61	0	51	4	55	2

Genus 2, split, positive reduced

operation	arb				nch2				ch2
	M	S	A	C	M	S	A	C	M	S	A	C
01ADD n=0,0	4	0	9	3	3	1	7	2	3	1	7	2
01ADD n=2,1	4	0	13	3	3	1	9	2	3	1	8	2
02ADD n=0,0	6	0	17	3	4	2	12	0	5	1	11	0
02ADD n=2,0	6	0	17	3	4	2	12	0	5	1	11	0
11ADD n=0,0	11	2	19	4	9	4	17	1	9	4	15	1
11ADD n=0,1	3	0	5	0	3	0	5	0	3	0	4	0
11ADD n=1,0	3	0	5	0	3	0	5	0	3	0	4	0
11ADD n=1,1	9	2	20	3	9	2	16	1	8	3	14	1
12ADD n=0,0	15	2	30	5	15	2	26	0	14	3	22	0
12ADD n=1,0	14	2	26	3	14	2	22	0	14	2	19	0
22ADD n=0,0	27	1	37	3	26	2	36	0	27	1	34	0
1DBL n=0	12	2	20	3	10	3	19	1	11	3	14	1
1DBL n=1	14	2	26	4	12	3	23	1	11	4	16	1
2DBL n=0	30	2	44	8	29	3	39	0	29	2	31	0

Genus 3, split, negative reduced

operation	arb				nch2				ch2
	M	S	A	C	M	S	A	C	M	S	A	C
01ADD n=0,0	33	2	48	21	30	4	37	7	31	3	37	11
01ADD n=0,1	8	0	17	5	6	1	14	3	6	1	12	3
01ADD n=1,0	8	0	17	5	6	1	14	3	6	1	12	3
01ADD n=3,2	8	0	12	4	6	1	10	3	6	1	10	3
02ADD n=0,0	37	2	54	21	33	5	42	6	34	4	39	10
02ADD n=0,1	10	0	23	6	8	2	19	2	9	1	17	2
02ADD n=1,0	10	0	23	6	8	2	19	2	9	1	17	2
02ADD n=3,1	10	0	23	6	9	1	21	2	9	1	20	2
03ADD n=0,0	40	2	60	22	36	5	44	3	37	3	46	9
03ADD n=1,0	11	0	29	7	9	1	21	0	9	1	21	2
03ADD n=3,0	11	0	29	7	9	1	21	0	9	1	21	2
11ADD n=0,0	41	4	57	23	38	6	46	8	38	6	45	10
11ADD n=0,1	14	2	26	5	13	3	23	1	13	3	20	1
11ADD n=0,2	3	0	5	0	3	0	5	0	3	0	5	0
11ADD n=1,0	14	2	26	5	13	3	23	1	13	3	20	1
11ADD n=1,1	3	0	5	0	3	0	5	0	3	0	5	0
11ADD n=1,2	3	0	5	0	3	0	5	0	3	0	5	0
11ADD n=2,0	3	0	5	0	3	0	5	0	3	0	5	0
11ADD n=2,1	3	0	5	0	3	0	5	0	3	0	5	0
11ADD n=2,2	17	2	25	5	15	4	23	1	15	4	21	1
12ADD n=0,0	47	5	67	22	44	7	54	6	44	7	50	9
12ADD n=0,1	18	3	36	6	17	4	30	1	17	4	28	1
12ADD n=1,0	18	3	36	6	17	4	30	1	17	4	28	1
12ADD n=1,1	6	1	10	0	6	1	10	0	6	1	10	0
12ADD n=2,0	6	1	10	0	6	1	10	0	6	1	10	0
12ADD n=2,1	20	3	39	7	19	4	36	1	18	5	33	1
13ADD n=0,0	53	4	74	22	49	7	62	3	51	5	56	7
13ADD n=1,0	22	2	43	7	21	3	36	0	22	2	33	0
13ADD n=2,0	25	2	49	8	23	4	42	0	23	4	40	0
22ADD n=0,0	61	3	78	25	56	6	72	5	57	5	66	8
22ADD n=0,1	30	1	47	8	29	2	47	0	29	2	41	0
22ADD n=1,0	30	1	47	8	29	2	47	0	29	2	41	0
22ADD n=1,1	37	1	56	7	36	2	57	0	33	4	52	0
23ADD n=0,0	75	3	89	18	72	5	78	3	72	4	76	7
23ADD n=1,0	41	1	59	3	41	1	57	0	41	1	55	0
33ADD n=0,0	66	3	75	12	66	3	73	0	66	3	68	0
1DBL n=0	42	5	66	27	40	6	57	7	38	7	44	10
1DBL n=1	7	1	19	6	7	1	15	3	7	1	14	3
1DBL n=2	14	3	25	8	14	3	24	3	12	3	19	4
2DBL n=0	62	5	95	31	60	7	89	4	60	7	80	7
2DBL n=1	37	0	56	13	35	2	54	3	36	1	48	3
3DBL n=0	74	3	89	19	73	4	85	0	72	4	74	1