Copyright	(c) 2016 Chris Fredrickson Google Inc.
License	MIT
Maintainer	Chris Fredrickson <chris.p.fredrickson@gmail.com>
Safe Haskell	Safe-Inferred
Language	Haskell2010

Math.NumberTheory.Quadratic.GaussianIntegers

Description

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

Synopsis

data GaussianInteger = (:+) {
- real :: !Integer
- imag :: !Integer
}
ι :: GaussianInteger
conjugate :: GaussianInteger -> GaussianInteger
norm :: GaussianInteger -> Integer
primes :: Infinite (Prime GaussianInteger)
findPrime :: Prime Integer -> Prime GaussianInteger

Documentation

data GaussianInteger Source #

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

Constructors

(:+) infix 6
Fields real :: !Integer imag :: !Integer

Instances

Instances details

UniqueFactorisation GaussianInteger Source #
Instance details Defined in Math.NumberTheory.Quadratic.GaussianIntegers Methods factorise :: GaussianInteger -> [(Prime GaussianInteger, Word)] Source # isPrime :: GaussianInteger -> Maybe (Prime GaussianInteger) Source #
Generic GaussianInteger Source #
Instance details Defined in Math.NumberTheory.Quadratic.GaussianIntegers Associated Types type Rep GaussianInteger :: Type -> Type # Methods from :: GaussianInteger -> Rep GaussianInteger x # to :: Rep GaussianInteger x -> GaussianInteger #
Num GaussianInteger Source #
Instance details Defined in Math.NumberTheory.Quadratic.GaussianIntegers Methods (+) :: GaussianInteger -> GaussianInteger -> GaussianInteger # (-) :: GaussianInteger -> GaussianInteger -> GaussianInteger # (*) :: GaussianInteger -> GaussianInteger -> GaussianInteger # negate :: GaussianInteger -> GaussianInteger # abs :: GaussianInteger -> GaussianInteger # signum :: GaussianInteger -> GaussianInteger # fromInteger :: Integer -> GaussianInteger #
Show GaussianInteger Source #
Instance details Defined in Math.NumberTheory.Quadratic.GaussianIntegers Methods showsPrec :: Int -> GaussianInteger -> ShowS # show :: GaussianInteger -> String # showList :: [GaussianInteger] -> ShowS #
NFData GaussianInteger Source #
Instance details Defined in Math.NumberTheory.Quadratic.GaussianIntegers Methods rnf :: GaussianInteger -> () #
Eq GaussianInteger Source #
Instance details Defined in Math.NumberTheory.Quadratic.GaussianIntegers Methods (==) :: GaussianInteger -> GaussianInteger -> Bool # (/=) :: GaussianInteger -> GaussianInteger -> Bool #
Ord GaussianInteger Source #
Instance details Defined in Math.NumberTheory.Quadratic.GaussianIntegers Methods compare :: GaussianInteger -> GaussianInteger -> Ordering # (<) :: GaussianInteger -> GaussianInteger -> Bool # (<=) :: GaussianInteger -> GaussianInteger -> Bool # (>) :: GaussianInteger -> GaussianInteger -> Bool # (>=) :: GaussianInteger -> GaussianInteger -> Bool # max :: GaussianInteger -> GaussianInteger -> GaussianInteger # min :: GaussianInteger -> GaussianInteger -> GaussianInteger #
Euclidean GaussianInteger Source #
Instance details Defined in Math.NumberTheory.Quadratic.GaussianIntegers Methods quotRem :: GaussianInteger -> GaussianInteger -> (GaussianInteger, GaussianInteger) # quot :: GaussianInteger -> GaussianInteger -> GaussianInteger # rem :: GaussianInteger -> GaussianInteger -> GaussianInteger # degree :: GaussianInteger -> Natural #
GcdDomain GaussianInteger Source #
Instance details Defined in Math.NumberTheory.Quadratic.GaussianIntegers Methods divide :: GaussianInteger -> GaussianInteger -> Maybe GaussianInteger # gcd :: GaussianInteger -> GaussianInteger -> GaussianInteger # lcm :: GaussianInteger -> GaussianInteger -> GaussianInteger # coprime :: GaussianInteger -> GaussianInteger -> Bool #
Ring GaussianInteger Source #
Instance details Defined in Math.NumberTheory.Quadratic.GaussianIntegers Methods negate :: GaussianInteger -> GaussianInteger #
Semiring GaussianInteger Source #
Instance details Defined in Math.NumberTheory.Quadratic.GaussianIntegers Methods plus :: GaussianInteger -> GaussianInteger -> GaussianInteger # zero :: GaussianInteger # times :: GaussianInteger -> GaussianInteger -> GaussianInteger # one :: GaussianInteger # fromNatural :: Natural -> GaussianInteger #
type Rep GaussianInteger Source #
Instance details Defined in Math.NumberTheory.Quadratic.GaussianIntegers type Rep GaussianInteger = D1 ('MetaData "GaussianInteger" "Math.NumberTheory.Quadratic.GaussianIntegers" "arithmoi-0.13.0.0-LV4QEqFnDk8FOh3Yrp60Gv" 'False) (C1 ('MetaCons ":+" 'PrefixI 'True) (S1 ('MetaSel ('Just "real") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 Integer) :*: S1 ('MetaSel ('Just "imag") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 Integer)))

ι :: GaussianInteger Source #

The imaginary unit, where

ι .^ 2 == -1

conjugate :: GaussianInteger -> GaussianInteger Source #

Conjugate a Gaussian integer.

norm :: GaussianInteger -> Integer Source #

The square of the magnitude of a Gaussian integer.

primes :: Infinite (Prime GaussianInteger) Source #

An infinite list of the Gaussian primes. Uses primes in Z to exhaustively generate all Gaussian primes (up to associates), in order of ascending magnitude.

>>> take 10 primes
[Prime 1+ι,Prime 2+ι,Prime 1+2*ι,Prime 3,Prime 3+2*ι,Prime 2+3*ι,Prime 4+ι,Prime 1+4*ι,Prime 5+2*ι,Prime 2+5*ι]

findPrime :: Prime Integer -> Prime GaussianInteger Source #

Find a Gaussian integer whose norm is the given prime number of form 4k + 1 using Hermite-Serret algorithm.

>>> import Math.NumberTheory.Primes (nextPrime)
>>> findPrime (nextPrime 5)
Prime 2+ι