Struct Form

Source

pub struct Form {
    pub a: BigInt,
    pub b: BigInt,
    pub c: BigInt,
}

Expand description

A binary quadratic form $f = ax^2 + bxy + cy^2$ over an imaginary quadratic field.

Forms are elements of the class group $\text{Cl}(D)$ of a negative fundamental discriminant $D = b^2 - 4ac < 0$. The group law is composition, and the identity element is the principal form $(1, 1, (1-D)/4)$.

All arithmetic operations (composition, squaring, exponentiation) produce reduced forms, meaning:

$-a < b \le a$
$a \le c$
if $a = c$ then $b \ge 0$

Fields§

§a: BigInt

The leading coefficient $a > 0$.

§b: BigInt

The cross-term coefficient $b$ (satisfies $-a < b \le a$ when reduced).

§c: BigInt

The constant coefficient $c > 0$ (satisfies $c \ge a$ when reduced).

Implementations§

Source §

impl Form

Source

pub fn new(a: BigInt, b: BigInt, c: BigInt) -> Self

Creates a new form $(a, b, c)$ without any validation or reduction.

Prefer Form::from_abd or Form::generator when constructing from external data, as they validate the discriminant identity.

Source

pub fn identity(d: &BigInt) -> Self

Returns the principal identity element $(1, 1, (1 - D) / 4)$ for discriminant $D$.

The identity satisfies $e \circ f = f$ for any form $f$ in the same class group. Requires $D \equiv 3 \pmod 4$ (standard for imaginary quadratic fields with fundamental discriminant).

Source

pub fn from_abd(a: &BigInt, b: &BigInt, d: &BigInt) -> Option<Self>

Constructs a form $(a, b, c)$ from $a$, $b$, and discriminant $D$, computing $c = (b^2 - D) / (4a)$ and verifying exact divisibility.

Returns None if:

a is zero (degenerate form)
$(b^2 - D)$ is not exactly divisible by $4a$

Source

pub fn generator(d: &BigInt) -> Option<Self>

Returns the canonical generator form $(2, 1, (1 - D) / 8)$.

Valid for prime discriminants $D = -p$ where $p \equiv 7 \pmod 8$. In this case $2$ splits in $\mathbb{Q}(\sqrt{D})$ and the form $(2, 1, \cdot)$ generates a subgroup of the class group of order $\text{ord}(2)$ in $\text{Cl}(D)$.

Returns None if $(1 - D)$ is not divisible by 8, i.e. $D$ is not a valid prime discriminant of the required form.

Source

pub fn is_reduced(&self) -> bool

Returns true if the form is in reduced normal form.

A form $(a, b, c)$ is reduced if and only if:

$a > 0$ and $c > 0$
$-a < b \le a$ (normalization condition)
$a \le c$ (minimality condition)
if $a = c$, then $b \ge 0$ (uniqueness condition)

Source

pub fn reduce(&mut self, d: &BigInt)

Reduces this form in place using the Euclidean-style Gauss reduction algorithm.

After reduction the form satisfies the standard reduced form conditions (see Form::is_reduced). Every form class has a unique reduced representative.

§Algorithm

Iterates two steps until the form is reduced:

Normalize $b$: compute $s = \lfloor (a - b) / 2a \rfloor$, then $b’ = b + 2as$, $c’ = (b’^2 - D) / 4a$.
Minimize $a$: if $a > c’$, swap and negate — set $(a, b, c) = (c’, -b’, a)$ — and loop.

Terminates because the $a$-coefficient strictly decreases each swap.

Source

pub fn nudupl(&self, d: &BigInt, l: &BigInt) -> Form

Shanks’ NUDUPL algorithm — fast squaring of a binary quadratic form.

Computes $f^2 = f \circ f$ in the class group without full reduction of intermediate results, using a partial Euclidean step controlled by threshold l.

§Algorithm (Shanks, 1989 — Cohen §5.4.2)

Given form $(a_1, b_1, c_1)$ and threshold $L$:

Compute $s = \gcd(b_1, a_1)$ via extended GCD and co-factor $k = -xc_1$.
If $s > 1$: divide $a_1$ by $s$, multiply $c_1$ by $s$.
Reduce $k \pmod{a_1}$.
If $a_1 < L$: use direct multiplication (no partial reduction).
Otherwise: run partial XGCD on $(a_1, k)$ stopping at $L$, then compute the new $(a, b, c)$ from the Bézout coefficients (co2, co1) and remainders (r2, r1).

§Parameters

d: The negative fundamental discriminant.
l: The Shanks threshold $L = \lfloor |D|^{1/4} \rfloor$.

§Returns

A (possibly unreduced) form. Callers must call Form::reduce to obtain the canonical representative. Use Form::square for the combined squaring+reduction.

Source

pub fn nucomp(&self, other: &Form, d: &BigInt, l: &BigInt) -> Form

Shanks’ NUCOMP algorithm — fast composition of two binary quadratic forms.

Computes $f_1 \circ f_2$ in the class group using a partial Euclidean reduction step, keeping intermediate coefficients bounded by threshold l.

§Algorithm (Shanks, 1989 — Cohen §5.4.1)

Given forms $f_1 = (a_1, b_1, c_1)$ and $f_2 = (a_2, b_2, c_2)$ with $a_1 \le a_2$:

Compute $ss = (b_1 + b_2)/2$, $m = (b_1 - b_2)/2$.
Compute $sp = \gcd(a_2 \bmod a_1, a_1)$ via extended GCD.
If $sp = 1$: set $k = m \cdot v_1 \bmod a_1$.
If $sp > 1$: reduce through a second extended GCD of $ss$ and $sp$, divide $a_1, a_2$ by $s = \gcd(ss, sp)$ and scale $c_2$.
Apply partial XGCD or direct multiplication depending on $a_1$ vs $L$.

§Parameters

other: The second form $f_2$ to compose with.
d: The negative fundamental discriminant.
l: The Shanks threshold $L = \lfloor |D|^{1/4} \rfloor$.

§Returns

A (possibly unreduced) form. Use Form::compose for the combined compose+reduction.

Source

pub fn fast_pow(&self, exp: &BigUint, d: &BigInt, l: &BigInt) -> Form

Fast binary exponentiation using NUDUPL and NUCOMP with threshold-based reduction.

Computes $f^n$ using the standard left-to-right binary method:

Start with $\text{result} = f$ (from the leading bit of $n$).
For each remaining bit $i$ from high to low:
- Square: $\text{result} \leftarrow \text{NUDUPL}(\text{result})$
- If bit $i$ is set: compose $\text{result} \leftarrow \text{NUCOMP}(\text{result}, f)$
- Opportunistically reduce when result.a.bits() > |D|.bits() / 2 to prevent coefficient blowup between full reductions.
Final full Gauss reduction before return.

Returns the identity form for exp = 0.