Miscalleneous

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

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

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

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

euler_phi_inv(n::ZZRingElem, 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

psi_lower(N::Integer, B::NfFactorBase) -> Vector{Int}, ZZAbsPowerSeriesRingElem
psi_lower(N::ZZRingElem, B::NfFactorBase) -> Vector{Int}, ZZAbsPowerSeriesRingElem

psi_upper(N::Integer, B::NfFactorBase) -> Vector{Int}, ZZAbsPowerSeriesRingElem
psi_upper(N::ZZRingElem, B::NfFactorBase) -> Vector{Int}, ZZAbsPowerSeriesRingElem

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

largest_elementary_divisor(A::ZZMatrix) -> ZZRingElem

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

maximal_elementary_divisor(A::ZZMatrix) -> ZZRingElem

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

mod_sym(M::ZZMatrix, p::ZZRingElem) -> ZZMatrix

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

mod_sym!(M::ZZMatrix, p::ZZRingElem)

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

mod!(M::ZZMatrix, p::ZZRingElem)

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

saturate(A::ZZMatrix) -> ZZMatrix

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.

elementary_divisors(A::ZZMatrix) -> Vector{ZZRingElem}

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

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.

divisors(A::ZZMatrix, d::ZZRingElem) -> ZZRingElem

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

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

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.

snf_with_transform(A)

Return the tuple $S, T, U$ consisting of the Smith normal form $S$ of $A$ together with invertible matrices $T$ and $U$ such that $TAU = S$.

induce_crt(a::ZZPolyRingElem, p::ZZRingElem, b::ZZPolyRingElem, q::ZZRingElem, signed::Bool = false) -> ZZPolyRingElem

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.

induce_crt(L::Vector{PolyElem}, c::crt_env{ZZRingElem}) -> ZZPolyRingElem

Given ZZRingElem_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]$.

induce_crt(L::Vector{MatElem}, c::crt_env{ZZRingElem}) -> ZZMatrix

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]$.

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

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

induce_rational_reconstruction(a::ZZPolyRingElem, M::ZZRingElem) -> QQPolyRingElem

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

induce_rational_reconstruction(a::Generic.Poly{nf_elem}, M::ZZRingElem) -> 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.