Trait number_theory::NumberTheory

source ·

pub trait NumberTheory: Default + Clone + Sized + Display {
Show 42 methods    // Required methods
    fn rng() -> Self;
    fn euclidean_div(&self, other: &Self) -> (Self, Self)
       where Self: Sized;
    fn residue(&self, ring: &Self) -> Self;
    fn is_sprp(&self, base: &Self) -> bool;
    fn is_prime(&self) -> bool;
    fn prime_proof(&self) -> (bool, Vec<Self>)
       where Self: Sized;
    fn prime_list(&self, sup: &Self) -> Vec<Self>
       where Self: Sized;
    fn nth_prime(&self) -> NTResult<Self>
       where Self: Sized + Clone;
    fn prime_gen(k: u32) -> NTResult<Self>
       where Self: Sized + Clone;
    fn pi(&self) -> Self;
    fn factor(&self) -> Vec<Self>
       where Self: Sized;
    fn checked_factor(&self) -> NTResult<Vec<Self>>
       where Self: Sized + Clone;
    fn sqrt(&self) -> (Self, Self)
       where Self: Sized;
    fn nth_root(&self, n: &Self) -> (Self, Self)
       where Self: Sized;
    fn max_exp(&self) -> (Self, Self)
       where Self: Sized;
    fn gcd(&self, other: &Self) -> Self;
    fn extended_gcd(&self, other: &Self) -> (Self, Self, Self)
       where Self: Sized;
    fn lcm(&self, other: &Self) -> Self;
    fn checked_lcm(&self, other: &Self) -> NTResult<Self>
       where Self: Sized + Clone;
    fn carmichael_totient(&self) -> NTResult<Self>
       where Self: Sized + Clone;
    fn euler_totient(&self) -> Self;
    fn jordan_totient(&self, k: &Self) -> NTResult<Self>
       where Self: Sized + Clone;
    fn dedekind_psi(&self, k: &Self) -> NTResult<Self>
       where Self: Sized + Clone;
    fn product_residue(&self, other: &Self, n: &Self) -> Self;
    fn checked_product_residue(&self, other: &Self, n: &Self) -> NTResult<Self>
       where Self: Sized + Clone;
    fn quadratic_residue(&self, n: &Self) -> Self;
    fn checked_quadratic_residue(&self, n: &Self) -> NTResult<Self>
       where Self: Sized + Clone;
    fn exp_residue(&self, pow: &Self, n: &Self) -> Self;
    fn checked_exp_residue(&self, pow: &Self, n: &Self) -> NTResult<Self>
       where Self: Sized + Clone;
    fn k_free(&self, k: &Self) -> bool;
    fn radical(&self) -> NTResult<Self>
       where Self: Sized + Clone;
    fn smooth(&self) -> NTResult<Self>
       where Self: Sized + Clone;
    fn is_smooth(&self, b: &Self) -> bool;
    fn legendre(&self, p: &Self) -> i8;
    fn checked_legendre(&self, p: &Self) -> NTResult<i8>;
    fn liouville(&self) -> i8;
    fn derivative(&self) -> NTResult<Self>
       where Self: Sized + Clone;
    fn mangoldt(&self) -> f64;
    fn mobius(&self) -> i8;
    fn jacobi(&self, p: &Self) -> i8;
    fn checked_jacobi(&self, p: &Self) -> NTResult<i8>;
    fn kronecker(&self, k: &Self) -> i8;
}

Expand description

Trait for number-theory functions across all integer types

Required Methods§

source

fn rng() -> Self

Random number generation, generally high-quality

source

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

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

Panic

y == 0

source

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

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

source

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

Correct primality tests account for this, so it is up to the user to account for them as well.

source

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).

N < 2^64 + 2^49 Provably correct deterministic test, uniquely uses a maximum of 2 strong fermat tests giving it the lowest average complexity publicly known. Average complexity 0.3 tests, worst-case 2.6 sprp checks (against 2^64-59)

