Miscalleneous

Integer related

# euler_phi_inv — Function.

euler_phi_inv(n::Integer) -> Vector{fmpz}

The inverse of the Euler totient functions: find all $x$ s.th. $phi(x) = n$ holds.

source

euler_phi_inv(n::fmpz) -> Vector{fmpz}

The inverse of the Euler totient functions: find all $x$ s.th. $phi(x) = n$ holds.

source

euler_phi_inv(n::fmpz, zk::NfAbsOrd{AnticNumberField, nf_elem}) -> Vector{NfOrdIdl}

The inverse of the ideal totient function: all ideals $A$ s.th. the unit group of the residue ring has the required size.

source

# modord — Method.

modord(a::fmpz, m::fmpz) -> Int
modord(a::Integer, m::Integer)

The multiplicative order of a modulo $m$ (not a good algorithm).

source

# is_prime_power — Method.

is_prime_power(n::fmpz) -> Bool
is_prime_power(n::Integer) -> Bool

Tests if $n$ is the exact power of a prime number.

source

# primes_up_to — Method.

primes_up_to(n::Int) -> Vector{Int}

Returns a vector containing all the prime numbers up to $n$.

source

Analytic

# dickman_rho — Function.

dickman_rho(x::Number, prec::Int=55) Number

Evaluates the Dickman-$\rho$ function at $x$.

source

dickman_rho(x::Number, e::UnitRange{Int}, prec::Int=55) Number[]

Evaluates the Dickman-$\rho$ function at $i*x$ for all $i\in e$.

source

# psi_guess — Function.

psi_guess(x::Number, B::Int) Number

Uses the dickman_rho function to estimate $\psi(x, B)$ the number of $B$-smooth integers bounded by $x$.

source

psi_guess(x::Number, e::UnitRange, B::Int) Number

Uses the dickman_rho function to estimate $\psi(x^i, B)$ the number of $B$-smooth integers bounded by $x^i$ for $i \in e$.

source

# psi_lower — Function.

psi_lower(N::Integer, B::Int, a::Int = 776) -> Vector{Int}, fmpz_abs_series
psi_lower(N::fmpz, B::Int, a::Int = 776) -> Vector{Int}, fmpz_abs_series

Uses Bernstein's ideas: https://cr.yp.to/papers/psi.pdf to compute lower bounds on the psi function counting smooth numbers. An array $L$ is returned s.th. $\psi(2^{i-1}, B) \ge L_i$ for $1\le i\le \rceil \log_2(B)\lceil$. The second return value is Bernstein's power series.

The optional other parameter $a$ controls the precision of the result, it defaults to 776.

source

psi_lower(N::Integer, B::NfFactorBase) -> Vector{Int}, fmpz_abs_series
psi_lower(N::fmpz, B::NfFactorBase) -> Vector{Int}, fmpz_abs_series

psi_upper(N::Integer, B::NfFactorBase) -> Vector{Int}, fmpz_abs_series
psi_upper(N::fmpz, B::NfFactorBase) -> Vector{Int}, fmpz_abs_series

Uses Bernstein's techniques to bound the number of ideals $A$ of norm bounded by $N$ that are smooth over the factor base $B$.

source

Linear Algebra

# largest_elementary_divisor — Function.

largest_elementary_divisor(A::fmpz_mat) -> fmpz

The largest elementary divisor of $A$, that is, the last diagonal entry of the Smith normal form of $A$.

source

# maximal_elementary_divisor — Method.

maximal_elementary_divisor(A::fmpz_mat) -> fmpz

The largest elementary divisor of $A$, that is, the last diagonal entry of the Smith normal form of $A$.

source

# mod_sym — Method.

mod_sym(M::fmpz_mat, p::fmpz) -> fmpz_mat

Reduces every entry modulo $p$ into the symmetric residue system.

source

# mod_sym! — Method.

mod_sym!(M::fmpz_mat, p::fmpz)

Reduces every entry modulo $p$ in-place, into the symmetric residue system.

source

# mod! — Method.

mod!(M::fmpz_mat, p::fmpz)

Reduces every entry modulo $p$ in-place, i.e. applies the mod function to every entry. Positive residue system.

source

# saturate — Method.

saturate(A::fmpz_mat) -> fmpz_mat

Computes the saturation of $A$, that is, a basis for $\mathbf{Q}\otimes M \cap \mathbf{Z}^n$, where $M$ is the row span of $A$ and $n$ the number of rows of $A$.

Equivalently, return $TA$ for an invertible rational matrix $T$ such that $TA$ is integral and the elementary divisors of $TA$ are all trivial.

source

# elementary_divisors — Method.

elementary_divisors(A::fmpz_mat) -> Vector{fmpz}

The elementary divisors of $A$, that is, the diagonal entries of the Smith normal form of $A$.

source

# jordan_normal_form — Function.

jordan_normal_form(M::MatElem{T}) where T <: FieldElem -> MatElem{T}, MatElem{T}

Returns matrices $J$ and $S$ such that $J = SMS^{-1}$ and $J$ is in Jordan normal form.

source

# divisors — Method.

divisors(A::fmpz_mat, d::fmpz) -> fmpz

Returns the diagonal entries of a diagonal form of $A$. We assume that all the elementary divisors are divisors of $d$.

source

# snf_with_transform — Method.

snf_with_transform(A::fmpz_mat, l::Bool = true, r::Bool = true) -> fmpz_mat, fmpz_mat, fmpz_mat

Given some integer matrix $A$, compute the Smith normal form (elementary divisor normal form) of $A$. If l and/ or r are true, then the corresponding left and/ or right transformation matrices are computed as well.

source

Polynomials

CRT

# induce_crt — Function.

induce_crt(a::fmpz_poly, p::fmpz, b::fmpz_poly, q::fmpz, signed::Bool = false) -> fmpz_poly

Given integral polynomials $a$ and $b$ as well as coprime integer moduli $p$ and $q$, find $f = a \bmod p$ and $f=b \bmod q$. If signed is set, the symmetric representative is used, the positive one otherwise.

source

induce_crt(L::Vector{PolyElem}, c::crt_env{fmpz}) -> fmpz_poly

Given fmpz_poly polynomials $L[i]$ and a crt\_env, apply the crt function to each coefficient resulting in a polynomial $f = L[i] \bmod p[i]$.

source

induce_crt(L::Vector{MatElem}, c::crt_env{fmpz}) -> fmpz_mat

Given matrices $L[i]$ and a crt\_env, apply the crt function to each coefficient resulting in a matrix $M = L[i] \bmod p[i]$.

source

induce_crt(a::Generic.Poly{nf_elem}, p::fmpz, b::Generic.Poly{nf_elem}, q::fmpz) -> Generic.Poly{nf_elem}, fmpz

Given polynomials $a$ defined modulo $p$ and $b$ modulo $q$, apply the CRT to all coefficients recursively. Implicitly assumes that $a$ and $b$ have integral coefficients (i.e. no denominators).

source

# induce_rational_reconstruction — Function.

induce_rational_reconstruction(a::fmpz_poly, M::fmpz) -> fmpq_poly

Apply rational_reconstruction to each coefficient of $a$, resulting in either a fail (return (false, s.th.)) or (true, g) for some rational polynomial $g$ s.th. $g \equiv a \bmod M$.

source

induce_rational_reconstruction(a::Generic.Poly{nf_elem}, M::fmpz) -> bool, Generic.Poly{nf_elem}

Apply rational reconstruction to the coefficients of $a$. Implicitly assumes the coefficients to be integral (no checks done) returns true iff this is successful for all coefficients.

source