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::AbsSimpleNumFieldOrder) -> Vector{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}

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::AbstractUnitRange{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::AbstractUnitRange, 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$.

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{PolyRingElem}, 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{AbsSimpleNumFieldElem}, p::ZZRingElem, b::Generic.Poly{AbsSimpleNumFieldElem}, q::ZZRingElem) -> Generic.Poly{AbsSimpleNumFieldElem}, 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{AbsSimpleNumFieldElem}, M::ZZRingElem) -> bool, Generic.Poly{AbsSimpleNumFieldElem}

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.