Zi – Gaussian Integers

Gaussian Integer Class

A Gaussian integer is a complex number whose real and imaginary parts are both integers. Similarly, a Gaussian rational is a complex number whose real and imaginary parts are rational numbers.

In mathematics, Gaussian integers and rationals are denoted by Z[i] & Q[i], resp. So, here, Zi & Qi denote the Gaussian integer and rational classes, respectively.

The classes support the arithmetic of Gaussian integers and rationals using the operators: +, -, , /, //, %, *, +=, -=, *=, and /=, along with a variety of number-theoretic algorithms, such as greatest common divisor (gcd), an extended Euclidean algorithm (xgcd), etc.

Example: >>> from gint import Zi, Qi >>> >>> alpha = Zi(11, 3) >>> beta = Zi(1, 8) >>> a, x, y = Zi.xgcd(alpha, beta) >>> print(f’{alpha * x + beta * y} = {alpha} * {x} + {beta} * {y}’) >>> # ==> (1-2j) = (11+3j) * (2-1j) + (1+8j) * 3j

class gint.zi.Zi(real=None, imag=None)

Bases: Complex

A class that represents a Gaussian integer. In mathematics, the set of all integers is denoted by Z, and the set of all Gaussian integers is denoted by Z[i].

__init__(real=None, imag=None) → None

property real: int

Retrieve the real component of this number.

This should subclass Real.

property imag: int

Retrieve the imaginary component of this number.

This should subclass Real.

conjugate()

(x+y*i).conjugate() returns (x-y*i).

property norm

__add__(other)

self + other

__sub__(other)

self - other

__mul__(other)

self * other

__truediv__(other)

Exact division. Returns the precise Gaussian-rational quotient as a Qi (or as a Zi, via Qi’s auto-collapse, when the division is exact). Uses exact integer/Fraction arithmetic throughout, so it never loses precision regardless of coefficient size.

__floordiv__(other)

Gaussian integers have no natural total order, so ‘floor’ division is defined as rounding to the nearest Gaussian integer (using exact Fraction arithmetic, so it stays precise regardless of coefficient size). This is distinct from __truediv__, which returns the exact quotient as a Qi or Zi.

inverse()

The exact multiplicative inverse of this Gaussian integer. Returns a Zi if self is a unit, otherwise a Qi. Provided so that inverse() works uniformly on any value coming out of Qi’s arithmetic, since a Qi with denominator 1 collapses into a Zi.

to_array()

static from_array(arr)

static is_gaussian_prime(x)

A Gaussian integer a+bi is prime iff:

• both a,b are nonzero and a^2+b^2 is a rational prime, or

• one of a,b is zero and the other has absolute value c, where c is a rational prime with c % 4 == 3 (primes p == 2 or p == 1 mod 4 are NOT Gaussian primes: 2 ramifies as -i(1+i)^2, and p == 1 mod 4 splits into two conjugate Gaussian primes).

static modified_divmod(a, b)

Divide a by b, rounding the quotient to the nearest Gaussian integer (rather than truncating), so that the remainder has strictly smaller norm than b. Returns q & r, such that a = b * q + r. This is what makes gcd/xgcd below terminate correctly, since Z[i] is a Euclidean domain under the norm only when division rounds to nearest.

static gcd(a, b)

A gcd algorithm for Gaussian integers. Returns the greatest common divisor of a & b.

This function implements the Euclidean algorithm for Gaussian integers.

static xgcd(a, b)

Extended Euclidean algorithm. Returns (g, s, t) such that a*s + b*t == g == gcd(a, b) (up to a unit factor).

static is_associate(a, b)

True iff a and b differ only by a unit factor (a == b*u for one of Z[i]’s four units). Two Gaussian integers that are associates generate the same ideal and share the same factorization up to units, e.g. this is why gcd/xgcd only determine their result up to a unit. By convention, 0 is only an associate of itself.

static is_coprime(a, b)

