Copyright	(c) 2016 Chris Fredrickson Google Inc.
License	MIT
Maintainer	Chris Fredrickson <chris.p.fredrickson@gmail.com>
Safe Haskell	None
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

Instance details

Defined in Math.NumberTheory.Quadratic.GaussianIntegers

type Rep GaussianInteger = D1 ('MetaData "GaussianInteger" "Math.NumberTheory.Quadratic.GaussianIntegers" "arithmoi-0.13.2.0-AwCKqZxCaASL4wirVJd5zg" 'False) (C1 ('MetaCons ":+" 'PrefixI 'True) (S1 ('MetaSel ('Just "real") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 Integer) :*: S1 ('MetaSel ('Just "imag") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 Integer)))

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.2.0-AwCKqZxCaASL4wirVJd5zg" '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+ι