Module discriminant 

Methods for sampling and working with discriminants (and the maps between them)

We specifically provide the maps from “A Cryptosystem Based on Non-maximal Imaginary Quadratic Orders with Fast Decryption” by Detlef Hühnlein, Michael J. Jacobson, Jr., Sachar Paulus, and Tsuyoshi Takagi (https://link.springer.com/content/pdf/10.1007/bfb0054134.pdf). These maps traditionally note the prime conductor as q, yet the following implementations consistently denote it as p. This is as “Linearly Homomorphic Encryption from DDH” by Guilhem Castagnos and Fabien Laguillaumie (https://eprint.iacr.org/2025/047) denote the prime conductor as p and we prefer consistency with the latter paper.

The two relevant maps from “A Cryptosystem Based on Non-maximal Imaginary Quadratic Orders with Fast Decryption” require a FindIdealPrimeTo function. We specify it here as a coprime_from function, specified / as follows:

fn coprime_form(a, b, c, p) {
  if gcd(a, p) == 1 {
    return (a, b)
  }
  if gcd(c, p) == 1 {
    return (c, -b)
  }
  return (c + (b + a), -(b + (2 * a)))
}

Our function has the same bounds on the input, that the form is primitive, and achieves the same bounds on the output, that the a coefficient is coprime to the prime p. Note we do input the c coefficient in order to calculate the result yet yield the result without its c coefficient. If necessary, it can be calculated via the yielded a, b coefficients and the corresponding discriminant, as usual.

For correctness, it should be noted there are three cases:

1. If gcd(a, p) == 1, the output is the input
2. Else if gcd(c, p) == 1, we apply the transformation (a, b, c) -> (c, -b, a)
3. Else, we apply the transformation (a, b, c) -> (a, b + 2 a, c + b + a) followed by the transformation (a, b, c) -> (c, -b, a). This is a special case of the general transformation, (a, b + 2 m a, c + m b + m^2 a), with m = 1.

Having established the form is equivalent, we are left to argue the resulting a coefficient is coprime to p. This is a result of p being prime and the form being primitive such that gcd(a, b, c) = 1. Accordingly, either a, b, or c must be coprime to q, as if all weren’t, we’d have the contradiction gcd(a, b, c) = q. If a is coprime, the form is left as-is. If c is coprime, we return the equivalent (unreduced) form where the new a coefficient is the old c coefficient. Finally, if neither a nor c are coprime, we know their sum a + c is a multiple of q and b must be coprime to q. Accordingly, (a + c) + b will be coprime to q, hence why we return an equivalent form with that as the a coefficient. We do specify this as c + (b + a), which is equivalent, as we are able to bound b + a as being positive for reduced positive definite forms, simplifying the bounds on that intermediary term.

Structs

Cl15k

A fundamental discriminant as part of the CL15 cryptosystem.

Cl15p

A non-fundamental discriminant as part of the CL15 cryptosystem.

WithoutTrailingZeroBytes 🔒

Enums

Cl15Error

An error when sampling discriminants for the CL15 cryptosystem.

Traits

Discriminant

A discriminant of a class group.

FundamentalDiscriminant

A fundamental (square-free) discriminant.

NegativeDiscriminant

A negative discriminant of a class group.

OddDiscriminant

An odd discriminant.

Functions

coprime_form 🔒

For a primitive reduced positive definite form of negative discriminant, return the equivalent form whose a coefficient is coprime to the prime p.

le_malleable_eq 🔒

Check if two little-endian encodings represent the same number.