Metadata-Version: 2.4
Name: py3-gmp
Version: 1.0
Summary: Python wrapper for GNU MP library
Author-email: Yves Legrandgérard <ylg@irirf.fr>
Maintainer-email: Yves Legrandgérard <ylg@irif.fr>
License-Expression: MIT
Project-URL: Documentation, https://py3-gmp.readthedocs.io
Keywords: arithmetic,integers,multiple precision
Classifier: Development Status :: 5 - Production/Stable
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: C
Classifier: Operating System :: POSIX :: BSD :: FreeBSD
Classifier: Operating System :: POSIX :: Linux
Classifier: Operating System :: POSIX
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.11
Description-Content-Type: text/x-rst
License-File: LICENSE
Dynamic: license-file

.. role:: C(code)
    :language: C
    :class: highlight

.. role:: Py(code)
    :language: python
    :class: highlight

.. role:: Bash(code)
    :language: console
    :class: highlight

=====================
Python Module py3-gmp
=====================

This Python module is an encapsulation of the `GNU MP library
<GMPLib_>`__. 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 :C:`mpz_t`). It is planned to integrate rational (i.e.,
   objects of C type :C:`mpq_t`) and floating-point (i.e., objects of
   C type :C:`mpf_t`) numbers in a future version.

The complete documentation for *py3-gmp* module can be found `here
<PyGMPDoc_>`__.

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:

.. code:: console

   # 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:

.. code:: console

   $ 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:

.. code:: console

   (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
<GMPDoc_>`__.

.. admonition:: Error management

   Errors generated by the GNU MP library via the :C:`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 :Py:`mpz` class which encapsulates its
equivalent :C:`mpz_t` in the GNU MP library.

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

   * :C:`mpz_probab_prime_p(z, 24)` :math:`\Rightarrow`
     :Py:`z.probab_prime_p(24)` [:Py:`mpz` method]
   * :C:`mpz_gcd(g, z1, z2)` :math:`\Rightarrow`
     :Py:`g = gcd(z1, z2)` [:Py:`gmp` method]

Creation and initialization
...........................

To create an instance of :Py:`mpz`:

.. code-block:: Python

   >>> 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:

.. code-block:: Python

   >>> 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 :Py:`mpz` objects. Furthermore, the two types can
be mixed. Let's look at some examples:

.. code-block:: Python

   >>> 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: :Py:`divmod`, :Py:`pow`, etc.

.. code-block:: Python

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

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

   .. code-block:: Python

      >>> 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: :Py:`+=`, :Py:`-=`, :Py:`*=`, etc.

Number Theoretic Functions
..........................

These functions from the GNU MP library are implemented either as a
method of an :Py:`mpz` object, or as a method of the :Py:`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:

.. code-block:: Python

   >>> 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
<PyGMPDoc_>`__.

Bitwise Operations
..................

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

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

Comparisons and Booleans
........................

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

Instructions such as :Py:`if x:` and :Py:`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 :C:`SIGFPE` (*Floating Point Error*) signal following a
fatal error (division by zero, for example), the :Py:`gmp` module
captures this signal and raises an appropriate exception **without
aborting** the Python interpreter. Let's look at an example:

.. code-block:: Python

   >>> 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: :Py:`GMPErrUnsupportedArgument`,
:Py:`GMPErrInvalidArgument` and :Py:`GMPErrMPZOverflow`.

Two examples
^^^^^^^^^^^^
.. _genrsakeys:

Generating RSA keys
...................

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

.. code-block:: Python

   >>> 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
:math:`n`: :math:`\phi(n)=(p-1)(q-1)` and then the inverse :math:`d`
of :math:`e` modulo :math:`\phi(n)` (private part of RSA key).

.. code-block:: Python

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

For example, to encrypt the integer :math:`i=12345` with this key:

.. code-block:: Python

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

And to decrypt:

.. code-block:: Python

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

Lucas–Lehmer primality test
...........................

The Lucas–Lehmer test is a primality test for Mersenne numbers
(:math:`M_p=2^p-1` where :math:`p` is a prime number). This test is
described `here <LLTest_>`__.

.. code-block:: Python

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

.. _GMPDoc: https://gmplib.org/gmp-man-6.3.0.pdf
.. _GMPLib: https://gmplib.org
.. _LLTest: https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test
.. _PyGMPDoc: https://py3-gmp.readthedocs.io
