Function Repository Resource:

# EisensteinIntegers

Support arithmetic operations for pairs of Eisenstein integers

Contributed by: Daniel Lichtblau
 ResourceFunction["EisensteinIntegers"][n,"operator"] returns the result of applying unary operation "operator" to the Eisenstein integer n. ResourceFunction["EisensteinIntegers"][n1,n2,"operator"] returns the result of applying binary operation "operator" to n1 and n2. ResourceFunction["EisensteinIntegers"][n1,…,ω,"operator"] uses ω to represent the Eisenstein ring extension element .

## Details

The ring of Eisenstein integers is ℤ[ω], where is a primitive third root of unity.
ResourceFunction["EisensteinIntegers"] supports two representations: an Eisenstein integer can be given either as a pair {i1,i2}, which denotes , or as . In the latter case, the symbol used to denote the extension element, ω, must be given explicitly in all operations.
The norm of an Eisenstein integer is defined as the product of the integer with its complex conjugate. The conjugate of ω is .
There are six units in the ring of Eisenstein integers: {±1,±ωω2=(1+ω)}. An Eisenstein integer is a unit if and only if its norm is 1.
Supported unary operations are "Re", "Im", "ReIm", "Conjugate", "Norm", "Abs", "Reciprocal", "UnitQ", "PrimeQ" and "FactorInteger".
The conjugate of ω is ω2. This is equal to -1-ω due to the fundamental identity ω2+ω+1=0. ResourceFunction["EisensteinIntegers"] always reduces by this identity, so ω2 is never used in a result (and is not supported in input).
Supported binary operations are "Plus", "Times", "Power", "Dot", "Quotient", "Remainder", "QuotientRemainder", "AssociatesQ", "DividesQ","IntegerExponent", "GCD" and "ExtendedGCD".
Except where specified otherwise, all supported operations in effect do what the corresponding functions do with ordinary or Gaussian integers.
ResourceFunction["EisensteinIntegers"] supports "Power" when the second argument is an explicit nonnegative integer.
Ordinary multiplication is used in "Dot", that is, no conjugation takes place.
ResourceFunction["EisensteinIntegers"] also supports "ListPlus" and "ListTimes" so one can give a list of arguments for adding or multiplying.
ResourceFunction["EisensteinIntegers"] also supports "PowerMod". The power must be a nonnegative integer. The modulus must be an Eisenstein integer.
ResourceFunction["EisensteinIntegers"] regards the multiplier of the extension element as the "imaginary" part, even though it has both a real and an imaginary component in the complex plane.
The Eisenstein integer a+b ω has norm a2+b2-ab. The absolute value is the square root of the norm.
Unary operations and binary operations that do not use division allow symbolic input—that is, Eisenstein numbers that are not expressed using explicit integers.
The reciprocal operation will in general return an Eisenstein rational rather than an integer. All other operations return integers when given explicit Eisenstein integer inputs.

## Examples

### Basic Examples (6)

Find the norm of an Eisenstein integer:

 In[1]:=
 Out[1]=

Find its conjugate:

 In[2]:=
 Out[2]=

Verify that the norm is the product of the number and its conjugate:

 In[3]:=
 Out[3]=

The absolute value of an Eisenstein number is the same as that of the complex number equivalent:

 In[4]:=
 Out[4]=

Find the reciprocal of an Eisenstein integer:

 In[5]:=
 Out[5]=

Verify that it is the reciprocal:

 In[6]:=
 Out[6]=

Multiply a pair of Eisenstein integers:

 In[7]:=
 Out[7]=

The product cannot be a prime:

 In[8]:=
 Out[8]=

Show that both factors are prime:

 In[9]:=
 Out[9]=

Divide a pair of Eisenstein integers:

 In[10]:=
 Out[10]=

Find the quotient and remainder of a pair of Eisenstein integers:

 In[11]:=
 Out[11]=

Recover the dividend from divisor, quotient and remainder:

 In[12]:=
 Out[12]=

### Scope (6)

Use the ordered pair representation:

 In[13]:=
 Out[13]=

Multiply a pair of Eisenstein numbers with symbolic values for real and imaginary parts:

 In[14]:=
 Out[14]=

Form the dot product of two vectors of Eisenstein integers:

 In[15]:=
 Out[15]=

Repeat, using the list representation for the Eisenstein integers:

 In[16]:=
 Out[16]=

Compute the GCD of a pair of Eisenstein integers:

 In[17]:=
 Out[17]=

Check that it divides both inputs:

 In[18]:=
 Out[18]=

Compute the extended GCD of this pair:

 In[19]:=
 Out[19]=

Show that we recover the GCD from the Bezout relation:

 In[20]:=
 Out[20]=

Check that the GCD is an associate of the common factor used to form the inputs:

 In[21]:=
 Out[21]=

Raise 11-7w to power 20 modulo 14+9w:

 In[22]:=
 Out[22]=

Create some Eisenstein primes:

 In[23]:=
 Out[23]=

No pair are associates:

 In[24]:=
 Out[24]=

Raise these primes to successive powers:

 In[25]:=
 Out[25]=

Take the product of these powers:

 In[26]:=
 Out[26]=

Now factor it:

 In[27]:=
 Out[27]=

Check that each factor after the initial unit is an Eisenstein prime:

 In[28]:=
 Out[28]=

Expand the factors to their specified powers:

 In[29]:=
 Out[29]=

Check that expanding the factorization recovers the product:

 In[30]:=
 Out[30]=

### Neat Examples (2)

The GCD implementation for EisensteinIntegers uses an asymptotically fast method that performs better than the standard Euclidean sequence method:

 In[31]:=
 Out[31]=

Here is a version of the Euclidean sequence method:

 In[32]:=

Time it on the same example:

 In[33]:=
 Out[33]=

Check that the results are equivalent:

 In[34]:=
 Out[34]=

Double the size and repeat the timing:

 In[35]:=
 Out[35]=

Now repeat the Euclidean sequence computation:

 In[36]:=
 Out[36]=

Do this again:

 In[37]:=
 Out[37]=

Again repeat the Euclidean sequence computation:

 In[38]:=
 Out[38]=

Check that the known factor e0 is a divisor of the GCD:

 In[39]:=
 Out[39]=

Show the first 18 powers of 7/6+ω:

 In[40]:=
 Out[40]=

## Version History

• 1.1.1 – 02 June 2021