Math.NumberTheory.GaussianIntegers

This module exports functions for manipulating Gaussian integers, including computing their prime factorisations.

Documentation

data GaussianInteger

A Gaussian integer is a+bi, where a and b are both integers.

Constructors

(:+) infix 6

Fields

• real :: !Integer
• imag :: !Integer

Instances

Eq GaussianInteger

Methods

(==) :: GaussianInteger -> GaussianInteger -> Bool

(/=) :: GaussianInteger -> GaussianInteger -> Bool

Num GaussianInteger

Methods

(+) :: GaussianInteger -> GaussianInteger -> GaussianInteger

(-) :: GaussianInteger -> GaussianInteger -> GaussianInteger

(*) :: GaussianInteger -> GaussianInteger -> GaussianInteger

negate :: GaussianInteger -> GaussianInteger

abs :: GaussianInteger -> GaussianInteger

signum :: GaussianInteger -> GaussianInteger

fromInteger :: Integer -> GaussianInteger

Show GaussianInteger

Methods

showsPrec :: Int -> GaussianInteger -> ShowS

show :: GaussianInteger -> String

showList :: [GaussianInteger] -> ShowS

UniqueFactorisation GaussianInteger

Methods

unPrime :: Prime GaussianInteger -> GaussianInteger

factorise :: GaussianInteger -> [(Prime GaussianInteger, Word)]

type Prime GaussianInteger

type Prime GaussianInteger

ι :: GaussianInteger

The imaginary unit, where

ι .^ 2 == -1

conjugate :: GaussianInteger -> GaussianInteger

Conjugate a Gaussian integer.

norm :: GaussianInteger -> Integer

The square of the magnitude of a Gaussian integer.

divModG :: GaussianInteger -> GaussianInteger -> (GaussianInteger, GaussianInteger)

Simultaneous div and mod.

divG :: GaussianInteger -> GaussianInteger -> GaussianInteger

Gaussian integer division, truncating toward negative infinity.

modG :: GaussianInteger -> GaussianInteger -> GaussianInteger

Gaussian integer remainder, satisfying

(x `divG` y)*y + (x `modG` y) == x

quotRemG :: GaussianInteger -> GaussianInteger -> (GaussianInteger, GaussianInteger)

Simultaneous quot and rem.

quotG :: GaussianInteger -> GaussianInteger -> GaussianInteger

Gaussian integer division, truncating toward zero.

remG :: GaussianInteger -> GaussianInteger -> GaussianInteger

Gaussian integer remainder, satisfying

(x `quotG` y)*y + (x `remG` y) == x

(.^) :: Integral a => GaussianInteger -> a -> GaussianInteger infixr 8

Raise a Gaussian integer to a given power.

isPrime :: GaussianInteger -> Bool

Compute whether a given Gaussian integer is prime.

primes :: [GaussianInteger]

An infinite list of the Gaussian primes. Uses primes in Z to exhaustively generate all Gaussian primes, but not quite in order of ascending magnitude.

gcdG :: GaussianInteger -> GaussianInteger -> GaussianInteger

Compute the GCD of two Gaussian integers. Enforces the precondition that each integer must be in the first quadrant (or zero).

gcdG' :: GaussianInteger -> GaussianInteger -> GaussianInteger

Compute the GCD of two Gauss integers. Does not check the precondition.

findPrime :: Integer -> GaussianInteger

Find a Gaussian integer whose norm is the given prime number. Checks the precondition that p is prime and that p mod 4 /= 3.

findPrime' :: Integer -> GaussianInteger

Find a Gaussian integer whose norm is the given prime number. Does not check the precondition.

factorise :: GaussianInteger -> [(GaussianInteger, Int)]

Compute the prime factorisation of a Gaussian integer. This is unique up to units (+- 1, +- i).