This file documents the python interface to the GNU multiple precision arithmetic library. See Overview (The GMP Manual).

Copyright © 1996 Niels Möller

Permission is granted to make and distribute verbatim copies of this manual provided the copyright notice and this permission notice are preserved on all copies.

Permission is granted to copy and distribute modified versions of this manual under the conditions for verbatim copying, provided that the entire resulting derived work is distributed under the terms of a permission notice identical to this one.

Permission is granted to copy and distribute translations of this manual into another language, under the above conditions for modified versions, except that this permission notice may be stated in a translation approved by the Foundation.

The Python GMP module
*********************

Introduction
************

The python module gmp is an interface to GMP library routines for arbitrary large integer numbers. The library can also handle rational numbers and arbitrary precision floats, but this module can not.

Comments and bug-reports can be sent to the author, Niels Möller <nisse@lysator.liu.se>.

The manual is written for gmpmodule version 0.95.

Why use GMP?
============

There's mainly two reasons you may want to use gmp integer objects instead of ordinary long python integers.

  * In many cases, gmp is much more efficient. For example modular exponentiation is an order of magnitude faster with GMP on the machines I have tried.

  * The gmp module contains some additional functions, for example fac, gcdext and is_prime that you may find handy.

Installing
**********

I assume that you already have Python installed. The instructions in this document describes installation with python version 1.3, but later versions should not be very different.

First, you have to install the GNU Multiple Precision Library, version 2.0 or better. As of this writing, the latest version is 2.0.2, avilable at any GNU mirror, for example as ftp://ftp.lysator.liu.se/pub/gnu/gmp-2.0.2.tar.gz. Unpack it and follow the installation instructions.

Copy the file gmpmodule.c into the Modules directory in the Python source tree. Then you have to edit the Setup file in the same directory. Add two lines

     GMP=/usr/local          # directory prefix used when installing GMP
     gmp gmpmodule.c -I$(GMP)/include -L$(GMP)/lib -lgmp

It's a good idea to comment out the obsolete mpz module from the Setup file at the same time.

Basic GMP usage
***************

Construction
============

There's only one constructor, mpz, that can take different types and number of arguments.
 -- Function: mpz, number
 -- Function: mpz, digits, base
 -- Function: mpz, string
     Possible arguments are

       * NUMBER may be an int, long or a mpz object.

       * DIGITS is a string of digits in BASE. Possible bases are the numbers 2 -- 36, inclusive.

       * STRING is a string interpreted as digits in base 256, least significant octet first.

For the reverse operations, use the digits() and binary() methods (see Methods).

Basic arithmetic
================

The standard arithmetic operations can be used for mpz numbers the same way as ordibary python integers. Arguments are converted to mpz objects as needed. The operations are +, -, *, /, %, &, |, ^, abs, divmod, int, hex, long, oct, pow, repr and str.

The formatting conventions for oct and hex are non-optimal, and might change in the future. I recommend using the digits() method instead.

More methods and functions
**************************

Some of the features of the gmp module are available as methods of mpz objects, some as functions, and many as both methods and functions. In the latter case, arguments are converted to mpz objects when needed.

 -- Function: binary NUMBER
 -- Method: binary
     Converts the number to a string of base 256 digits, least significant octet first. The returned value is suitable as argument to the constructor mpz (see Basic usage).

 -- Function: digits (NUMBER [BASE])
 -- Method: digits [BASE]
     Converts the number to a string of digits, in the indicated base. Possible bases are 2 -- 36 inclusive. BASE zero or omitted is equivalent to 10. This function is the inverse to the two arg form of the mpz constructor (see Basic usage).

 -- Function: divm A B M
     Computes X such that B * X = A (modulo M). If B is not invertible modulo M a ZeroDivisionError is raised.

 -- Function: fac I
     Computes the factorial of I, where I must be a (short) int.

 -- Function: gcd M N
     Returns the greatest common divisor of the numbers M and N.

 -- Function: gcdext M N
     Returns the a tuple (G, S, T) such that G is the greatest common divisor of the numbers M and N, and G = S * M + T * N.

 -- Function: is_square NUMBER
 -- Method: is_square
     Returns 1 if and only if NUMBER is a square, and 0 otherwise.

 -- Function: is_prime (NUMBER [COUNT])
 -- Method: is_prime [COUNT]
     Returns 1 if NUMBER is probably prime, and 0 otherwise. The meaning of probably depends on the COUNT argument. Default is 25, and the larger the COUNT value, the more thoroughly the NUMBER is investigated.

 -- Function: set_debug LEVEL
     Set the debug level. The previous debug level is returned. Nonzero level turns debug output on, zero turns it off.

 -- Function: sqrt NUMBER
 -- Method: sqrt
     Computes the greatest integer less than or equal to the square root of NUMBER, which must be non-negative.

 -- Function: sqrtrem number
 -- Method: sqrtrem
     Similar to the previous function. Returns a tuple (X, REM), where X is greatest integer less than or equalt to the square root, and REM = NUMBER - X².