Number Theory

with Mathematica at UMBC

Contents

1. Integer Operations
2. Polynomial Operations
3. Gaussian Integer Operations
4. Finite Field Operations

The Mathematica programming language has basic commands and subroutines which implement all basic number theory (and many other things). A general introduction to Mathematica use and how Mathematica can be accessed at UMBC can be found in a separate document.

Mathematica supports the use of integers of arbitrary length and a number of other basic data types such as polynomials.

Integer Operations

The basic arithmetic operations, +, -, *, /, are available from the keyboard. Note that the division operator returns a quotient (eg 7/2 returns 7/2) so the answer should be truncated with the Floor function (eg Floor(7/2) returns 3). The modular reduction operator is represented by the Mod command (eg Mod[7,2] returns 1). Exponentiation is represented with the ^ symbol.

Examples:

• Mod[8 + 7, 13]
  (returns an answer of 2)
• Mod[5 * 4, 13]
  (returns an answer of 7)
• Floor(7 / 2);
  (returns an answer of 3)
• 3^2;
  (returns an answer of 9)

In addition to the basic arithmetic operations for integers Mathematica implements gcd and the extended gcd operations as basic functions:

Examples:
• GCD[15,6]
  (returns an answer of 3)
• ExtendedGCD[23,7]
  (returns an answer of {1, {-3, 10}}, as 23*(-3)+7*10=1)

Efficient modular exponentiation (the Russian Peasant algorithm) is implemented with the PowerMod command, so
PowerMod[2, 1236, 1237]
returns the value 1.

Factoring and primality testing are implemented with the FactorInteger and PrimeQ commands. Examples of their use are
FactorInteger[123456]
which returns {{2, 6}, {3, 1}, {643, 1}} (interpreted as 2^6*3*6 43) and the command
PrimeQ[643]
which returns the value True.

Polynomial Operations

Polynomials are represented using the usual arithmetic operations. Thus, the polynomial 2x³+5x²-x+2 is typed in as 2*x^3+5*x^2-x+2.

Polynomials are manipulated and combined with the same basic operations as are used on integers, +, -, *, ^. Division is done with the PolynomialQuotient[], PolynomialRemainder[] and PolynomialMod[] commands. Multiplication and exponentiation operations are left unevaluated unless the Expand[] command is used to force expansion and evaluation.

Examples:

• (x^2+2*x+1)+(x+5)
  (returns an answer of x²+3x+6)
• (x^2+2*x+1)*(x+5)
  (returns an unevaluated answer of (x²+2x+1)*(x+5))
• Expand[(x^2+2*x+1)*(x+5)]
  (returns an answer of x³+7x²+11x+5
• Expand[(x+1)^2]
  (returns an answer of x²+2x+1)
• PolynomialQuotient[x^2+3,x+1,x]
  (returns the quotient of the two polynomials w/ variable "x", x-1)
• PolynomialMod[x^2+3,x+1]
  (reduces the first polynomial mod the second, returning 4)
• PolynomialMod[x^2+3,{2, x+1}]
  (reduces the first polynomial mod the others, returning 0)

The Euclidean and for polynomials is implemented with the PolynomialGCD. While the Mathematica kernel does not have an extended Euclidean algorithm for polynomials the package "Algebra`PolynomialExtendedGCD`" implements one. Polynomials are factored with the Factor command.

Examples:
• PolynomialGCD[x^3+2*x^2+x+2,x^2+5*x+6]
  (returns an answer of x+2)
• Factor[x^3+2*x^2+x+2]
  (returns an answer of (x+2)(x²+1))

Some of these commands can also be used over a ground field When working with polynomials over a ground field other than the integers or rationals. This is implemented with the Modulus and Extension attributes:

• Factor[x^2+3*x+3, Modulus->7] # Factor with coefficients mod 7

Gaussian Integer Operations

Simple operations on Gaussian Integers can be performed with the usual operations and with the GaussianIntegers option for the FactorInteger, PrimeQ and Factor functions.
In[1]:= a = 3+6I; b = 2-I
In[2]:= n = a*b
In[3]:= PrimeQ[n,GaussianIntegers->True]
In[4]:= FactorInteger[n,GaussianIntegers->True]

Finite Field Operations

The newer versions of Mathematica implement the basics of finite fields with the package Algebra`FiniteFields`. This is well documented on the site [ http://reference.wolfram.com].

In the interrum I wrote the package FinFld.ma to implement operations in finite fields. I still prefer this package for various reasons over the standard Mathematica package. Below is a short example of its use, but there are a number of functions not shown in this example. Look at the source to see examples of their use.

     In[1]:= << FinFld.ma
       {CreateFinFld,ElementFinFld,FinFld,ModFinFld,PlusFinFld,...}
       >    have been defined in package FinFld.
     In[2]:= gf16=CreateFinFld[x^4+x+1,x,2]
     Out[2]= GF(2^4)
     In[3]:= a = ElementFinFld[x,gf16]
     Out[3]= (x)
               GF(2^4)
     In[4]:= a+a
     Out[4]= (0)
               GF(2^4)
     In[5]:= a^15
     Out[5]= (1)
               GF(2^4)
     In[6]:= a^(-1)
     Out[6]= (1 + x^3)
                     GF(2^4)