The Python GMP Module

An efficient BIGNUM module for Python

Edition 1.0

For version 0.95 of the gmp module Based on version 2.0 of the gmp library

20 August 1996

by Niels Mller

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1996, Niels Mller

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.

The Python gmp module 1

The Python gmp module 1 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 Mller <nisse@lysator.liu.se>.

The manual is written for gmpmodule version 0.95.

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

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

3 Basic gmp usage

3.1 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 Chapter 4 [Methods], page 5).

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

4 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 Chapter 3 [Basic usage], page 4).

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 Chapter 3 [Basic usage], page 4).

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.

Chapter 5: Index 7

5 Index

B

binary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

D

digits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 divm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

F

fac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

G

gcd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 gcdext . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

I

is prime. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 is square . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

M

mpz, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

S

set debug . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 sqrt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 sqrtrem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Table of Contents

The Python gmp module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.1 Why use gmp? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Installing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 Basic gmp usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3.1 Construction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.2 Basic arithmetic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

4 More methods and functions. . . . . . . . . . . . . . . . . . . . . . . 5 5 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7