Module encoding 

Compressed and uncompressed encoding of primitive reduced positive definite binary quadratic forms of negative discriminants (even or odd). While this is of greater scope than this library (which restricts itself to odd discriminants), it ensures the wire format allows the library to expand to include also implementing binary quadratic forms of even discriminants (without requiring a distinct encoding specification for those, when the time comes).

Each module contains a documented, exact technical specification as to allow portable interoperability with any other implementation which also implements this specification.

All algorithms are presented in a pseudo-code which should be clear to any developer but is not guaranteed to coincide with any specific language or standard. When decoding, we generally use bytestream.next_byte() to signify reading the next byte from some (error-free, non-empty, ideal) stream of bytes. This is done to denote how the encodings (and associated decode methods) do not require any encapsulating and are self-contained. They additionally do not explicitly require the ability to look ahead or any external buffers.

Our encoding method is canonical, only yielding a single encoding for any binary quadratic form. When decoding, we require encodings be canonical. While the simplest check would be to decode, reduce, and re-encode, before checking the equality of the resulting bytes with the input bytes, we provide more cost-effective methods which perform the canonicity checks during the decoding process itself. While this requirement does increase the cost of decoding, we do not find it a considerable portion of a larger context’s runtime, but do find malleability too often a footgun to be worth the performance benefits.

The following function is used to validate decoded binary quadratic forms as primitive and reduced. It yields (a, b_positive, b_abs, c) for valid forms.

We assume the existence of a gcd function, which for gcd(x, y) returns the greatest common divisor of x, y.

// is used to represent floor division.

fn validate_binary_quadratic_form(a, b_positive, b_abs, discriminant) {
  c = ((b_abs * b_abs) - discriminant) // (4 * a)

  # Assert the form is of this discriminant
  assert ((b_abs * b_abs) - (4 * a * c)) == discriminant

  # Assert the form is reduced
  assert b_abs <= a
  assert a <= c
  # Assert _neither_ `|b| == a, a == c` _or_ that `b_positive == true`
  # (as required for a reduced form, when such a equality exists)
  assert (!((b_abs == a) || (a == c))) || b_positive
  # Assert the form is primitive
  assert gcd(a, b_abs, c) == 1

  return (a, b_positive, b_abs, c)
}

Modules

compressed 🔒 alloc

Compression of binary quadratic forms

uncompressed 🔒

Uncompressed encoding of binary quadratic forms

Enums

Error

An error encountered while decoding.

Traits

Limbs 🔒

The required view over a collection of limbs to validate a binary quadratic form.

Functions

validate_binary_quadratic_form 🔒

Validate a positive definite binary quadratic form (of negative discriminant) as primitive and reduced.