Struct number_theory::Mpz

pub struct Mpz { /* private fields */ }

Arbitrary precision integer (Z)

Implementations

impl Mpz

pub fn u_new(limbs: Vec<u64>) -> Self

 use number_theory::Mpz;  // includes arbitrary-precision arithmetic
 use number_theory::Sign; // allows sign
 use number_theory::NumberTheory; // includes methods from NumberTheory trait

 let bignum = Mpz::new(Sign::Positive, vec![5,5]);

 let fortyfour = Mpz::from_u128(44u128);

 let fortyfour_neg = Mpz::from_i128(-44i128);

 let twopow = Mpz::from_u64(128);


 assert_eq!("92233720368547758085", bignum.to_string());
 assert_eq!("44", fortyfour.to_string());
 assert_eq!("-44", fortyfour_neg.to_string());
 assert_eq!("128", twopow.to_string());

Returns a positive x from a big-endian vector representation

pub fn new(sign: Sign, limbs: Vec<u64>) -> Self

Returns a x from a big-endian vector representation and a sign

pub fn unchecked_u_new(limbs: Vec<u64>) -> Self

Returns a positive x from a big-endian vector, this function does not eliminate extraneous leading zeros

pub fn unchecked_new(sign: Sign, limbs: Vec<u64>) -> Self

Returns a x from a big-endian vector and sign, this function does not eliminate extraneous leading zeros

pub fn from_slice(sign: Sign, x: &[u64]) -> Self

Returns x from a big_endian slice and sign

pub fn from_u128(x: u128) -> Self

Return x from u128

pub fn from_i128(x: i128) -> Self

Return x from i128

pub fn from_u64(x: u64) -> Self

Return x from u64

pub fn from_i64(x: i64) -> Self

Return x from i64

pub fn to_u64(&self) -> Option<u64>

Converts to 64-bit unsigned integer if it can fit

pub fn to_i64(&self) -> Option<i64>

Convert to 64-bit signed integer

pub fn to_u32(&self) -> Option<u32>

Converts to 32-bit unsigned integer if it can fit

pub fn to_u128(&self) -> Option<u128>

Converts to 128-bit unsigned integer if it can fit

pub fn to_vector(&self) -> Vec<u64>

Returns the vector representation of n

pub fn rand(len: usize) -> Self

Set an integer between 2^(n-1);2^n

pub fn set_limbs(len: usize, gen: fn() -> u64) -> Self

Creates a integer from limbs generated by a function

pub fn to_string(&self) -> String

Converts n to a radix-10 string

pub fn to_hex_string(&self) -> String

Converts n to a radix-16 string in linear time

pub fn to_radix_vec(&self, radix: u64) -> Vec<u64>

Returns the polynomial representation of self in the form of the coefficient vector. Here we see that 50620 to radix-127 is 3x^2 + 17x + 74. Accepts all radix in the interval 0;2^64-1.

use number_theory::Mpz;

 let value = Mpz::from_u64(50620);
 assert_eq!(value.to_radix_vec(127),vec![74,17,3])

pub fn from_string(x: &str) -> Option<Self>

Conversion from radix-10^n string.

use number_theory::Mpz;
 let num = "-3141592653589793238462643383279502884197169399375105820974944592307816406286".to_string();
 let machine = Mpz::from_string(&num).unwrap();

 assert_eq!(machine.to_string(),num)

pub fn zero() -> Self

Returns 0

pub fn one() -> Self

Returns positive 1

pub fn two() -> Self

Returns positive 2

pub fn neg(&mut self)

Additive inverse of n, evaluated in-place

pub fn abs(&self) -> Self

Returns the absolute value of n

pub fn is_one(&self) -> bool

Checks if n == 1 or n == -1

pub fn is_zero(&self) -> bool

Checks if n == 0

pub fn is_positive(&self) -> bool

Checks if n >= 0

pub fn is_even(&self) -> bool

Checks if n in 2Z

pub fn is_power_of_two(&self) -> bool

Checks if n in 2^Z

pub fn set_bit(&mut self, k: usize)

