fp2-cbrt

Companion code for "Fast cube roots in Fp2 via the algebraic torus" (https://ia.cr/2026/392).

Methods

Six cube root methods are implemented:

Method	Description
cbrtTorus	Reduces the Fp2 cube root to base-field operations via the algebraic torus T₂(Fp) and a binary ladder for the Lucas V-sequence. This is the main method (Algorithm 1 in the paper).
cbrtTorusPrac	Same torus approach but uses a PRAC differential addition chain for the Lucas V-sequence instead of a binary ladder.
cbrtOkeyaSakurai (Fastest)	Same as cbrtTorus with Okeya–Sakurai-style recovery and Hamburg's trick: merges the U⁻¹ inversion into the cube-root exponentiation so that cbrt(n), 1/n and 1/U come from a single exponentiation + a few extra multiplications.
cbrtFrobenius (2-bit)	Frobenius-splitting multi-exponentiation in Fp2 using 2-bit windowed Strauss–Shamir (15-entry table).
cbrtFrobenius1bit	Same Frobenius splitting with 1-bit Strauss–Shamir (3-entry table).
cbrtDirect	Direct exponentiation in Fp2 using a fixed addition chain generated by addchain.

The exported Cbrt calls cbrtOkeyaSakurai. All methods produce zero heap allocations.

Target primes

Name	Prime	log₂(p)	p mod 9	Source
p-p254	BN254 base field	254	1	Pairing
p-p377	BLS12-377 base field	377	7	Pairing
p-p381	BLS12-381 base field	381	1	Pairing
i-p381	2^372 · 437 − 1	381	4	Isogeny
i-p575	2^567 · 139 − 1	575	4	Isogeny
i-p765	2^756 · 257 − 1	765	4	Isogeny

Repository structure

fp/                          Pre-generated Fp arithmetic packages (from gnark-crypto)
  pp254/                     BN254 base field
  pp377/                     BLS12-377 base field
  pp381/                     BLS12-381 base field
  ip381/                     2^372 * 437 - 1
  ip575/                     2^567 * 139 - 1
  ip765/                     2^756 * 257 - 1

fp2/                         Per-prime Fp2 arithmetic + cube root implementations
  pp254/
    e2.go                    Fp2 arithmetic (Add, Sub, Mul, Square, Inverse, ...)
    cbrt.go                  Cube root methods (generated)
    cbrt_addchain.go         Addition chain for direct exponentiation (machine-generated)
    prac.go                  PRAC differential addition chain (generated)
    cbrt_test.go             Tests and benchmarks (generated)
  pp377/ ip381/ ip575/ ip765/ pp381/   (same layout)

internal/generator/cbrt/     Code generator for cbrt.go, prac.go, cbrt_test.go
  generate.go                Per-field configs + main entry point
  template/
    cbrt.go.tmpl             Cube root algorithm template
    prac.go.tmpl             PRAC chain template
    cbrt_test.go.tmpl        Test/benchmark template

Code generation

The cube root logic is shared across all 6 fields via Go text/template. Only field-specific constants (exponents, loop bounds, verification constants) and structural variants (β = −1 vs −5, p mod 9) differ. The cbrt_addchain.go files are also generated automatically using addchain to search for optimal addition chains. To regenerate after modifying templates or configs:

go generate ./...

# or directly
go run ./internal/generator/cbrt/

Prerequisites

• Go >= 1.22

Build & test

# Run all tests
go test ./fp2/...

# Run tests for a specific prime
go test ./fp2/pp377/

# Verbose
go test -v ./fp2/...

Benchmarks

# Benchmark all methods for all primes
go test -bench=BenchmarkCbrt -benchmem -count=4 ./fp2/...

# Benchmark a specific prime
go test -bench=BenchmarkCbrt -benchmem -count=4 ./fp2/pp377/

Sample results (AMD EPYC 9R14, x86_64, Go 1.24)

Prime	Direct (µs)	Frob 1-bit (µs)	Frob 2-bit (µs)	Okeya–Sakurai (µs)	vs Direct
p-p254	33.0	27.8	23.0	18.6	1.77x
p-p377	113.4	86.1	74.5	52.3	2.17x
p-p381	95.6	80.0	65.9	53.1	1.80x
i-p381	66.9	67.0	54.2	39.0	1.72x
i-p575	354.8	366.6	290.1	153.6	2.31x
i-p765	1162.8	1226.3	967.0	732.0	1.59x

License

See LICENSE.