Crate gmpmee_sys

The gmpmee-sys crate provides Rust FFI bindings to the GMP Modular Exponentiation Extension (GMPMEE), which is a minor extension of GMP. It adds simultaneous modular exponentiation and fixed base modular exponentiation functionality to the set of integer functions (the mpz-functions), as well as special purpose primality testing routines.

The crate is strongly inspired from gmp-mpfr-sys. In particular the file build.rs is copied from this crate, and adapted to the needs of the gmpmee-sys crate. No cache is implemented, since the compilation is quick.

Types

Unlike in the C libraries, the types (e.g. gmpmee_spowm_tab, gmpmee_fpowm_tab) are defined directly as structs, not as single-element arrays.

Using gmpmee-sys

The gmpmee-sys crate is available on crates.io. To use gmpmee-sys in your crate, add it as a dependency inside [Cargo.toml]:

[dependencies]
gmpmee-sys = "0.1"

Building on GNU/Linux

To build on GNU/Linux, simply make sure you have diffutils, gcc, make and m4 installed on your system. For example on Fedora:

sudo dnf install diffutils gcc make m4

Building on macOS

To build on macOS, you need the command-line developer tools. To install them, run the following command in a terminal:

xcode-select --install

Building on Windows

You can build on Windows with the Rust GNU toolchain and an up-to-date MSYS2 installation. Some steps for a 64-bit environment are listed below. (32-bit: Changes for a 32-bit environment are written in brackets like this comment.)

To install MSYS2:

1. Install MSYS2 using the [installer][msys].

2. Launch the MSYS2 MinGW 64-bit terminal from the start menu. (32-bit: Launch the MSYS2 MinGW 32-bit terminal instead.)

3. Install the required tools.

   pacman -S pacman-mirrors
   pacman -S diffutils make mingw-w64-x86_64-gcc

   (32-bit: Install mingw-w64-i686-gcc instead of mingw-w64-x86_64-gcc.)

Then, to build a crate with a dependency on this crate:

1. Launch the MSYS MinGW 64-bit terminal from the start menu. (32-bit: Launch the MSYS2 MinGW 32-bit terminal instead.)
2. Change to the crate directory.
3. Build the crate using cargo.

Licence

The gmpee-sys crate is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. See the full text of the LICENSE for details.

Structs

• gmpmee_fpowm_tab
  Stores a fixed base exponentiation table.
• gmpmee_millerrabin_safe_state
  Stores the states needed for using the Miller-Rabin test for testing for safe-primality.
• gmpmee_millerrabin_state
  Stores state inbetween individual invokations of the Miller-Rabin test and keeps allocated space.
• gmpmee_spowm_tab
  Stores the tables of precomputed products of subsets of the bases. Each table contains the precomputed products for a range of a given width of the bases.

Functions

• gmpmee_fpowm^⚠
  Computes a fixed base exponentiation using the given table and exponent.
• gmpmee_fpowm_clear^⚠
  Frees the memory allocated by table.
• gmpmee_fpowm_init^⚠
  Allocates and initializes a table with the given modulus, block width, and expected exponent bit length.
• gmpmee_fpowm_init_precomp^⚠
  Equivalent to calling gmpmee_fpowm_init and then gmpmee_fpowm_precomp.
• gmpmee_fpowm_precomp^⚠
  Fills the table with precomputed values using the given basis.
• gmpmee_millerrabin_clear^⚠
  Free memory resources allocated for testing.
• gmpmee_millerrabin_init^⚠
  Allocate and initialize Miller-Rabin state using the given integer.
• gmpmee_millerrabin_next_cand^⚠
  Updates the state to correspond to the next larger candidate integer that passes the trial divisions.
• gmpmee_millerrabin_next_rs^⚠
  Searches for the smallest prime larger than the given integer. Primality testing is done using the Miller-Rabin test using randomness from one of GMP’s random sources.
• gmpmee_millerrabin_once^⚠
  Executes one round of the Miller-Rabin test and returns 0 or 1 depending on if the tested integer is deemed to be composite or not.
• gmpmee_millerrabin_reps_rs^⚠
  Executes the Miller-Rabin test using randomness from one of GMP’s random sources. Assumes that the tested integer is greater than three.
• gmpmee_millerrabin_rs^⚠
  Executes a number or repetitions of the Miller-Rabin test using basis derived from the given GMP random source and returns 0 or 1 depending on if the tested integer is deemed to be composite or not.
• gmpmee_millerrabin_safe_clear^⚠
  Free memory allocated in the states.
• gmpmee_millerrabin_safe_init^⚠
  Initialize Miller-Rabin state to be used for safe-primality testing using the given integer.
• gmpmee_millerrabin_safe_next_cand^⚠
  Sets the state to the next candidate integer larger than the most recently tested candidate that passes the trial divisions.
• gmpmee_millerrabin_safe_next_rs^⚠
  Uses gmpmee_millerrabin_safe_rs to find the smallest safe prime larger than the input integer.
• gmpmee_millerrabin_safe_once^⚠
  Executes one round of the Miller-Rabin test and returns 0 or 1 depending on if the tested integer is deemed to not be a safe prime, or a safe prime. Assumes that the tested integer is at least 8.
• gmpmee_millerrabin_safe_reps_rs^⚠
  Executes a safe primality test for the integer used to initialize the given testing state, using randomness from the given GMP’s random source.
• gmpmee_millerrabin_safe_rs^⚠
  Executes several repetitions of the of the Miller-Rabin test and returns 0 or 1 depending on if the tested integer is deemed to not be a safe prime, or a safe prime. The basis elements are derived from the given random number generator.
• gmpmee_millerrabin_safe_trial^⚠
  Performs trial divisions and returns 0 or 1 depending on if the integer is definitely a not a safe prime, or if it could potentially be a safe prime. Assumes that n is at least 8.
• gmpmee_millerrabin_trial^⚠
  Performs trial divisions and returns 0 or 1 depending on if a small factor of the integer has been found or not. Assumes that the input is greater than three.
• gmpmee_spowm^⚠
  Computes a simultaneous exponentiation. Precomputation is performed in blocks of a reasonable width in a single batch.
• mpz_probab_prime_p_next^⚠
  Naive implementation of a search for the next prime test. Based on GMP’s probab_prime_p. Used for debugging.
• mpz_probab_safe_prime_p^⚠
  Naive implementation of a safe-primality test based on GMP’s probab_prime_p. Used for debugging.
• mpz_probab_safe_prime_p_next^⚠
  Naive implementation of a search for the next safe prime test. Based on probab_safe_prime_p. Used for debugging.