Python Module py3-gmp¶

This Python module is an encapsulation of the GNU MP library. With a few exceptions, all the functions (see note below) of this library are available in the py3-gmp module.

Note

Currently, this module only handles integers (i.e., objects of C type mpz_t). It is planned to integrate rational (i.e., objects of C type mpq_t) and floating-point (i.e., objects of C type mpf_t) numbers in a future version.

The complete documentation for py3-gmp module can be found here.

Installation¶

GNU MP library¶

This module can, in principle, be installed on any POSIX system that has the GNU MP library and the <gmp.h> header. The minimum required version of GNU MP library is 6.3.0.

For example, on Debian-based Linux systems, you need to install the following packages:

# apt-get install libgmp10    # library
# apt-get install libgmp-dev  # header

Module py3-gmp¶

The recommended approach is to first create a Python virtual environment:

$ python3 -m venv py3-gmp
$ cd py3-gmp
$ source bin/activate
(py3-gmp) $ python3 -m pip install --upgrade pip setuptools wheel

Next, retrieve the py3-gmp module and build it:

(py3-gmp) $ python3 -m pip install py3-gmp

And you are done…

An overview of the module¶

Let us recall that the GNU MP library is a library for arbitrary precision arithmetic on integers, rational numbers, and floating-point numbers. For a complete description, refer to GNU MP Manual.

Error management

Errors generated by the GNU MP library via the SIGFPE signal are handled in such a way as not to cause the Python interpreter to exit (see Error handling section below).

Quick start¶

The core class is the mpz class which encapsulates its equivalent mpz_t in the GNU MP library.

Renaming of GNU MP library functions

All function names in the GNU MP library are prefixed with mpz_. This prefix is removed in the _gmp.gmpz module, but the suffixes are retained. Thus, for example:

mpz_probab_prime_p(z, 24) \(\Rightarrow\) z.probab_prime_p(24) [mpz method]
mpz_gcd(g, z1, z2) \(\Rightarrow\) g = gcd(z1, z2) [gmp method]

Creation and initialization¶

To create an instance of mpz:

>>> from gmp import *
>>> z = mpz()
>>> print(z)
0 # z is initialized to 0 by default

When creating an instance, it can also be initialized in different ways:

>>> z = mpz(2026) # a Python integer
>>> z = mpz(3.14159) # a Python float
>>> z = mpz('10001011', 2) # a Python string in base 2
>>> t = mpz(1013)
>>> z = mpz(t) # a mpz instance

Arithmetic operators¶

All the arithmetic operators available for Python integers are also available for mpz objects. Furthermore, the two types can be mixed. Let’s look at some examples:

>>> z = mpz(1729); t = mpz(2026)
>>> u = z + t; v = -178 -z; w = t % 27; x = (-z + 5 * t) // 12
>>> print(u, v, w, x)
3755 -1907 1 700

All other standard operators are available: divmod, pow, etc.

>>> print(divmod(567345, z))
(328, 233)
>>> print(pow(z, t, 1765))
116

Tip

There is a restriction regarding the types of the ** operator’s operands. Specifically, z ** n is only defined if z is an mpz object and n is a Python integer that fits in a C unsigned long. However, it is easy to circumvent this restriction:

>>> z = mpz(32)
>>> print(2 ** int(z)) # using operator int()
4294967296

As a consequence of the above, all corresponding in-place operators are therefore available, namely: +=, -=, *=, etc.

Number Theoretic Functions¶

These functions from the GNU MP library are implemented either as a method of an mpz object, or as a method of the gmp module, the criterion depending essentially on the prototype and the parameters of each of them. Here are a few examples to help you understand:

>>> z = mpz(2026)
>>> print(z.rootrem(4))
(6, 730)
>>> t = mpz(1729)
>>> print(gcd(z, t))
1
>>> print(jacobi(z, t))
-1
>>> print(divisible_p(z, 1013))
True

For a complete list of number theoretic functions, see py3-gmp manual.

Bitwise Operations¶

All bitwise operations are also available: x | y, x ^ y, x & y, x << n, x >> n and ~x. The operands x and y are either instances of mpz or ìnt and n is an instance of ìnt that must fit into a C unsigned long.

All the bitwise functions specific to the GNU MP library are also available, such as setbit(), popcount(), etc.

Comparisons and Booleans¶

Let x and y be two objects that are either instances of mpz or int. Then all comparison operations are valid: x < y, x <= y, x > y, x >= y, x == y, x != y.

Instructions such as if x: and if not x: are valid and have their usual meaning.

Random Number Functions¶

See Two examples section below.

Error handling¶

We gently trap errors generated by the GNU MP library. When the latter sends the SIGFPE (Floating Point Error) signal following a fatal error (division by zero, for example), the gmp module captures this signal and raises an appropriate exception without aborting the Python interpreter. Let’s look at an example:

>>> z = mpz(-1); u = mpz()
>>> try:
...     z.sqrt()
... except GMPErrSqrtOfNegative:
...     # Error handling...
>>> try:
...     z // u
... except GMPErrDivisionByZero:
...     # Error handling...
>>> # Python interpreter still alive - no abort()

Three other errors are defined: GMPErrUnsupportedArgument, GMPErrInvalidArgument and GMPErrMPZOverflow.

Two examples¶

Generating RSA keys¶

We will first generate the public key \((n, e)\) where \(n\) will be the product of two 64-bits prime numbers (therefore unrealistic because they are too small) and \(e\) is the Fermat’s number \(F_4=65537\).

>>> randseed_ui()
>>> p = mpz(urandomb_ui(64))
>>> p = p.nextprime()
>>> q = mpz(urandomb_ui(64))
>>> q = q.nextprime()
>>> n, e = p * q, 65537

Let’s now calculate the value of the Euler totient function at \(n\): \(\phi(n)=(p-1)(q-1)\) and then the inverse \(d\) of \(e\) modulo \(\phi(n)\) (private part of RSA key).

>>> phi_n = (p - 1) * (q - 1)
>>> d = invert(e, phi_n)

For example, to encrypt the integer \(i=12345\) with this key:

>>> i = 12345
>>> c = pow(i, e, n)
>>> print(c)
42371417114112030784039967521718236254

And to decrypt:

>>> c = pow(c, d, n)
>>> print(c)
12345

Lucas–Lehmer primality test¶

The Lucas–Lehmer test is a primality test for Mersenne numbers (\(M_p=2^p-1\) where \(p\) is a prime number). This test is described here.

>>> def LL_test(p):
...     if p <= 2 or not p.probab_prime_p():
...         raise TypeError('arg1 must a prime number > 2')
...     s, M_p = mpz(4), 2**int(p) - 1 # <int>**<mpz> is not defined
...     for i in range(1, p - 1): # p has the __index__ method, no need to write int(p)
...         s = (s**2 - 2) % M_p
...     return False if s else True
>>> print(LL_test(mpz(11)))
False # 2**11 - 1 = 23 * 89
>>> print(LL_test(mpz(9941)))
True # 2**9941 - 1 is prime