N > 2^64 + 2^49 Weighted to ensure 2^-64 probability of failure against a random input.Performs a minimum of 3 sprp checks. Strongest counterexamples are of the form n = p(x(p-1)+1)(y(p-1)+1) where p is prime and gcd(x,y,p) = 1 and n > 2^512, passing at a rate of approximately 25%. Any other equally strong counterexamples are encouraged to be reported. Further strengthening the test should be by calling sprp_check afterwards not by calling is_prime again. Average complexity 0.18 worst case 12 sprp checks (typical worst case is around 3.1, 12 is the absolute worst case against a very narrow interval).

Mersenne : Deterministic, not computed

Fermat : Deterministic, not computed, assumed to not exist beyond 65537 .

source

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

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.

source

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

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).

source

fn nth_prime(&self) -> NTResult<Self>
where Self: Sized + Clone,

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

DNE

n == 0 (there is no zeroth prime)

Overflow

Pn > datatype MAX

source

fn prime_gen(k: u32) -> NTResult<Self>
where Self: Sized + Clone,

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

DNE

x == 0

Overflow

x > datatype length in bits

source

fn pi(&self) -> Self

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

source

fn factor(&self) -> Vec<Self>
where Self: Sized,

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

Failure

x == 0 OR x == 1

source

fn checked_factor(&self) -> NTResult<Vec<Self>>
where Self: Sized + Clone,

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

InfiniteSet

x == 0

DNE

x == 1

source

fn sqrt(&self) -> (Self, Self)
where Self: Sized,

Returns the integer component of at least one solution to the equation x*x = n where x in Z[i] (aka the Gaussian integers). When x < 0 the result is (sqrt(x),1) otherwise it is the (sqrt(x),0)

source

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

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

source

fn max_exp(&self) -> (Self, Self)
where Self: Sized,

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

source

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

Binary gcd, Computes the greatest common divisor of two numbers

source

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

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

Z : returns the GCD and Bezout coefficients (x,y) such that gcd(a,b) = ax + by

N : returns the GCD and Bezout coefficients such that ax + by = gcd(a,b) over Z[lcm(a,b)]

Note that if gcd(a,b) != a OR b this is equivalent to ax mod b = gcd(a,b) and by mod a = gcd(a,b). In the case of gcd(a,b) =1 these coefficients are the multiplicative inverses of a over Z[b] and b over Z[a], respectively

source

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

Computes the least common multiple of x,y

Failure

If lcm(x,y) > datatype MAX

source

fn checked_lcm(&self, other: &Self) -> NTResult<Self>
where Self: Sized + Clone,

Computes the least common multiple checking for overflow, and zeroes

Overflow

lcm(x,y) > datatype MAX

source

fn carmichael_totient(&self) -> NTResult<Self>
where Self: Sized + Clone,

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

Infinite

x == 0 As the infinite group of Z/0Z has no exponent

source

fn euler_totient(&self) -> Self

Counts the number of coprimes from 0 to self

source

fn jordan_totient(&self, k: &Self) -> NTResult<Self>
where Self: Sized + Clone,

Counts the Jordan’s totient

Overflow

Jordan_totient(x,k) > datatype MAX

CompOverflow

Computation overflowed

source

fn dedekind_psi(&self, k: &Self) -> NTResult<Self>
where Self: Sized + Clone,

Higher-order Dedekind psi

Overflow

dedekind_psi(x,k) > datatype MAX

CompOverflow

Computational overflow

source

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

Returns x*y mod n

Failure

if x * y > datatype MAX AND n == 0

source

fn checked_product_residue(&self, other: &Self, n: &Self) -> NTResult<Self>
where Self: Sized + Clone,

Returns x*y mod n

Overflow

if x * y > datatype MAX AND n == 0

source

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

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

Failure

if x * x > datatype MAX AND n == 0

source

fn checked_quadratic_residue(&self, n: &Self) -> NTResult<Self>
where Self: Sized + Clone,

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

Overflow

if x * x > datatype MAX AND n == 0

source

fn exp_residue(&self, pow: &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.