Module mvpoly::utils

This module contains functions to work with prime numbers and to compute dimension of multivariate spaces

Structs

• PrimeNumberGenerator

Functions

• compute_all_two_factors_decomposition
  Compute all the possible two factors decomposition of a number n. It uses an cache where previous values have been computed. For instance, if n = 6, the function will return [(1, 6), (2, 3), (3, 2), (6, 1)]. The cache might be used to store the results of previous computations. The cache is a hashmap where the key is the number and the value is the list of all the possible two factors decomposition. The hashmap is updated in place. The third parameter is a precomputed list of prime numbers. It is updated in place in case new prime numbers are generated.
• compute_indices_nested_loop
  Compute the list of indices to perform N nested loops of different size each, whose sum is less than or equal to an optional upper bound. In other words, if we have to perform the 3 nested loops:
• get_mapping_with_primes
  Build mapping from 1..N to the first N prime numbers. It will be used to encode variables as prime numbers For instance, if N = 3, i.e. we have the variable $x_1, x_2, x_3$, the mapping will be [1, 2, 3, 2, 3, 5] The idea is to encode products of variables as products of prime numbers and then use the factorization of the products to know which variables must be fetched while computing a product of variables
• is_prime
  Naive implementation checking if n is prime You can also use the structure PrimeNumberGenerator to check if a number is prime using
• naive_prime_factors
  Given a number n, return the list of prime factors of n, with their multiplicity The first argument is the number to factorize, the second argument is the list of prime numbers to use to factorize the number The output is a list of tuples, where the first element is the prime number and the second element is the multiplicity of the prime number in the factorization of n.