Sets the bit at 2^k to 1, if it is already 1 then this does not change

pub fn flip_bit(&mut self, k: usize)

Flips the bit at 2^k

pub fn check_bit(&self, index: usize) -> bool

Check if the bit in the k-place is set

pub fn set_sign(&mut self, sign: Sign)

Change the sign

pub fn len(&self) -> usize

Returns the number of 64-bit machine words used in this representation

pub fn lead_digit(&self) -> u64

Returns the lead digit in 2^64 representation

pub fn trailing_zeros(&self) -> u64

Returns k such that d*2^k = x

pub fn leading_zeros(&self) -> u64

Returns the number of extraneous zeros in bit representation

pub fn bit_length(&self) -> u64

Returns the number of bits used to represent x

pub fn normalize(&mut self)

Removes extraneous zeros

pub fn u_cmp(&self, other: &Self) -> Ordering

Compares the magnitude of x and y, ignoring sign

pub fn congruence_u64(&self, n: u64, c: u64) -> bool

Checks if x mod n === c

pub fn successor(&mut self)

      use number_theory::Mpz;
  let mut one = Mpz::one();

  one.successor();  //Applies the successor function ignoring sign

  assert_eq!("2", one.to_string())

pub fn inc_by(&mut self, n: u64)

Increments by n amount

pub fn inv_successor(&mut self)

Inverse successor function. Subtracts 1 ignoring sign

pub fn pow(&self, x: u64) -> Self

Returns self^x

pub fn ln(&self) -> f64

Aproximation of the natural logarithm ln(x)

pub fn log2(&self) -> f64

Approximation of the base-2 logarithm

pub fn log10(&self) -> f64

Approximation of the base-10 logarithm

pub fn log(&self, log: f64) -> f64

Approximation of the base-k logarithm, where k is a Real.

pub fn iter_log(&self, log: f64) -> u8

Iterated logarithm

pub fn eea(&self, other: &Self) -> (Self, Self, Self)

Finite ring variant of Extended Euclidean algorithm, see trait definition of extended gcd

pub fn sirp(infimum: u64, supremum: u64, modulo: u64, residue: u64) -> Self

Sequential Interval Residue Product, a generalization of the k-factorials

   // see the sirp crate for greater extension of this functionality
    use number_theory::Mpz;
        
   let factorial_100 = Mpz::sirp(1,100,1,0);
       
   // Even. Odd double factorial would be sirp(1,100,2,1)
   let doublefact_100 = Mpz::sirp(1,100,2,0);
   assert_eq!(
   "3424322470251197624824643289520818597\
    5118675053719198827915654463488000000000000",doublefact_100.to_string())

pub fn cip(infimum: u64, supremum: u64, cond: fn(_: &u64) -> bool) -> Self

Conditional Interval Product computes the product of integers satisfying an unary function. In this example the unary function is the primality function. In practice it can be any function that borrows a u64 and returns a boolean.

    use number_theory::Mpz;
    use number_theory::NumberTheory;

   let primorial_25 = Mpz::cip(1,100,u64::is_prime);

impl Mpz

pub fn mut_and(&mut self, other: &Self)

Performs bitwise AND operation between x and y storing the result in x

pub fn mut_or(&mut self, other: &Self)

Performs bitwise OR operation between x and y storing the result in x

pub fn mut_xor(&mut self, other: &Self)

Performs bitwise XOR operation between x and y storing the result in x

pub fn mut_not(&mut self)

Performs bitwise NOT on x in-place

pub fn mut_shl(&mut self, shift: usize)

Shift-left k places in-place

pub fn mut_shr(&mut self, shift: usize)

Shift-left k places in-place

pub fn shl(&self, shift: usize) -> Mpz

Returns x * 2^k

pub fn shr(&self, shift: usize) -> Mpz

Returns x / 2^k

pub fn and(&self, other: &Self) -> Self

Returns x AND y

pub fn or(&self, other: &Self) -> Self

Returns x OR y

pub fn xor(&self, other: &Self) -> Self

Returns x XOR y

pub fn mut_addition(&mut self, other: Self)

