#include <limits.h>
#include <inttypes.h>
#include <math.h>
#include <gmp.h>
#include "macros.h"
#include "array.h"
#include "tifa_config.h"
Go to the source code of this file.
Data Structures | |
| struct | struct_mult_data_t |
| Ad hoc structure used in the computation of the multiplier to use. More... | |
Defines | |
| #define | _TIFA_FUNCS_H_ |
| #define | LARGEST_MULTIPLIER 97 |
| #define | BITSIZE_LARGEST_MULTIPLIER 7 |
| #define | MAX_IPRIME_IN_MULT_CALC 31 |
| #define | NO_SQRT_MOD_P (UINT32_MAX) |
| #define | NO_SQRT_MOD_P2 (ULONG_MAX) |
Typedefs | |
| typedef struct struct_mult_data_t | mult_data_t |
Equivalent to struct struct_mult_data_t. | |
Functions | |
| uint32_t | most_significant_bit (uint32_t n) |
| Most significant bit of a positive integer. | |
| static uint32_t | floor_log2 (uint32_t n) |
| Floor of logarithm in base 2 of a positive integer. | |
| static uint32_t | ceil_log2 (uint32_t n) |
| Ceil of logarithm in base 2 of a positive integer. | |
| static uint32_t | ceil_log2_mp_limb (mp_limb_t limb) |
Ceil of logarithm in base 2 of a mp_limb_t. | |
| void | find_coprime_base (mpz_array_t *const base, const mpz_t n, const mpz_array_t *const factors) |
| Find a coprime base from a list of factors. | |
| int8_t | kronecker_ui (uint32_t a, uint32_t b) |
| Kronecker symbol restricted to positive simple precision integers. | |
| uint32_t | powm (uint32_t base, uint32_t power, uint32_t modulus) |
| Modular exponentiation restricted to positive simple precision integers. | |
| uint32_t | sqrtm (uint32_t a, uint32_t p) |
| Shanks' algorithm for modular square roots computation. | |
| static unsigned long int | is_square (unsigned long int x) |
| Perfect square detection test. | |
| bool | is_prime (uint32_t n) |
Composition test for uint32_t integers. | |
| unsigned long int | gcd_ulint (unsigned long int a, unsigned long int b) |
| Greatest common divisor for unsigned long int. | |
| unsigned long int | modinv_ui (unsigned long int n, unsigned long int p) |
| Modular inverse for unsigned long int. | |
| unsigned long int | sqrtm_p2 (uint32_t a, uint32_t p) |
| Modular square root modulo the square of a prime. | |
| uint32_t | ks_multiplier (const mpz_t n, const uint32_t size_base) |
| Find best multiplier using the Knuth-Schroeppel function. | |
| uint32_t | hash_rj_32 (const void *const keyptr) |
| Robert Jenkins' 32 bit mix function. | |
| uint32_t | hash_pjw (const void *const keyptr) |
| An hash function for strings. | |
| uint32_t | hash_sfh_ph (const void *const keyptr) |
| The "Super Fast Hash" function By Paul Hsieh. | |
| int | mpz_cmp_func (const void *const mpza, const void *const mpzb) |
Comparison function between two mpz_t. | |
| int | uint32_cmp_func (const void *const uinta, const void *const uintb) |
Comparison function between two uint32_t. | |
| int | string_cmp_func (const void *const stra, const void *const strb) |
| Comparison function between two strings. | |
| int | cmp_mult_data (const void *mda, const void *mdb) |
Comparison function between two mult_data_t. | |
| uint32_t | n_choose_k (uint8_t n, uint8_t k) |
| Binomial coefficient C(n, k) (n choose k). | |
| void | next_subset_lex (uint32_t n, uint32_t k, uint32_t *subset, bool *end) |
| Generate the successor of a fixed cardinal subset from a base set, in lexicographic order. | |
| void | unrank_subset_lex (uint32_t n, uint32_t k, uint32_t r, uint32_t *subset) |
| Generate a fixed cardinal subset from a base set, according to a given rank. | |
| void | unrank_subset_revdoor (uint32_t n, uint32_t k, uint32_t r, uint32_t *subset) |
| Generate a fixed cardinal subset from a base set, according to a given rank. | |
| void | tifa_srand (uint32_t seed) |
| Initializes TIFA's basic pseudo-random generator. | |
| uint32_t | tifa_rand () |
| Returns a pseudo-random integer. | |
Variables | |
| const unsigned short qres_mod_221[221] | MAYBE_UNUSED |
| Quadratic residues mod 221. | |
Definition in file funcs.h.
| #define BITSIZE_LARGEST_MULTIPLIER 7 |
| #define MAX_IPRIME_IN_MULT_CALC 31 |
| #define NO_SQRT_MOD_P (UINT32_MAX) |
| #define NO_SQRT_MOD_P2 (ULONG_MAX) |
| static uint32_t ceil_log2 | ( | uint32_t | n | ) | [inline, static] |
Ceil of logarithm in base 2 of a positive integer.
Returns the value of the ceil of the logarithm (in base 2) of a positive integer in essentially constant time. In other words, it returns the smallest natural i such that 2^i >= n.
| [in] | n | A positive integer. |
n) in base 2. Definition at line 162 of file funcs.h.
References IS_POWER_OF_2_UI, and most_significant_bit().
Referenced by ceil_log2_mp_limb().
| static uint32_t ceil_log2_mp_limb | ( | mp_limb_t | limb | ) | [inline, static] |
Ceil of logarithm in base 2 of a mp_limb_t.
Returns the value of the ceil of the logarithm (in base 2) of a mp_limb_t in essentially constant time. In other words, it returns the smallest natural i such that 2^i >= n.
| [in] | n | A positive integer as an mp_limb_t. |
n) in base 2. Definition at line 180 of file funcs.h.
References ceil_log2().
| int cmp_mult_data | ( | const void * | mda, | |
| const void * | mdb | |||
| ) |
Comparison function between two mult_data_t.
This is a comparison function between two mult_data_t structures passed as pointers to void, according to the criteria set forth in Morrison and Brillhart's paper "A Method of Factoring and the Factorization of F_7" (Mathematics of Computation, vol 29, #129, Jan 1975, pages 183-205).
If a and b are the two underlying mult_data_t structures to compare, it returns:
a.count > b.count a.count < b.count a.count == b.count, returns: a.sum_inv_pi > b.sum_inv_pi a.sum_inv_pi > b.sum_inv_pi a.sum_inv_pi == b.sum_inv_pi, returns:a.multiplier < b.multiplier (Indeed, we prefer smaller multipliers) a.multiplier > b.multiplier a.multiplier > b.multiplier
| [in] | mda | A pointer to the first mult_data_t to compare. |
| [in] | mdb | A pointer to the second mult_data_t to compare. |
mult_data_t. | void find_coprime_base | ( | mpz_array_t *const | base, | |
| const mpz_t | n, | |||
| const mpz_array_t *const | factors | |||
| ) |
Find a coprime base from a list of factors.
Finds a coprime base for the list of factors of n given by the array *factors and stores it in the allocated but uninitialized array base. After invocation, we know that n is smooth on the returned computed base and that all elements of the base are coprime to each other.
The resulting base is obtained:
n (up to the prime multiplicities).base array has not enough room to hold all the coprimes found, it will be resized via a call to resize_mpz_array with ELONGATION extra mpz_t slots to avoid too frequent resizes.
Consecutive invocation of this function with the same base and n but for different factors arrays will build a coprime base for all elements in all the aforementioned factors arrays.
| [in,out] | base | The found coprime base. |
| [in] | n | A positive integer. |
| [in] | factors | A pointer to an array holding some factors of n. |
| [in,out] | A | pointer to the unintialized mpz_array_t to hold the coprime base. |
| static uint32_t floor_log2 | ( | uint32_t | n | ) | [inline, static] |
Floor of logarithm in base 2 of a positive integer.
Returns the value of the floor of the logarithm (in base 2) of a positive integer in essentially constant time. In other words, it returns the greatest natural i such that 2^i <= n.
most_significant_bit.| [in] | n | A positive integer. |
n) in base 2. Definition at line 148 of file funcs.h.
References most_significant_bit().
| unsigned long int gcd_ulint | ( | unsigned long int | a, | |
| unsigned long int | b | |||
| ) |
Greatest common divisor for unsigned long int.
Returns the greatest common divisor of a and b as an unsigned long int.
| [in] | a | An unsigned long int. |
| [in] | b | An unsigned long int. |
a and b. | uint32_t hash_pjw | ( | const void *const | keyptr | ) |
An hash function for strings.
Returns the hash of a C-style character string (passed as a pointer to void) using an hash function attributed to P.J. Weinberger.
| [in] | keyptr | A pointer to the character string to hash. |
| uint32_t hash_rj_32 | ( | const void *const | keyptr | ) |
Robert Jenkins' 32 bit mix function.
Returns the hash of a uint32_t integer (passed as a pointer to void) using Robert Jenkins' 32 bit mix function.
| [in] | keyptr | A pointer to the uint32_t to hash. |
| uint32_t hash_sfh_ph | ( | const void *const | keyptr | ) |
The "Super Fast Hash" function By Paul Hsieh.
Returns the hash of a C-style character string (passed as a pointer to void) using the so-called "SuperFastHash" function By Paul Hsieh.
| [in] | keyptr | A pointer to the character string to hash. |
| bool is_prime | ( | uint32_t | n | ) |
Composition test for uint32_t integers.
Returns false if n is definitely composite. Returns true if n is probably prime.
NMILLER_RABIN iterations preceded with some trial divisions if n is sufficiently small.| [in] | n | The uint32_t to be checked for composition. |
false if n is found to be definitely composite. true otherwise. | static unsigned long int is_square | ( | unsigned long int | x | ) | [inline, static] |
| int8_t kronecker_ui | ( | uint32_t | a, | |
| uint32_t | b | |||
| ) |
Kronecker symbol restricted to positive simple precision integers.
Returns the value of the Kronecker symbol (a/b) where a and b are positive integers.
| [in] | a | A positive integer. |
| [in] | b | A positive integer. |
a/b). | uint32_t ks_multiplier | ( | const mpz_t | n, | |
| const uint32_t | size_base | |||
| ) |
Find best multiplier using the Knuth-Schroeppel function.
Given the size of factor base size_base, returns the "best" multiplier to factor n, using the modified version of the Knuth-Schroeppel function described by Silverman in: "The Multiple Quadratic Sieve".
LARGEST_MULTIPLIER.| [in] | n | The number to factor |
| [in] | size_base | The desired size of the factor base |
| unsigned long int modinv_ui | ( | unsigned long int | n, | |
| unsigned long int | p | |||
| ) |
Modular inverse for unsigned long int.
Returns the modular inverse of n modulo the odd prime p as an unsigned long int.
p must be a positive odd prime, strictly less than LONG_MAX (yes, LONG_MAX and not ULONG_MAX!) and, of course, n % p must be non-null.| [in] | n | An unsigned long int. |
| [in] | p | An odd prime unsigned long int. |
n mod p. | uint32_t most_significant_bit | ( | uint32_t | n | ) |
Most significant bit of a positive integer.
Returns the value of the most significant bit of the integer n in essentially constant time, or in other words, its logarithm in base 2. The returned result is an integer from 0 (the least significant bit) to 31 included (the most significant bit).
| [in] | n | A positive integer. |
n) in base 2. Referenced by ceil_log2(), and floor_log2().
| int mpz_cmp_func | ( | const void *const | mpza, | |
| const void *const | mpzb | |||
| ) |
Comparison function between two mpz_t.
This is a natural order comparison function between two mpz_t elements passed as pointers to void. It returns:
mpz_t is greater than the second one. mpz_t is equal to the second one. mpz_t is less than the second one.mpz_cmp.| [in] | mpza | A pointer to a mpz_t. |
| [in] | mpzb | A pointer to another mpz_t. |
mpz_t. | uint32_t n_choose_k | ( | uint8_t | n, | |
| uint8_t | k | |||
| ) |
Binomial coefficient C(n, k) (n choose k).
Returns the binomial coefficient C(n, k) (i.e n choose k).
Note that this single precision function only returns correct results if the actual value of the binomial coefficient fits in 32 bits.
| [in] | n | |
| [in] | k |
| void next_subset_lex | ( | uint32_t | n, | |
| uint32_t | k, | |||
| uint32_t * | subset, | |||
| bool * | end | |||
| ) |
Generate the successor of a fixed cardinal subset from a base set, in lexicographic order.
Starting with a subset of cardinal k of a base set of cardinal n, generates the subset's successor in the lexicographic order. The new subset is stored in subset and thus overrides the previous one.
Subsets are decribed by an array of length k holding indexes in the interval [1, n].
The first k-subset in the lexicographic order is given by {1, 2, 3, ... k}. After a call to next_subset_lex end is true if and only if the last k-subset has been reached (i.e. the next one will be {1, 2, 3, ... k}).
This is actually algorithm 2.6 from the book "Combinatorial Algorithms - Generation, Enumeration, and Search" by Donald L. Kreher and Douglas Stinson.
| [in] | n | Cardinal of the base set. |
| [in] | k | Cardinal of the subset. |
| in/out] | subset Current subset to be replaced by its successor. | |
| [in] | end | Have we reached the end of the cycle? |
| uint32_t powm | ( | uint32_t | base, | |
| uint32_t | power, | |||
| uint32_t | modulus | |||
| ) |
Modular exponentiation restricted to positive simple precision integers.
Returns (base^power) mod modulus as an unsigned integer.
| [in] | base | The base of the modular exponential. |
| [in] | power | The power of the modular exponential. |
| [in] | modulus | The modulus of the modular exponential. |
base^power) mod modulus. | uint32_t sqrtm | ( | uint32_t | a, | |
| uint32_t | p | |||
| ) |
Shanks' algorithm for modular square roots computation.
Returns the modular square root of a (mod p) (where p is an odd prime) using Shanks' algorithm, that is, returns the positive integer s such that s^2 = a (mod p). If no such integer exists, returns NO_SQRT_MOD_P.
p is not checked by sqrtm. It is the responsability of the caller to check whether p is indeed prime. Failure to assure such a precondition will lead to an infinite loop.| [in] | a | The modular square. |
| [in] | p | The modulus. |
a (mod p) if it exists. NO_SQRT_MOD_P otherwise. | unsigned long int sqrtm_p2 | ( | uint32_t | a, | |
| uint32_t | p | |||
| ) |
Modular square root modulo the square of a prime.
Provided that a verifies 1 <= a < p*p, returns the modular square root of a (mod p*p) (where p is an odd prime) that is, returns a positive integer s such that s^2 = a (mod p*p). If no such integer exists, returns NO_SQRT_MOD_P2.
p*p should be strictly less than LONG_MAX.
The primality of p is not checked by sqrtm_p2. It is the responsability of the caller to check whether p is indeed prime. Failure to assure such a precondition will lead to an infinite loop.
| [in] | a | The modular square. |
| [in] | p | The square root of the modulus. |
a (mod p*p) if it exists. NO_SQRT_MOD_P2 otherwise. | int string_cmp_func | ( | const void *const | stra, | |
| const void *const | strb | |||
| ) |
Comparison function between two strings.
This is a lexicographical order comparison function between two C-style character strings passed as pointers to void. It returns:
strcmp.| [in] | stra | A pointer to a C-style character string. |
| [in] | strb | A pointer to another C-style character string. |
| uint32_t tifa_rand | ( | ) |
Returns a pseudo-random integer.
Returns a pseudo-random integer using TIFA's basic random number generator.
| [in] | seed | The seed as a uint32_t. |
| void tifa_srand | ( | uint32_t | seed | ) |
Initializes TIFA's basic pseudo-random generator.
Initializes TIFA's basic random number generator with a user defined seed.
| [in] | seed | The seed as a uint32_t. |
| int uint32_cmp_func | ( | const void *const | uinta, | |
| const void *const | uintb | |||
| ) |
Comparison function between two uint32_t.
This is a natural order comparison function between two uint32_t elements passed as pointers to void. It returns:
uint32_t is greater than the second one. uint32_t is equal to the second one. uint32_t is less than the second one.| [in] | uinta | A pointer to a uint32_t. |
| [in] | uintb | A pointer to another uint32_t. |
uint32_t. | void unrank_subset_lex | ( | uint32_t | n, | |
| uint32_t | k, | |||
| uint32_t | r, | |||
| uint32_t * | subset | |||
| ) |
Generate a fixed cardinal subset from a base set, according to a given rank.
Starting with a base set of cardinal n, constructs a subset of cardinal k and rank r (in [0, c(n, k)]) where the rank is given by the lexicographic order. The constructed subset is stored in subset and thus overrides the previous data.
Subsets are decribed by an array of length k holding indexes in the interval [1, n].
This is actually algorithm 2.8 from the book "Combinatorial Algorithms - Generation, Enumeration, and Search" by Donald L. Kreher and Douglas Stinson.
| [in] | n | Cardinal of the base set. |
| [in] | k | Cardinal of the subset. |
| [in] | r | Rank of the subset (assuming lexicographic order). |
| [out] | subset | Subset to be returned. |
| void unrank_subset_revdoor | ( | uint32_t | n, | |
| uint32_t | k, | |||
| uint32_t | r, | |||
| uint32_t * | subset | |||
| ) |
Generate a fixed cardinal subset from a base set, according to a given rank.
Starting with a base set of cardinal n, constructs a subset of cardinal k and rank r (in [0, c(n, k)]) where the rank is given by the minimal change order. The constructed subset is stored in subset and thus overrides the previous data.
Subsets are decribed by an array of length k holding indexes in the interval [1, n].
This is actually algorithm 2.12 from the book "Combinatorial Algorithms - Generation, Enumeration, and Search" by Donald L. Kreher and Douglas Stinson.
| [in] | n | Cardinal of the base set. |
| [in] | k | Cardinal of the subset. |
| [in] | r | Rank of the subset (assuming minimal change order). |
| [out] | subset | Subset to be returned. |
| const uint32_array_t first_primes_array MAYBE_UNUSED |
Quadratic residues mod 221.
Quadratic residues mod 315.
Quadratic residues mod 256.
x is a square mod 221 if qres_mod_221[x % 221] == 1.
x is a square mod 256 if qres_mod_256[x % 256] == 1.
x is a square mod 315 if qres_mod_315[x % 315] == 1.
The largest prime in the first_primes array.
first_primes_array is a uint32_array_t wrapper to the array first_primes.
first_primes_array 's alloced field is set to zero. Indeed, first_primes_array is merely a uint32_array_t wrapper for first_primes, and as such, it has no real "alloced" memory. Setting first_primes_array.alloced to 0 will prevent errors if free_mpz_array is inadvertently called on first_primes_array.