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, autotools, m4 and gmp installed on your system. For example on Debian:

sudo dnf install diffutils gcc make m4 gmp

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

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.