True iff gcd(a, b) is a unit, i.e., a and b share no common Gaussian-prime factor. Follows the gcd(0, 0) == 0 convention, so is_coprime(0, 0) is False (0 is not a unit).

static divides(a, b)

True iff a divides b exactly (there exists a Gaussian integer q with b == a*q). By convention, 0 divides only 0.

static lcm(a, b)

Least common multiple of two Gaussian integers, computed as a*b // gcd(a, b) (exact, since gcd always divides a*b evenly). Like gcd, this is only well-defined up to multiplication by a unit, Z[i] has four units, so ‘the’ lcm isn’t unique, just as ‘the’ gcd isn’t.

static congruent_modulo(a, b, c)

True iff a is congruent to b modulo c, i.e., iff c divides (a - b). Raises ZeroDivisionError if c == Zi(0, 0), via the underlying % operator (same behavior as gcd/xgcd on a zero modulus).

static crt(residues, moduli)

Chinese Remainder Theorem over the Gaussian integers.

Given pairwise-coprime moduli m_0, …, m_{k-1} in Z[i] and matching residues a_0, …, a_{k-1}, returns a Gaussian integer x such that

x % moduli[j] == residues[j] % moduli[j] for every j

i.e. x is congruent to residues[j] modulo moduli[j] for every j (see congruent_modulo). x is unique modulo M = prod(moduli), the same guarantee the classic integer CRT gives, except that here, as with gcd/xgcd/factor, everything is only determined up to a unit factor, since Z[i]’s four units (see Zi.units) make “the” gcd/product non-unique to begin with.

Method: fold the two-modulus formula in one pair at a time, given x already solving the system for m_0…m_{i-1} (combined so far into M), and a new pair (residues[i], moduli[i]), xgcd(M, moduli[i]) gives Bezout coefficients s, t with M*s + moduli[i]*t == g. Coprimality (required for a solution to exist) means g is a unit, so normalizing s, t by g’s inverse gives M*s + moduli[i]*t == 1 exactly, and x_new = x*t*moduli[i] + residues[i]*s*M (mod M*moduli[i]) satisfies both x_new == x (mod M) and x_new == residues[i] (mod moduli[i]), the standard two-modulus CRT construction. Repeating this for each successive modulus folds all of them into one solution.

Raises ValueError if residues and moduli have different lengths, if moduli is empty, or if the moduli aren’t pairwise coprime. (Detected as soon as some modulus fails to be coprime with the product of the ones already folded in, which, since Z[i] is a UFD, can only happen if it shares a common non-unit factor with one of them individually.) Raises ZeroDivisionError if any modulus is zero.

static factor(z)

Factor a nonzero Gaussian integer into Gaussian primes.

Returns (unit, factors) where unit is one of Zi.units() and factors is a list of (prime, exponent) pairs, such that z == unit * prod(prime ** exponent for prime, exponent in factors) and each prime satisfies Zi.is_gaussian_prime. Raises ValueError for z == 0, since 0 has no factorization.

Method: factor the rational integer N(z) by trial division, then lift each rational prime factor p to its Gaussian-prime form –

• p == 2 (ramified): 1+i, appearing to the same power

  p appears in N(z)

• p == 3 (mod 4) (inert): p itself, a Gaussian prime

• p == 1 (mod 4) (split): a+bi and its conjugate a-bi,

  whose individual exponents in z are found by direct trial division on z (not derivable from N(z) alone, since the two conjugate primes can divide z to different powers)

This is trial division throughout, so it’s fine for the sizes you’d hit interactively, but isn’t meant for cryptographic-size inputs.

classmethod get_unit_symbol()

classmethod set_unit_symbol(symbol)

static random(re_min=-100, re_max=100, im_min=None, im_max=None)

static eye()

static units()

property is_unit

A Gaussian integer is a unit iff it has norm 1 (equivalent to, but cheaper than, checking membership in Zi.units()).

static two()