arithmoi-0.9.0.0: Efficient basic number-theoretic functions.

Copyright(c) 2018 Alexandre Rodrigues Baldé
LicenseMIT
MaintainerAlexandre Rodrigues Baldé <alexandrer_b@outlook.com>
Safe HaskellNone
LanguageHaskell2010

Math.NumberTheory.Quadratic.EisensteinIntegers

Contents

Description

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

Synopsis

Documentation

data EisensteinInteger Source #

An Eisenstein integer is a + bω, where a and b are both integers.

Constructors

(:+) infix 6 

Fields

Instances
Eq EisensteinInteger Source # 
Instance details

Defined in Math.NumberTheory.Quadratic.EisensteinIntegers

Num EisensteinInteger Source # 
Instance details

Defined in Math.NumberTheory.Quadratic.EisensteinIntegers

Ord EisensteinInteger Source # 
Instance details

Defined in Math.NumberTheory.Quadratic.EisensteinIntegers

Show EisensteinInteger Source # 
Instance details

Defined in Math.NumberTheory.Quadratic.EisensteinIntegers

Generic EisensteinInteger Source # 
Instance details

Defined in Math.NumberTheory.Quadratic.EisensteinIntegers

Associated Types

type Rep EisensteinInteger :: Type -> Type #

NFData EisensteinInteger Source # 
Instance details

Defined in Math.NumberTheory.Quadratic.EisensteinIntegers

Methods

rnf :: EisensteinInteger -> () #

Euclidean EisensteinInteger Source # 
Instance details

Defined in Math.NumberTheory.Quadratic.EisensteinIntegers

UniqueFactorisation EisensteinInteger Source #

See the source code and Haddock comments for the factorise and isPrime functions in this module (they are not exported) for implementation details.

Instance details

Defined in Math.NumberTheory.Quadratic.EisensteinIntegers

type Rep EisensteinInteger Source # 
Instance details

Defined in Math.NumberTheory.Quadratic.EisensteinIntegers

type Rep EisensteinInteger = D1 (MetaData "EisensteinInteger" "Math.NumberTheory.Quadratic.EisensteinIntegers" "arithmoi-0.9.0.0-E3bSyM9N8uIFxgJyxrBJhq" False) (C1 (MetaCons ":+" PrefixI True) (S1 (MetaSel (Just "real") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Integer) :*: S1 (MetaSel (Just "imag") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Integer)))

ω :: EisensteinInteger Source #

The imaginary unit for Eisenstein integers, where

ω == (-1/2) + ((sqrt 3)/2)ι == exp(2*pi*ι/3)

and ι is the usual imaginary unit with ι² == -1.

conjugate :: EisensteinInteger -> EisensteinInteger Source #

Conjugate a Eisenstein integer.

norm :: EisensteinInteger -> Integer Source #

The square of the magnitude of a Eisenstein integer.

associates :: EisensteinInteger -> [EisensteinInteger] Source #

Produce a list of an EisensteinInteger's associates.

ids :: [EisensteinInteger] Source #

List of all Eisenstein units, counterclockwise across all sextants, starting with 1.

Primality functions

findPrime :: Prime Integer -> Prime EisensteinInteger Source #

Find an Eisenstein integer whose norm is the given prime number in the form 3k + 1 using a modification of the Hermite-Serret algorithm.

The maintainer Andrew Lelechenko derived the following:

  • Each prime of the form 3n + 1 is actually of the form 6k + 1.
  • One has (z + 3k)^2 ≡ z^2 + 6kz + 9k^2 ≡ z^2 + (6k + 1)z - z + 9k^2 ≡ z^2 - z + 9k^2 (mod 6k + 1).

The goal is to solve z^2 - z + 1 ≡ 0 (mod 6k + 1). One has:

  1. z^2 - z + 1 ≡ 0 (mod 6k + 1)
  2. z^2 - z ≡ -1 (mod 6k + 1)
  3. z^2 - z + 9k^2 ≡ 9k^2 - 1 (mod 6k + 1)
  4. (z + 3k)^2 ≡ 9k^2 - 1 (mod 6k + 1)
  5. z + 3k = sqrtsModPrime(9k^2 - 1) (mod 6k + 1)
  6. z = (sqrtsModPrime(9k^2 - 1) (mod 6k + 1)) - 3k

For example, let p = 7, then k = 1. Square root of 9*1^2-1 ≡ 1 (mod 7), and z = 1 - 3*1 = -2 ≡ 5 (mod 7).

Truly, norm (5 :+ 1) = 25 - 5 + 1 = 21 ≡ 0 (mod 7).

primes :: [Prime EisensteinInteger] Source #

An infinite list of Eisenstein primes. Uses primes in Z to exhaustively generate all Eisenstein primes in order of ascending norm.

  • Every prime is in the first sextant, so the list contains no associates.
  • Eisenstein primes from the whole complex plane can be generated by applying associates to each prime in this list.