arithmoi-0.10.0.0: Efficient basic number-theoretic functions.

Copyright (c) 2018 Alexandre Rodrigues Baldé MIT Alexandre Rodrigues Baldé None Haskell2010

Contents

Description

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

Synopsis

# Documentation

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

Constructors

 (:+) infix 6 Fieldsreal :: !Integer imag :: !Integer
Instances
 Source # Instance details Methods Source # Instance details Methods Source # Instance details Methods Source # Instance details MethodsshowList :: [EisensteinInteger] -> ShowS # Source # Instance details Associated Typestype Rep EisensteinInteger :: Type -> Type # Methods Source # Instance details Methodsrnf :: EisensteinInteger -> () # Source # Instance details Methods Source # Instance details Methods Source # Instance details Methods Source # Instance details Methods 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 Methods Source # Instance details type Rep EisensteinInteger = D1 (MetaData "EisensteinInteger" "Math.NumberTheory.Quadratic.EisensteinIntegers" "arithmoi-0.10.0.0-ERYv2VuF0BeGX7OVoZ5V00" False) (C1 (MetaCons ":+" PrefixI True) (S1 (MetaSel (Just "real") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Integer) :*: S1 (MetaSel (Just "imag") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Integer)))

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 a Eisenstein integer.

The square of the magnitude of a Eisenstein integer.

Produce a list of an EisensteinInteger's associates.

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

# Primality functions

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).

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.