x+y stored in x

pub fn ref_addition(&self, other: &Self) -> Self

Returns x+y

pub fn mut_subtraction(&mut self, other: Self)

x-y stored in x

pub fn ref_subtraction(&self, other: &Self) -> Self

Returns x-y

pub fn ref_product(&self, other: &Self) -> Self

Returns x*y

pub fn mut_product(&mut self, other: Self)

x*y stored in x

pub fn mut_scale_add(&mut self, x: u64, y: u64)

Unsigned in-place multiply by x and add y

pub fn scale_add(&self, x: u64, y: u64) -> Self

Unsigned in-place multiply by x and add y

pub fn sqr(&self) -> Self

x*x squaring

pub fn mut_sqr(&mut self)

x*x squaring in-place

pub fn ref_euclidean(&self, other: &Self) -> (Self, Self)

Returns x/y and x mod y

impl Mpz

pub fn sprp_check(&self, n: usize) -> bool

Performs n random base checks, can be combined with is_prime to strengthen it. As is_prime is equivalent to one random sprp check in the worst case, the function below has an error rate of less than 2^-64 in the worst case.

use number_theory::NumberTheory;
use number_theory::Mpz;

fn strong_check(x: &Mpz) -> bool{
  if !x.is_prime(){
    return false
  }
  x.sprp_check(31)
}

pub fn is_sophie(&self) -> Option<Self>

Faster than naive evaluation of sophie prime, returns safe prime if true, otherwise None. As this uses is_prime, the accuracy matches that function exactly as the verification of the safe prime itself is deterministic and solely reliant on the accuracy of the verification of the sophie prime.

pub fn psp(k: usize) -> NTResult<Self>

Returns an integer in the interval 2^(k-1);2^k that can satisfy the Monier-Rabin bound of passing the Artjuhov-Selfridge test with (1/4) probability

pub fn fermat(&self, base: &Self) -> bool

A weak fermat test

pub fn miller(&self) -> bool

Deterministic primality test, reliant on GRH

Trait Implementations

impl Clone for Mpz

fn clone(&self) -> Mpz

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Mpz

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Mpz

fn default() -> Mpz

Returns the “default value” for a type.

impl Display for Mpz

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl NumberTheory for Mpz

fn sqrt(&self) -> (Self, Self)

Returns the integer component of sqrt(x)

fn rng() -> Self

Random number generation, generally high-quality

fn residue(&self, ring: &Self) -> Self

Returns the representation of x in the ring Z[n]

fn euclidean_div(&self, other: &Self) -> (Self, Self)

Euclidean function, normally called euclidean division, returns Q,R such that Q*y + R = x

fn quadratic_residue(&self, n: &Self) -> Self

Returns x*x mod n, similar to product_residue except more optimized squaring.

fn checked_quadratic_residue(&self, n: &Self) -> NTResult<Self>

Returns x*x mod n, similar to product_residue except more optimized squaring.

fn product_residue(&self, other: &Self, n: &Self) -> Self

Returns x*y mod n

fn checked_product_residue(&self, other: &Self, n: &Self) -> NTResult<Self>

Returns x*y mod n

fn exp_residue(&self, y: &Self, n: &Self) -> Self

Returns x^y mod n, generally called mod_pow in other libraries. If y < 0 returns -x^|y| mod n, aka the exponentiation of the multiplicative inverse, analogous to the behavior in the Reals.

fn checked_exp_residue(&self, y: &Self, n: &Self) -> NTResult<Self>

Exponential residue x^y mod n

fn is_sprp(&self, base: &Self) -> bool

Strong probable prime test.Performs Artjuhov-Selfridge test exactly which means that if gcd(x,base) > 1 and x is a prime then it will be flagged as composite

fn is_prime(&self) -> bool

Optimized for the average case. Although speed is valued over determinism, the probability of failure is extremely small and never deterministic (i.e repeating the test will almost certainly fail a previous composite that passed).

fn prime_proof(&self) -> (bool, Vec<Self>)

