Number Theory

with Python

Contents

1. Integer Operations
2. Number Theory Operations
3. Gaussian Integer Operations
4. Polynomial Operations
5. Finite Field Operations

1. Packages for Number Theory in Python
2. References & Links

The Python programming language has basic commands which implement integer arithmetic. More involved number theory will require us to write short programs and modules in Python. A general introduction to Python use and where it can be found/installed at UMBC can be found in a separate document.

A particular strength of Python for number theory is its native support for arbitrary sized integers. These numbers are entered by writing the number followed by the letter "L" (for example 1234512L). Starting with Python 2.x there is an automatic conversion from regular integers to long integers when the size of the number is large enough.

1. Integer Operations

The basic arithmetic operations, +, -, *, /, are available from the keyboard. Note that when used with integers, the division operator returns the greatest integer less than the exact result. (Note that this is done consistently, even for negative values - this differs from many programming languages.) The modular reduction operator is represented by the % operator (eg 7 % 2 returns 1. Again, this differs from many languages in that, if the modulus is positive the result is always positive.) Exponentiation is represented with the ** symbol. The pow() function can be used for exponentiation if called with two parameters, or efficient modular exponentiation if called with three parameters. (pow(a,b,c) returns the same result as (a**b % c), but is much more efficient.)

Examples:

• (8 + 7) % 13;
  (returns an answer of 2)
• (5 * 4) % 13;
  (returns an answer of 7)
• floor(7 / 2);
  (returns an answer of 3)
• 3**2;
  (returns an answer of 9)
• pow(2,6,11);
  (returns an answer of 9)

[There is a fine point with the division operation which may become important with Python 3.0. Currently the "/" operation on integers returns the floor of the quotient. In future it may be possible to use "/" to produce the floating point quotient, and "//" to produce the floor of the quotient. A full treatment is in PEP 238.]

2. Number Theory Operations

Beyond the basic arithmetic operations Python has few natively implemented number theory functions. It is easy to write a Python module which will implement these functions though.

I have also written a simple package which implements a variety of integer number theory operations in Python. This package is available here. Once the source is downloaded to your working directory it can be loaded with the command "import numbthy". An simple example of use is:

	>>> import numbthy
	>>> numbthy.__doc__  # Print the module documentation
	>>> numbthy.gcd(123456,987654)
	6
	>>> numbthy.powmod(3,1234,1237) # Compute 3**1234 mod 1237
	275
	>>> from numbthy import * # Allow direct use of functions
	>>> isprime(1237)  # Pseudoprime test (currently Fermat test)
	True
	>>> factors(12345678) # Simple factorization (currently Pollard Rho)
	[2, 3, 3, 47L, 14593L]
	

Pointers to several other number theory modules written in Python are available in the section Packages for Number Theory in Python.

3. Gaussian Integer Operations

Python implements a complex class. This class is implemented based on floating point values, so we re-implement it as a Python class, requiring at least Python 2.x. The Python source for this class is available here.

An example of the use of the Gaussian Integers class is here:

	>>> from gaussint import *
	>>> a = GaussInt(1,2)
	>>> m = GaussInt(7,2)
	>>> a + m
	(8 + 4i)
	>>> a * m
	(3 + 16i)
	>>> 5*a  # Multiply an integer times a GaussInt
	(5 + 10i)
	>>> a.powmod(12,m) # Compute a**12 mod m
	(-2 + 2i)
	>>> GaussInt(-2544,1788).xgcd(GaussInt(2241,5238))
	((21 + -12i), (148 + 168i), (73 + -98i))
	# So (21-12i) is the gcd of (-2544+1788i) and (2241+5238i)
	# and (21-12i) = (-2544+1788i)(148+168i) + (2241+5238i)(73-98i)
	# We check this:
	>>> GaussInt(-2544,1788)*GaussInt(148,168) + GaussInt(2241,5238)*GaussInt(73,-98)
	(21 + -12i)
	

4. Polynomial Operations

5. Finite Field Operations

A. Packages for Number Theory in Python

A number of authors have implemented packages for number theory operations in Python. A partial list is:

• Elementary Number Theory Python Module from Chap 7 of Elementary Number Theory by William Stein, Harvard Univ. Implements basic operations with integers - gcd,
  [http://modular.fas.harvard.edu/ent/ent_py]
• NZMATH - A Python-based number theory oriented calculation system developed at Tokyo Metropolitan University. Appears to implement classes for integers, rational numbers, polynomials and rings.
  [http://tnt.math.metro-u.ac.jp/nzmath/]
• PariPython - A Python interface to the powerful PARI/GP number theory library, which is written in C.
  [http://www.fermigier.com/fermigier/PariPython/readme.html]

I have also written a simple package which implements a variety of integer number theory operations in Python. This package is available here. Once the source is downloaded to your working directory it can be loaded with the command "import numbthy". An simple example of use is:

	>>> import numbthy
	>>> numbthy.gcd(123456,987654)
	6
	>>> numbthy.powmod(3,1234,1237) # Compute 3**1234 mod 1237
	275
	>>> from numbthy import * # Allow direct use of functions
	>>> isprime(1237)  # Pseudoprime test (currently Fermat test)
	True
	>>> factors(12345678) # Simple factorization (currently Pollard Rho)
	[2, 3, 3, 47L, 14593L]
	

B. References & Links

• Computations in Number Theory Using Python: A Brief Introduction by Jim Carlson, Univ of Utah [www.math.utah.edu/~carlson]
• Elementary Number Theory Python Module from Chap 7 of Elementary Number Theory by William Stein, Harvard Univ [http://modular.fas.harvard.edu/ent/ent_py]