divisor-arithmetic

Explicit formulas for divisor arithmetic on genus 2 and 3 hyperelliptic curves.

This crate provides highly optimized implementations of divisor addition and doubling operations on the Jacobian of hyperelliptic curves, based on the research and Magma implementations from salindne/divisorArithmetic.

Features

• Genus 2 Ramified Model: Curves with one point at infinity

  • y² + h(x)y = f(x) where deg(f) = 5, deg(h) ≤ 2
  • Three optimized variants:
    • arbitrary - Arbitrary characteristic (general case)
    • not_char2 - Not characteristic 2 (simplified formulas when h(x) = 0)
    • char2 - Characteristic 2 (XOR-based operations)

• Genus 2 Split Model: Curves with two points at infinity

  • y² + h(x)y = f(x) where deg(f) = 6, deg(h) ≤ 3
  • Balanced divisors carry an integer balance weight, reduced with respect to a positive (Vpl) or negative (Vn = −Vpl − h) basis, with both bases provided (add_neg/double_neg, add_pos/double_pos)
  • Three variants: not_char2, arbitrary (any characteristic), char2
  • All formulas are cross-checked against a generic Cantor reference implementation (generic::split)

• Batched group law (ramified not_char2): add_batch / double_batch amortize the single field inversion across a whole batch of independent operations via Montgomery's trick (field::batch_invert), the same strategy smalljac uses for generic-group order computations

• Field Implementations:

  • PrimeField<P> - Prime fields F_p for small primes
  • MontgomeryField<P> - Prime fields F_p in Montgomery form (REDC multiply + binary-GCD inverse, no division) for odd P < 2^63: ~4× faster group law than PrimeField, drop-in via the same Field trait
  • BinaryExtField<K> - Binary extension fields GF(2^k) for k ≤ 24

• Generic Polynomial Algorithms: Reference implementations using Cantor's algorithm, NUCOMP, and NUDUPLE

Usage

Add to your Cargo.toml:

[dependencies]
divisor-arithmetic = "0.1"

Example: Divisor Addition on a Genus 2 Curve

use divisor_arithmetic::field::PrimeField;
use divisor_arithmetic::g2::ramified::not_char2::{add, double, CurveConstants, DivisorCoords};

type F31 = PrimeField<31>;

// Define curve: y² = x⁵ + 2x³ + 3x² + 4x + 5 over F_31
let curve = CurveConstants {
    f3: F31::new(2),
    f2: F31::new(3),
    f1: F31::new(4),
    f0: F31::new(5),
};

// Create degree-2 divisors
let d1 = DivisorCoords::deg2(F31::new(1), F31::new(2), F31::new(3), F31::new(4));
let d2 = DivisorCoords::deg2(F31::new(5), F31::new(6), F31::new(7), F31::new(8));

// Compute D1 + D2
let sum = add(&d1, &d2, &curve);

// Compute 2*D1
let doubled = double(&d1, &curve);

Example: Characteristic 2 Fields

use divisor_arithmetic::field::BinaryExtField;
use divisor_arithmetic::g2::ramified::char2::{add, double, CurveConstants, DivisorCoords};

type GF256 = BinaryExtField<8>;  // GF(2^8)

// Define curve over GF(2^8)
let curve = CurveConstants {
    f2: GF256::new(0x1A),
    f1: GF256::new(0x2B),
    f0: GF256::new(0x3C),
    h2: GF256::new(0),
    h1: GF256::new(0x4D),
    h0: GF256::new(0x5E),
};

let d1 = DivisorCoords::deg2(
    GF256::new(0x11), GF256::new(0x22),
    GF256::new(0x33), GF256::new(0x44),
);

let doubled = double(&d1, &curve);

Performance

g2::ramified::not_char2 compared to smalljac (Sutherland), a fast C library implementing the same genus-2 imaginary/ramified (degree-5) group law. Measured on the same machine (Apple Silicon, single core) at a 56-bit prime, using this crate's MontgomeryField backend.

Both run the affine group law with one field inversion per operation. In batched mode a single inversion is amortized across N = 1024 independent operations via Montgomery's trick: this crate's add_batch / double_batch (built on field::batch_invert), and smalljac's hecurve_ctx_t state machine + ff_parallel_invert. ns per operation:

operation	this crate (scalar)	smalljac (scalar)	this crate (batched)	smalljac (batched)
add	163	190	40	48
double	168	210	46	54

The crate matches or beats smalljac in both scalar and batched modes. Reproduce with cargo bench -- not_char2; the smalljac harness and arm64 build notes are in benches/smalljac-compare/.

Testing

Run all tests:

cargo test --release

Or use the test script for detailed output:

./scripts/test.sh

References

This implementation is based on:

• Original Magma Implementation: salindne/divisorArithmetic
• Thesis: Sebastian Lindner, "Explicit Formulas for Hyperelliptic Curve Arithmetic", University of Calgary, 2020

License

This project is licensed under the MIT License - see the LICENSE file for details.