Checks primality for the integer and returns the evaluation in addition to a vector of the witness followed by the factors of n-1. For instance 269u64.prime_proof may return (true, [238, 2,67]). Verification requires checking that 238.exp_residue(269-1, 269) == 1 and 238.exp_residue((269-1)/2, 269) != 1 and 238.exp_residue((269-1)/67, 269) != 1. See prime_proof in examples to see how. Unable to construct a proof for Carmichael numbers.

fn prime_list(&self, sup: &Self) -> Vec<Self>

Enumerates the primes between self and sup values. If sup < self then it enumerates up to self from sup. Note that while evaluation is possible for any interval it becomes infeasible with very large numbers (>10^6000) or very large intervals (>10^12).

fn nth_prime(&self) -> NTResult<Self>

N-th prime, exact evaluation for less than 2^64, approximation beyond that. Not currently feasible beyond 10^12

fn pi(&self) -> Self

Prime-counting function, exact evaluation for less than 2^64, approximation beyond that. Not currently feasible beyond 10^12

fn prime_gen(x: u32) -> NTResult<Mpz>

Generates an odd positive prime in the interval 2^(k-1);2^k

fn gcd(&self, other: &Self) -> Self

Binary gcd, Computes the greatest common divisor of two numbers

fn extended_gcd(&self, other: &Self) -> (Self, Self, Self)

Extended Euclidean GCD algorithm. The behavior of this function varies depending on if the type is in Z or N.

fn lcm(&self, other: &Self) -> Self

Computes the least common multiple of x,y

fn checked_lcm(&self, other: &Self) -> NTResult<Self>

Computes the least common multiple checking for overflow, and zeroes

fn factor(&self) -> Vec<Self>

Factorizes into a vector of the form prime factor, power, prime factor, power . . . i.e 2,6,5,2 for 2^6 * 5^2 = 1600

fn checked_factor(&self) -> NTResult<Vec<Self>>

Factorizes into a vector of the form prime factor, power, prime factor, power . . . i.e 2,6,5,2 for 2^6 * 5^2 = 1600

fn nth_root(&self, n: &Self) -> (Self, Self)

Returns the integer component of one of the solutions to the equation x*x..*x where x in Z[i]

fn max_exp(&self) -> (Self, Self)

Returns the representation of x as a base and exponent biasing towards high exponents. E.g 81 -> 3^4 If no higher representation of the number exists then it will return the trivial solution of x^1

fn radical(&self) -> NTResult<Self>

Returns the product of each prime such that p | n AND p > 0

fn k_free(&self, x: &Self) -> bool

Determines of a number is k-free, i.e square-free, cube-free etc. . .

fn euler_totient(&self) -> Self

Counts the number of coprimes from 0 to self

fn jordan_totient(&self, k: &Self) -> NTResult<Self>

Counts the Jordan’s totient

fn carmichael_totient(&self) -> NTResult<Self>

Carmichael totient function, also the exponent of the multiplicative group Z/nZ

fn dedekind_psi(&self, k: &Self) -> NTResult<Self>

Higher-order Dedekind psi

fn legendre(&self, p: &Self) -> i8

Legendre symbol of a,p.

fn checked_legendre(&self, p: &Self) -> NTResult<i8>

Legendre symbol of a,p.

fn liouville(&self) -> i8

Liouville function

fn derivative(&self) -> NTResult<Self>

Lagarias derivative

fn mangoldt(&self) -> f64

Von Mangoldt function, returns the natural logarithm of self if it is a prime-power

fn mobius(&self) -> i8

Mobius function

fn jacobi(&self, k: &Self) -> i8

Jacobi symbol of x,p.

fn checked_jacobi(&self, k: &Self) -> NTResult<i8>

Jacobi symbol of x,p.

fn kronecker(&self, k: &Self) -> i8

kronecker symbol

fn smooth(&self) -> NTResult<Self>

Returns the smoothness bound of n, this is the largest prime factor of n.

fn is_smooth(&self, b: &Self) -> bool

Checks if the smoothness bound is at least b

impl PartialEq for Mpz

fn eq(&self, other: &Mpz) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl StructuralPartialEq for Mpz