conway(p, n)

Return the conway-polynomial of degree n over ZZ/p, as far as available.

For n in (1,2) the polynomials are calculated and memoized in the data cache.

conway_multi(p, m, X=:x; nr=10^5)

Return a list of conway polynomials for GF(p^m), length clipped to `nr.

has_conway_property1(poly)

Check if poly is monomial.

has_conway_property2(poly)

Check if an irreducible polynomial poly over ZZ/p of degree n has property 2 (is primitive).

That means that the standard generator x in the quotient ring (field) (ZZ/p) / poly is also generator in the multiplicative group of the ring.

If m is the order of this group (p^n - 1 if a field), it sufficient to check, if x ^ (m / s) != 1 for all prime factors of m. (y ^ m == 1 for all y != 0)

The function returns missing if p^n - 1 has no known prime factors.

has_conway_property3(poly::(ZZ/p)[:x]})

Check if a polynomial poly over ZZ/p of degree n has property 3.

That means, for all divisors 1 <= m < n we have conway(p, m)(x^w) == 0 mod poly with w = (p^n - 1) / (p^m - 1).

The definition is recursive and requires the knowledge of Conway polynomials of lesser degree.

If such polynomials are unknown, missing is returned.

isconway(::Type{GaloisField})

Return true, iff the modulus of the field is the standard conway polynomial.

quasi_conway(p, m, X::Symbol, nr::Integer=1, factors=nothing)

Return the first irreducible polynomial over ZZ/p of degree m.

The polynomials are scanned in the canonical order for Conway polynomials.

Variable symbol is X. If given, factors must be the prime factorization of m. If nr > 0 is given, the nr+1^st of found polynomials is returned.

B(n), B(n, x)

Bernoulli-number and Bernoulli-polynomial

E(n), E(n, x)

Euler-number and Euler-polynomial

Ein(z)

Return "exponential integral" normalizing function.

We have also

• Ei(z) = γ + log(|z|) - Ein(-z) for z != 0
• E_1(z) = -γ -log(z) + Ein(z) for |arg(z)| < π

Li(z, n)

Return value of "polylogarithmic" function Li of order n.

stirling2(n, k)

Stirling numbers of the second kind. See also stirling2r.

lin1p(z) = lin(1 + z) = -Ein(-log(1 + z))

Return "logarithmic integral" normalizing function.

We have:

• lin(z) = lin1p(z - 1)
• li(z) = Ei(log(z))
• li(z) = γ + log(|log(z)|) + lin(z) for z > 0

lin1pe(u) = lin1p(expm1(u))

Return "logarithmic integral" variant.

Faster converging series, if applied to log(z) devoted to Ramanujan.

• lin1pe(log1p(z)) == lin1p(z)

Podhammer(x, n::Integer)

Podhammer symbol.

Decreasing product: podhammer(x, 3) = x * (x-1) * (x-2)

Increasing product: podhammer(x, -3) = x * (x+1) * (x+2).

power1p(z, p) = (1 + z)^p

sqrt1p(z) = sqrt(1 + z)

stirling1(n, k)

Stirling numbers of the first kind. See also stirling1r.

stirling1r(n, k)

Unsigned Stirling numbers of first kind. stirling1r(n, k) = (-1)^(n-k) * stirling1(n, k)

stirling2r(n, k)

Signed Stirling numbers of second kind. striling2r(n, k) = (-1)^(n-k) * stirling2(n, k).

ver(z) = 1 - cos(z)

Return the versine of z

MINPRIME constant for first prime to try irreducibility

RingInt

Union of system Integer types and any Ring subtype.

FSeries{T,F}

Represent a Taylor- or Laurent-series by a function over the integers.

Frac{R}

The ring of fractions of R. The elements consist of pairs num::R,den::R. During creation the values may be canceled to achieve gcd(num, den) == one(R). The special case of R<:Integer is handled by QQ{R}.

FractionRing{S<:RingInt,T<:FractionRingClass}

Rational extension of elements of ring S. Example the field of rational numbers.

GaloisField

@see GF, ofindex.

Hom{function,R,S}

Represent a ring homomorphism function:R -> S.

Ideal{R}

Respresent in Ideal of Ring R. Only Ideals with a finite (Groebner) basis.

IterTerms(p::Polynomial)

Return iterator over all non-zero terms of polynomial p.

MultivariatePolynomial{S<:Ring,N,Id}

Polynomials of ring elements S in N variables. The Id identifies on object of type MultiPolyRingClass which is needed to store the variable names and properties.

A convenience constructor S[:x,:y...] is the preferred way to construct this class.

Polynomial{S<:Ring,T<:PolyRingClass}

Power Series (aka Taylor Series) are a generalization of polynomials. Calculation is restricted to a maximal "precision"(number of terms to be considered). All further terms are subsumed in a "remainder term".

QQ{S<:Integer}

Quotient{R,I,m}

The quotient ring of R modulo m of type I, also written as R / m. m may be an ideal of R or a (list of) element(s) of R generating the ideal. Typically m is replaced by a symbolic X, and the actual m is given as argument(s) to the type constructor like new_class(Quotient{ZZ,X}, m...). If the $X$is omitted, an anonymous symbol is used.

The preferred way of construction is via Zm = Z/m.

QuotientRing{S<:Union{Integer,Ring},T<:QuotientRingClass}

Quotient ring of ring S by some ideal. If S = Z, the ring of integer numbers, and p a positive number Z/p is calculation modulo p.

RNF(polynomials, transformation)

Store the polynomials list and the transformation for rational normal form, aka Frobenius normal form.

Ring{<:RingClass}

Abstract superclass of all commutative ring element types. All subtypes support the arithmetic operators +, -, *, and ^(power). The operators inv, / may be defined on a subset.

SNF(D, S, T)

Store the elements of a Smith normal form of a matrix A.

D is a vector with nonzero elements of a principal ideal domain (PID). Each vector element except the last one divides its successor.

S and T are invertible matrixes over the PID, with S * A * T == Diag(D).

UnivariatePolynomial{S<:RingInt,Id}

Polynomials of ring elemets S in one variable Id (by default :x). The variable name is specified as a Symbol.

A convenience constructor S[:x] is the preferred way to construct this class.

UnivariatePolynomials{X,S}(vector)

Construct a new polynomial Ring-element. Allow all coefficient classes, which can be mapped to S, that means the canonical homomorphism is used.

VectorSpace{R,V}

Represent a vector space over a Vfield R.

VectorSpace(v::AbstractVector...)

Vector space generated by the vectors or matrix. To obtain a basis of the space, use Matrix(::VectorSpace).

WNF(polynomials, transformation)

Store the polynomials list and the transformation for Weierstrass normal form. The vector of polynomials corresponds to the transformation matrix.

ZZ{S<:Signed}

The ring of integer numbers. There may be restrictions on the set of representable elemets according to the chosen S.

ZZmod{m,S<:Integer}

Quotient ring modulo integer m > 0, also noted as ZZ/m. If p is a prime number, ZZmod{p} is the field ZZ/p.

intersect(v1::V, v2::V)::V where V<:VectorSpace

Intersection of two vector spaces.

log(g::GaloisField)

Return the integer k in 0:order(G)-2 with g == α ^ k, where α is the generator of G or -1 if g == 0. For example log(one(G)) == 0 and log(generator(G)) == 1.

precision(::Type{<:PowerSeries})
precision(s::PowerSeries)

Return the maximal relative precision of a power series type. Return the actual relative precision of a power series object.

The absolute precision of an element is ord(s) + precision(s)

reverse(p::UnivariatePolynomial)

Revert the order of coefficients. If n = deg(p) and kmaximal withx^kdividesp, thenreverse(p) == x^(n + k) * p(1 // x). The degree ofp` is not changed.

sqrt(z::GaloisField)

Calculate a x in the same field with x ^ 2 == z.

Throw DomainError if no solution exists. With xalway -x is a solution. With characteristic 2, every zhas a square root`.

sqrt(s::PowerSeries)

For power series s with constant term 1 calculate the powerseries p with p^2 == s and constant term 1.

sum(v1::V, v2::V)::V where V<:VectorSpace

Sum of two vector spaces resulting in vector space of same kind.

CC(p::UnivariatePolynomial)

Return the constant coefficient of polynomial.

GCD(u::P, v::P) where P<:UnivariatePolynomial

Calculate g = gcd(u, v) and returngcd(u, v), u / g, v / g`.

GF(p, r; mod=:conway, nr=0, maxord=2^20)

Create a class of element type GaloisField of order p^r. p must be a prime integer and r a positive integer.

The modulus polynomial is looked up or calculated dependant on argument mod:

• If mod == nothing, an irreducible monic primitive polynomial of degree r over ZZ/p is calculated, which has the constant coefficient (-1)^r * generator(ZZ/p).
• If mod == :conway (default), the compatible Conway polynomial is used if available, otherwise a less restrictive polynomial is calculated as described above.
• If mod is a polynomial, that irreducible monic polynomial is used as the modulus.

If nr != 0 is given, in the case of modulus calculation, the first nr solutions are skipped.

maxord defines the maximal order, for which logarithm tables are stored to implement the class. Otherwise a representation by quotient space of the polynomial over ZZ/p is used.

GFImpl(p[, m=1]; mod=modulus, nr=0)

Return a representation for Galois Field GFImpl(p, m). p must be a prime number and m a positive integer.

If m == 1, ZZmod{p} is returned, otherwise an irreducible polynomial g ∈ ZZmod{p}[:x] and deg(g) == m is generated and ZZmod{p}[:x]/(g) is returned.

Optionally either the modulus polynomial mod or a integer search modifier nr may be given to control the selection of the modulus polynomial.

Elements of the field can be created like

    GF7 = GFImpl(7)
    GF7(5)  # or
    GF53 = GFImpl(5, 3)
    GF53([1,2,3])

LC(r::Ring)

Return the leading coefficient of r. For non-polynomials return r itself.

LC(p::Polynomial)

Return the leading coefficient of a non-zero polynomial. This coefficient cannot be zero. Return zero for zero polynomial.

LT(p::Polynomial)

Return leading term of polynomial p. Coefficient is taken from p.

SPOL(f, g)

Calculate the S-polynomial (SPOL) of the polynomials f, g.

_divremv(cp::Vector, fp::Int, cq::Vector, fq::Int, F::Val{Bool})

Perform "long division" of polynamials over a ring, represented by p = cp(x) * x^fp etc.

Division and remainder algorithm. d, r = divrem(p, q) => d * q + r == p.

If the boolean argument is true, perform pseudo-division by multiplying the divident by Ring element in order to allow division.

In the other case, divide by leading term of q. If remainder is not zero the degree of d is not reduced (lower than that of q).

Attempt to divide by null polynomial throws DomainError.

absprecision(s::PowerSeries)

Return absolute precision of a power series element.

Essentially: ord(s) + precision(s)

adjugate(A::AbstractMatrix{<:Ring})

The adjugate of matrix A. Invariant is adjugate(A) * A == det(A) * I.

all_factors_irreducible!(res, fac, p)

Move factors, that are proved irreducible, from fac to res. Factors ar proved irreducible with respect to integer p, if either they cannot be reduced modulo p, or the absolute values of the coefficients are less than p / 2. B is an upper bound on the coefficients. Return true iff fac becomes empty.

allgcdx(v)

Given vector v of mutual coprime elements modulo p. Calculate vector a with sum(div.(a .* prod(v), v)) == 1 modulo p and deg.(a) .< deg.(v). If element type is not a polynomial over ZZ/p, read deg as abs.

allpf(n::Integer)

Return ordered vector of prime factors of n.

allzeros(p, vx)

Assume p is an irreducible polynomial over ZZ/q. If p(vx) == 0 for a galois field element vx, find all zeros of p in the galois field, vx belongs to.

aroot(s, n)

Calculate approximately (53 bits) s^(1/n)

axspace(A, u, n)

Return new matrix [u A*u A^2*u ... A^(n-1)*u]

bestpowers(n::Integer, p::Vector{Integer})

Calculate the smallest number m >= n, which is a product of integral powers of the elements of p.

bezout_sum(u, a)

Calculate the sum of products a[i] * (prod(u) / u[i]). Should be 1 if a are bezout factors of u.

butterfly2!(a, d, k)

Permute in-memory so a_new[revert(i, ilog2(n))*d+l] == a[i*d] for i ∈ 0:n-1 for l ∈ 1:d.

carmichael(n::Integer)

Return the Carmichael λ-function value at of n, also called the reduced totient.

It is a divisor of the Euler ϕ-function (aka totient).

cbin(n, d)

Calculate the greatest integer c such that binomial(c, d) <= n

characteristic(::Type)

Returns characteristic c of ring R. c is the smallest positive integer with c * one(R) == 0, or 0 if c * one(R) != 0 for all positive integers c.

characteristic(Z::Type{<:Ring})

Returns the characteristic c of ring Z. c is the smallest positive integer with c * one(Z) == 0, or 0 if c * one(Z) != 0 for all positive integers c.

characteristic_polynomial(A[, P])

Characteristic polynomial of matrix A. P is an optional univariate polynomial type, defaulting to eltype(A)[:x]

coeffbounds(u::UnivariatePolynomial, m)::Vector{<:Integer}

Assuming u is a univariate polynomial with integer coefficients and LC(u) != 0 != u(0). If u has an integer factor polynom v with deg(v) == m, calculate array of bounds b with abs(v[i]) <= b[i+1] for i = 0:m. Algorithm see TAoCP 2.Ed 4.6.2 Exercise 20.

coeffs(p::UnivariatePolynomial)

Return vector of length deg(p)+1 with all coefficients of polynomial. First vector element is constant term of polynomial.

combinefactors(u, v::Vector{<:UnivariatePolynomial{ZZ/p}}, a::Vector{<:UnivariatePolynomial{ZZ/q}})

Given integer polynomial u and v a monic squarefree factorization of u modulo p (vector of polynomials over ZZ/p), and a a vector of corresponding Bezout factors. Return vector of tuples containing integer polynomial factors U, V vector with corresponding factorization, and A corresponding Bezout factors modulo q. The vector is build by a brute-force search of all products of subsets of v, until a product divides u.

If degrees of V sums up to the degree of U, that indicates the factorization was successful. It is also possible, that only one factor is found. The factors are not proved to be irreducible.

companion(p::UnivariatePolynomial)

Return the companion matrix of monic polynomial p. The negative of p's trailing coefficients are in the last column of the matrix. Its characteristic polynomial is identical to p.

complement(v::V)::V where V<:VectorSpace

Return a complementary space of vector space.

compose_inv(f::PowerSeries{R}) -> g::PowerSeries

Compute composition inverse g of f.

Condition: f(0) == 0 and f(x) / x is invertible and ring has characteristic(R) == 0. Use the "Lagrange inversion formula".

compress(p, n)

Return polynomial q with q(x^n) == p(x).

Assuming p has this form. compress(uncompress(p) == p.

content(p::Polynomial)

Return the content of the polynomial p, i.e. the gcd of its coefficients, negated if leading coefficient is negative. See also primpart.

content_primpart(p::UnivariatePolynomial{<:QQ})

Return content and primpart of a polynomial.

convolute_all!(r, a, b, n, w)

Multiply pairwise polynomials modulo x^n + 1.

a[j*n+1:j*n+n] and b[j*n+1:j*n+n] contain the coefficients of the source polynomials, r[j*n+1:j*n+n] of the results. w is additional workspace of same size as a, b, and r. r may be identical to a (but not b). If length is not a multiple of n, results are undefined.

convolute_j!(p::Vector, jn, n, z)

Multiply in place polynomial of degree n-1 by x^z modulo x^n + 1.

The polynomial is given by sum^n-1_i=0 p[i+jn+1] * x^i. Assume 0 <= jn < length(p) - n.

crt(x, y, p, q)

Chinese remainder theorem. Given x, y, p, q with gcd(p, q) == 1, return 0 <= z < lcm(p, q) with 'mod(z - x, p) == 0andmod(z - y, q) == 0`. The result type is widened to avoid overflows.

cyclotomic(P, n)

Calculate nth cylotomic polynomial in polynom ring P over the integers. This polynom is defined to be the unique irreducible divisor of x^n - 1, which is coprime to all x^k - 1 with k < n.

If n is prime, `cyclotomic(P, n) = (x^n - 1) / (x - 1).

If n is squarefree (product of distinct primes p1 * p2 * ... * pk) and c_k(x) = cyclotomic(P, p1*...*pk) we use the recursion formula c_(k+1)(x) = c_k(x^pk) / c_k(x).

If v = p1*...*pk with the distinct prime factors of n, we have cyclotomic(P, n)(x) = cyclotomic(P, v)(x^(n/v)).

ddf(p)

Distinct-degree factorization. Input is a squarefree polynomial. Returns a list of pairs g_i => d_i of polynomials gi, each of which is a product of all irreducible monic polynomials of equal degree `di. The product of allg_i == p`.

deg(r::Union{Ring,Number})

Return the degree of ring element or number r.

For zero elements, that is -1, otherwise 0 for non-polynomials, the ordinary degree for univariate polynomials and the maximum sum of exponents for multivariate polynomials.

deg(p::Polynomial)

Return the degree of the polynomial p, i.e. the highest exponent in the polynomial that has a nonzero coefficient. The degree of the zero polynomial is defined to be -1.

deg_prod(v, d)

Calculate and return deg(pprod(v, n)) efficiently.

degree2index(d)

For degree d return the index of the first element of that degree.

degree2row(d)

For degree d return the row of the first element of that degree. Inverse of row2degree.

derive(p::UnivariatePolynomial)

Return formal derivative of polynomial p.

For k in 1:deg(p) we have derive(p)[k-1] = k * p[k]. If deg(p) * LC(p) == 0 degree: deg(derive(p)) < deg(p) - 1.

derive(p::MultivariatePolynomial, (d1,...dN))

Derive polynomial with N variables with respect to variables 1 ... N with the respective degrees d1 ... dN.

det_Bird(a::Matrix{D}) where D

This is a division-free algorithm to calculate the determinant of a. There are no conditions on D except it is a non-empty commutative ring with one. Derived from "Pearls of Functional Algorithm Design, chap. 22" by Richard Bird - 2010

det_DJB(a::Matrix{D}) where D<:Union{Ring,Number}

This code is taken from "Algorithm 8.36 (Dogdson-Jordan-Bareiss)" of "Algorithms in Real Algebraic Geometry" by Basu, Pollak, Roy - 2016.

Its use is restricted to the case of D an integral domain.

det_MV(a)

Divisionfree combinatoric algorithm to calculate determinant. "Determinant: Combinatorics, Algorithms, andComplexity" by Mahajan, Vinay in Chicago Journal of Theoretical Computer Science1997-5 http://cjtcs.cs.uchicago.edu/articles/1997/5/cj97-05.pdf

det_QR(a::Matrix{D}) where D<:QuotientRing

This code is an extension of det_DJB to certain quotient rings which are domains. I.e. ZZ/p where p is not prime and P[:x]/q where q is the product of polynomials.

dimension(::Type)

Returns the number of dimensions of vector-space like rings (like quotient rings over polynomials). In al other cases return 1

discriminant(a)

Calculate discriminant of a univariate polynomial a.

divides_maybe(v, u)

Check the two least significant coefficients of v and u. Return false if polynomial v does definitely not divide u. If return value is true, v possibly does.

divremv(p::P, v::Vector{T}) where T<:UnivariatePolynomial

Find polynomials a[i] and remainder r with p == sum(a[i] * v[i]) + r with minimal degree of r.

edf(p::Polynomial, d::Integer)

Equal-degree factorization. Algorithm of Cantor-Zassenhaus to find the factors of p, a product of monomials of degree d. (Such polynomials are in the output of ddf). The base type for p must be a finite field. Odd charcteristic is a covered special case.

enumx(n::Integer, bits)::Integer

For each bits >= 0, n -> enumx(n, bits) is a bijection of 0:2^bits-1 in a way that enumx.(0:2^bits-1, bits) is sorted by number of ones in two's complement representation. In other words, enumx.(0:n, bits) is sorted by the bitcount.

evaluate(p, y)

Evaluate polynomial by replacing variable :x by y. y may be an object which can be converted to basetype(p) or another polynomial. Convenient method ot evaluate is is p(y).

expo2ord(a)

bijective mapping from tuples of non-negative integers to positive integers.

The induced order of tuples is degrevlex.

expo2ordblock(::Type{<:Polynomial}, a::Vector{Int})

Return Integer or tuple of Integer representing the monomial ordering. In the first case, or if the tuple has length one, that is the :grevlex order, otherwise a block order, based on :grevlex, including :lex, if each variable block consists of one variable.

exponents(u::UnivariatePolynomial)

Return the list of exponents with non-zero coefficient.

exposum(a::Polynomial, i, b::Polynomial, j)

Return the sum of variable exponents at a.ind[i] and b.ind[j]. Realizes multiplication of monomials. If one of the coefficients is undefined, returnmaxindex` symbolizing zero.

fact_mult_order(::Type{<:Ring})

Return the Primes factorization of the order of the multiplicative group

factor(u::UnivariatePolynomial, a::Integer; p0 = MINPRIME)

factorize polynomial u(x^a) over ZZ.

factors(n)
factors(Primes.factor(n))

Return an iterator generating all factors of integer n.

fft!(n, F:Vector{R}, dd, z, W::Vector) where R

Special case of fft over the quotient ring R[X]/(X^dd + 1) for n and dd powers of 2, using principal 2ddth root of unity ω = X^z, ω^dd == -1.

Result overwrites input F. W is workspace of same size as F. Assume n * dd == length(F).

fft2(n, f::AbstractVector{R}, w::R) where R<:Ring

Calculate Fast Fourier Transform of degree n (power of 2) for f (length(f) <= n is filled up with 0). Given w a nth principal root of R(1). (w^n == 1 && w^(n/2) == -1). For efficiency reasons, w may be substituted by precalculated[1, w, w^2, ..., w^(n/2-1)]`.

fibonacci(n)

Calculate the n^th Fibonacci number F_n. (F_0 = 0, F_1 = 1, F_n+1 = F_n + F_n-1) Valid for all integer n.

Algorithm by D. Takahashi / Information Processing Letters 75 (2000) 243–246

generator(::Type{<:GaloisField})

Return the generator element of this implementation of Galois field.

generator(::Type{<:Ring})

Return the first primitive element of given iterable ring.

generators(P)

Return an array of all monomial generators (variables) of a polynomial type P.

gettypevar(t::Type)

Return value, which has previously been associated with this type

groebnerbase(H::AbstractVector{<:Polynomial})

Calculate the reduced groebner base from a set of generators of an ideal <H>.

see for example: https://en.wikipedia.org/wiki/Gr%C3%B6bnerbasis http://www.crypto.rub.de/imperia/md/content/may/12/ws1213/kryptanal12/13buchberger.pdf

hensel_lift(u, v::Vector, a::Vector) -> V, A

Given integer polynomial u to be factorized, a vector v of polynomials over Z/q and a corresponding vector of Bezout factors a over Z/p. q is an integer power of p.

Create output vector V of polynomials over Z/(p*q)

Algorithm see "D. Knuth - TAoCP 2.Ed 4.6.2 Exercise 22" and "E. Kaltofen - Factorization of Polynomials"

Assumptions fo the input

• u = LC(u) * prod(v) mod q
• sum( a .* prod(v) ./ v) = 1 mod p - (bezout_sum(a, v) == 1).

In the case u is not monic, the factor lc(u) has been multiplied into v[1]: lc(v[1]) == lc(u) mod p and lc(v[i]) = 1 for i > 1.

The output vector V contains polynomials of same degree as corresponding v. The input relations are propagated to the output V and A modulo p * q.

hermite_normal_form(A::AbstractMatrix{R}) where R<:Ring -> H, U

Calculate matrixes H in column Hermite normal form and unimodular U with A * U = H. Unimodular means det(U) is unit element of the ring R.

See Wiki Algorithm

homomorphism(R, S [,nr=0])

Return a function iso: R -> S, which describes an homomorphism between two Galois fields R and S of the same characteristic. If R == S that are the Frobenius automorphisms, if order(R) == order(S) isomorphisms, in the case of dim(S) == dim(R) * s with s > 1 the (injective) monomorphisms.

The optional nr ∈ 0:r-1 produces all possible monomorphisms (automorphisms) between R and S. In the automorphism case, nr = 0 is the identity.

hypercube(x, n, EnumPolynomial(), [EnumFull(), EnumHalf()])

Return the x-th n-tuple of integers where the last element is not zero. The implied order is no way canonical.

hypercube(x, n, EnumCube(), [EnumFull(), EnumHalf()])

Return the x-th n-tuple of integers. Start with zero-tuple for x == 0. The tuples 0:(2k+1)^n - 1 are contained in n-dimensional hypercube [-k:k]^n. Tuple number (2k+1)^n - 1 is always -k*ones(n). The implied order is no way canonical.

ilog(base::Integer, a::Integer)::Int

For nonzero integers a > 0 return Int(floor(log(abs(a)) / log(base))) exact arithmethic. For zero return -1

ilog2(a::Integer)::Int

For nonzero integers a return Int(floor(log2(abs(a)))) exact arithmethic. For zero return -1

ilog3(a::Integer)::Int

For nonzero integers a > 0 return Int(floor(log(abs(a)) / log(3))) exact arithmethic. For zero return -1

index2expo(p::Polynomial, i::Integer)

Return the tuple of variable exponents stored at this index (of p.ind).

index2indexdegree(x) -> (dx, degree)

Return the degree-relative index and the degree of the element at position x.

index2row(x)

For the zero based index x return the row id, in which the element number x is located.

index_of_select(v::AbstractVector{<:Integer}[, Type{<:Integer}])

Gives the one-based index of integer vector v in the canonical sequence of select_k_from_n. Reverse of select_k_from_n. Assuming v is strictly sorted and positive.

indexdegree2index(dx, d) -> index

Return the index of the element , which is identified by its degree-relative index and its degree.

insert_zeros!(FF, F, j, n, d)

Fill vector FF of length 2n with chunks [F[j*n+1:j*n+d]; zeros(d)]... taken form F. If length of F is not sufficient, it is virtually filled with zeros.

intpower(a, b)

Calculate a ^ b in appropriate result type.

inv_hypercube(v::AbstractVector{<:Integer}, EnumCube(), [EnumFull(), EnumHalf()])

For a given integer vector v return the index x, which reconstructs v via hypecube.

x = inv_hypercube(v)

implies

v = hypercube(x, length(v))

invert(p, q)

Inverse of p modulo q, where both are polynomials of the same type. If the base type is not a field, typically no inverse exists.

iroot(a::Integer, n::Integer)

Integer root: the largest integer m such that m^n <= a. Assumes a >= 0 and n > 0.

::UnivariatePolynomial{<:QuotientRing} irreducible(P, n, nr=0)

Returns an irreducible polynomial with in P with degree n. Skip first nr hits.

irreducibles(P, n)

Returns iterator of all irreducible monic polynomials in P with degree n.

iscoprime(a, b)

Return if there is no non-unit common divisor of a and b.

iscoprime(a, b)

Return if there is a common non-unit divisor of a and b.

isdiv(a, b)

Return if ring element a is dividable by b without remainder.

isfield(::Type{<:Ring})

Return iff type is a field (all elements except zero are invertible).

isinvertible(a, b)

Return if there is an inverse of a mod b.

isirreducible(p::R)

Return iff p is neither 0 nor a unit nor a product of non-units of R.

isirreducible(p::F[X])

Returns iff p is an irreducible (prime) polynomial over field F. See also factor.

ismonic(p::Polynomial)

Return iff leading coefficient LC of polynomial p is one.

ismonom(p::Polynomial)

Return iff polynomial p is identical to its leading term ond not 0.

isnegative(a::Ring)

Check if a < 0.

isprimitive(g::G)

Return iff g is a primitive element of its ring (its powers form the complete multiplicative subgroup of G)

isreducible(p::R)

Return iff p is neither 0 nor a unit nor irreducible in R.

iszerodiv(q::R) where R<:Ring

Return true iff q is not a zero divisor in R

jacobi(k, n)

Calculate Jacobi symbol of k over n. 0 < n && isodd(n), jacobi(k, n) ∈ {-1, 0, 1}.

joinpoly(p::Polynomial{<:Polynomial}, var)

Convert polynomial of polynomials to multivariate polynomial with variables var.

killmemo!(mf::Function)

Empty memory of memoized function mf.

kronecker(k, n)

Calculate Kronecker symbol of k over n. Generalization of jacobi without restrictions to n or k. kronecker(k, n) ∈ {-1, 0, 1}`

l0prod(v, n)

Return pprod(v, n)[0] efficiently.

l1prod(v, n)

Return pprod(v, n)[0:1] efficiently.

lcunit(p::Polynomial)

Returns leading coefficient lco if that is a unit, otherwise lcunit(lco).

lcunit(r::Ring)

Return a unit element s of the same ring or of an object, which may be promoted to this ring, so r / s has a simplified form. Example, for a polynomial over a field, the leading coefficient. For numbers, return 1 or -1 depending on the sign.

lift!(fac, i)

Replace (u, v, a) = fac[i] with a list of lifted (U, V, A). This list fac contains one entry for each factor of u, which could be found, but none of the U needs to be irreducible.

lll_repeated(A, result=[]; imax, igap)

Repeatedly call C, = lll_reduce(B), initially with B = A, then B = C[:,pcol], where pcol is a permutation of the columns of C. Record all suboptimal solutions of norm(C, 1) in result. Stop iteration as soon as after igap iterations the optial value did not change, at most imax iterations.

log_zech(k::Integer, G::Type{<:GaloisField})

If α is the generator of G, for k >= 0 return the log(α^k + 1), for k < 0 return 0. In other words: α ^ log_zech(k, G) == α ^ k + 1 for k >= 0.

logmonom(::Type{<:GaloisField})

Return numeric representation of generator (in range 0:order(G)-1). Ideally == characteristic(G).

lu_axu(A, u)

Calculate partial lu-factorization of [u A*u A^2*u A^(rank-1)*u] with row pivoting. Return LU_total factorization where L and R are extended by unit base. As second output return A^rank*u.

lu_total!(A::AbstractMatrix)

Compute partial L-U factorization of general matrix A.

Left upper rxr A is regular. right lower corner consits of elements a with abs(a) == 0 The element type must assure, that isunit(a) <=> abs(a) != 0 0 <= abs(a) ∈ Real Input matrix A is overwritten with the components of L and U. Return r = rank(A) and permutation vectors for rows and columns

lucas(n)

Calculate the n^th Lucas number L_n. (L_0 = 2, L_1 = 1, L_n+1 = L_n + L_n-1)

matrix(rnf::RNF)

Return matrix in 'rational normal form' from rnf-factorization of a square matrix. The form is also known as 'Frobenius normal form' or 'rational canonical form'. The matrix is a unique block diagonal matrix containing the companion matrices of the minimal polynomials. See also polynomials.

matrix(rnf::SNF)

Return matrix in 'Smith normal form' from snf-factorization of a matrix A. The matrix has the same shape as the original matrix, and only the leading diagonal elements are different from zero. Each diagonal element divides its successor, if applicable.

matrix(rnf::WNF)

Return matrix in 'Weierstrass normal form' from wnf-factorization of a square matrix. The matrix is a block diagonal matrix containing the companion matrices of powers of irreducible polynomials. See also wnf_polynomials. They are factors of the minimal polynomials for the rational normal form.

memoize(f)

Return a memoized version of one-arg function f.

If used recursively make sure that the new function is called. It can be stored in a global constant to keep the data accessible.

mfactor(p::UnivariatePolynomial)

Like factor. Memoize all intermediate results.

Memory is reset using killmemo!(mfactor).

minimal_polynomial(A::AbstractMatrix)

Calculate the minimal polynomial m_A of a square matrix A over a ring.

m_A is the minimum degree monic polynomial with m_A(A) == 0.

minimal_polynomial(A::AbstractMatrix{F}, u::AbstractVector{F}) where F<:Ring (field)

Calculate the local minimal polynomial m_A_u of a square matrix A over a ring for vector u.

m_A_u is the minimum degree monic polynomial with m_A_u(A)*u == 0

moebius(n)

Calculate Moebius function of n.

monom(::Type{<:Polynomial}, expos::Vector{Int})

Return monic monomial with given exponent(s). (monom(Z[:x.:y],[1,2]) == x * y^2)

monom(::Type{<:UnivariatePolynomial}, n = 1)

Return monic monomial of degree n.

mult_by_monom(p, k)

Return a new polynomial with the same coefficient vector, and ord increased by k.

mult_by_monom(p, k)

Return a new fraction of polynomials, multipled by x^k.

mult_order(R::Type{<:Ring})

order of multiplicative subgroup of R.

multideg(p::Polynomial)

Return vector of variable exponents of the leading monomial of p.

necklace(q, n)

Return the value of the necklace polynomial of order n at q.

Return count of irreducible monic polynomials of degree n over ZZ/x.

Sometimes also called "Moreau's necklace-counting function". The necklace polynomial of degree in polynomial ring R is obtained by calling necklace(monomial(R), n).

new_class(t::Type{<:Ring{T}}, args...) where T<:RingClass

Store type variable T(args...) for t and return t. The return value can be used to create ring elements of the new class. Example:

    ZZp = new_class(ZZmod{:p,BigInt}, 1000000000000000000000000000057)
    element = ZZp(123456)^10000000

normalbase(::Type{Q})

Find the first a in Q for which normalmatrix(a) is regular.

normalmatrix(a::Q[, m])

Return a matrix of element type ZZ/p, whose colums are the coefficient vectors of a^(p^i) for i = 0:m-1.

Here Q is a galois field of characteristic p and order p^r.

m m defaults to r.

If normalmatrix(a)) is regular, the field elements a^(p^i) for i = 0:r-1 form a base of Q as a vector space over ZZ/p (a normal base).

normalmatrix(::Type{Q}[, m])

Return normalmatrix(a, m) for the first a in Q for which this has maximal rank.

g, ag, bg = normgcd(a, b)

Divided a and b by the gcd of their contents.

num_irreducibles(::Type{<:UnivariatePolynomial{F}}, r)

Number of irreducible polynomials over F of degree r.

num_primitives(::Type{G})

Number of primitive elements (generators of multiplicative group) of GaloisField G.

ofindex(num::Integer, G) where G <: GaloisField

Ring element constructor. num is not the canonical homomorphism, but enumerates all elements of GF(p, r) in 0:p^r-1. The numbers ofindex.(0:p-1,G) correspond to the base field, and ofindex(p, G) to the polynomial x in the representation of Q.

ord(p::UnivariatePolynomial)

Return the multiplicity of 0 as a root of p. For p == 0 return 0.

ord2expo(n, d)

bijective mapping from integers to d-tuples of integers.

The induced order of tuples is degrevlex.

order(z::Ring)

Returns the order of the cyclic multiplicative group generated by z, or 0 if z^k != 1 for all integers k.

order(::Type)

Returns the number of elements of (finite) ring Z or 0 if |Z| == inf.

pade(p, m, n)

Calculate Padé approximation of order m / n for polynomial or series p.

If deg(p) is greater than m + n, the higher terms of p are ignored.

The Padé approximant is a rational function R(x) = P(x) / Q(x) with polynomials with deg(P) ≤ m + ord(p), deg(Q) ≤ n and Q(0) = 1.

It is defined by the coincidence of the derivatives of p and R of degrees less than or equal m + n + ord(p) at 0.

If m or n are not given, in the case of univariate polynomials, appropriate default values are provided.

pade_normal!(p::Frac)

Normalize rational function by multiplying denominator and numerator polynom in order to change least significant term of denominator to one.

q, r, f = pdivrem(a::T, b::T) where T<:UnivariatePolynomial{R}

A variant of divrem, if leading term of divisor is not a unit. The polynomial a is multiplied by a minimal factor f ∈ R with f * a = q * b + r.

pgcd(a, b)

Pseudo gcd of univariate polynomials a and b. Uses subresultant sequence to accomplish non-field coeffient types.

g, u, v, f = pgcdx(a, b)

Extended pseudo GCD algorithm. Return g == pgcd(a, b) and u, v, f with a * u + b * v == g * f.

pivot(A, i, j)

Find maximal element in A[i:end,j]

polynomials(rnf::RNF)

Return the sequence of minimal polynomials P with P[1] multiple of P[2] ...

polynomials(rnf::WNF)

Return the sequence of pairs of irreducible polynomials and powers.

positionsin(va, vb)

Return integer array of the same size as va. Element i is the index of first va[i] in vb or zero, if missing.

powerdiv(s::Integer, x::Integer, p::Integer)

Calculate div(s, x^p)without overflow fors, x, p >= 0`. Terminate calculation as soon as it is evident that the result will be zero.

powersum(h, ex, f)

Calculate the sum h + h^2 + h^4 + h^8 + ... + h^ex mod f

pprod(v::Vector, n::{Integer,BitVector})

Product of elements of v, with corresponding bit in n is set. (lsb corresponds to index 1).

presultant_seq(a, b)

Modification of Euclid's algorithm to produce subresultant sequence of pseudo-remainders. The next to last calculated remainder is a scalar multiple of the gcd. Another interpretation of this remainder yields the resultant of a and b. See: WIKI: Subresultant and TAoCP 2nd Ed. 4.6.1.

primefactors(n::Integer)

Return an iterator over the prime factors of n, sorted.

primpart(p::Polynomial)

The primitive part of the polynomial p, equals p / content(p). If the basetype is QQ, returned polynomial has basetype ZZ.

prod_pvm(p, A, v)

Calculate p(A) * v where p is a polynomial, A a matrix, and v an array.

prototype(::Type{<:Polynomial}, n1, n2)

Return polynomial of given type as sum of monic monomials.

The degree of each variable is limited by n1, the total degree by n2.

pushmemo!(f::Function, v)

Push v to memory of memoized function.

randlattice([rng,] n, p)

Create "random" nxn - integer lattice base with maximal entry of p. Result is the matrix of columns of the base.

randm([rng,], n::Int, k::Int, r, T) where T<:Integer

Create "random" integer unimodal nxn transformation matrix M by repeatedly compose elementary operations (add multiple of column i to column j).

The number of operations is limited by k, and norm(M, Inf) <= rmax. The elemental multiplicity is restricted by max(1, r / norm(M, Inf)) at every step.

rational_normal_form(A::AbstractMatrix{field})

Calculate the rational canonical form factorization of square matrix A. Element type of A must be a field. The form is also known as 'Frobenius normal' form or 'rational canonical form'.

@see:

The algorithm is derived from the lecture notes 'Klaus Bongartz, Normalformen von Matrizen' https://www2.math.uni-wuppertal.de/~bongartz/Normalformen.pdf

rational_relationship(a; e=1e-5, c=1e9)

Given a vector of numbers a, find small integers m such that m' * a is small. The constant c is used to set up the initial matrix to be lll_reduced.

reducible(P, n, nr=0)

Returns a reducible polynomial with in P with degree n. Skip first nr hits.

reducibles(P, n)

Returns iterator of all reducible monic polynomials in P with degree n.

reduction(p::Polynomial)

Return polynomial q and integers nord, g, nex with p == q * x^ord and q(x) == qq(x^g) for some qq. nex is the number of nonzero coefficients of q.

reindex2(values, pos, n)

Return an array of integers of size n such that result[pos] = val. Default values in result are zero. The indices with pos[i] == 0 are silently ignored.

remove_subset(v::Vector, bitmask::BitVector)

Delete vector element v[i] for all i with bitmask[i] == 1.

resultant(a, b)

Calculate resultant of two univariate polynomials of general coeffient types.

resultant_naive(u, v)

Reference implementation of resultant (determinant of sylvester matrix)

revert(a::Int, n::Int, base::Int)

Represent a in a n-digit system given by base, revert positions and return "reverse" of a.

revert(a::Int, b::Int)

Return a with bits 0:n-1 in reverse order.

revert(a::Int, v::Vector)

Represent a in a digit system given by v, revert positions and return "reverse" of a.

row2degree(r)

Return the maximal degree of elements in row number r. This is the fundamantal definition of the shape of the table.

row2index(r)

For row id r return index of degree 0 element of that row. Rows are zero-based.

rowdivgcd!(b::Matrix, i, k, ij, s)

Divide row b[i,k::end] by the gcd of that row. Return gcd, index of a now unit element of the row, s * gcd

Multiply by x^(z*j) modulo x^n + 1 all polynomials F[j*n+1:j*n+n] contained in F.

schoenhage_strassen(F, G, n, FF, GG, W) -> (FF, m)

Like shoenhage_strassen(F, G, n) but using preallocated working spaces FF, GG, W. On return FF is keeping the compete result, while F[1:m] is the result.

schoenhage_strassen(F, G, n)

Calculate product of polynomials with coefficients F and G, both with degree < n. Return result modulo x^n + 1. The size of the result vector is reduced to minimum.

Allocates working space of 3 * 2n.

schoenhage_strassen_algo(P, Q, n::Integer)

For polynomials P and Q with degree < n calculate P * Q mod x^n + 1. The element type of P and Q must have invertible 2.

n must be a power of 2 or 0, in latter case the smallest possible value is calculated.

Only the principle of the algorithm is demonstrated. The implementation does not allow the estimated efficiency gains.

select_k_from_n(x, n, k)

For x in the range 0:binomial(n,k)-1 find subset of size k of 1:n with number x. Each subset is represented by an ordered vector of integers from 1:n. The order given to the subsets is by reverse tuple order (last element most significant).

settypevar!(f::Function, t::Type)

Associate type with value f(). f is called only once per type. The value can be retrieved by calling gettypevar(t).

settypevar!(t::Type, value)

Associate type with a value. The second call for the same type is gnored. The value can be retrieved by calling gettypevar(t).

sff(p)

Square-free factorization. Algorithm to split polynomial p into a product of powers of squarefree factors. Return an array of pairs of squarefree factors and corresponding powers.

shiftleft(vector, integer)

Increase size of vector by s, copy content and fill lower indices with zeros.

shrink!(A, d, δ)

Reduce size of A from orinally 2*d*δ to d*δ by adding chunks A[j*2d+1:j*2d+2d] to A[j*d+1:j*d+2d] for j ∈ 0:δ-1. Special treatment of last d to relize multiplication modulo x^(d*δ) + 1.

signedsubresultantpolynomials(P::T, Q::T) where {S,T<:UnivariatePolynomial{S}}

This code is taken from "Algorithm 8.21 (Signed Subresultant Polynomials)" "Algorithms in Real Algebraic Geometry" by Basu, Pollak, Roy - 2006. Its use is restricted to the case of S is an integral domain (there is no non-trivial divisor of zero). Effort is O(deg(p)*deg(q)).

sintern(a)

Return a symbol, which uniquly identifies the argument.

sized(a::Vector, r)

Return a vector of length r, which starts with a and is filled up with zeros if required.

smallfactors(vv::Vector{Polynomial{ZZ/p}}, u::Polynomial{ZZ{Integer}})::w

Assuming vv is an array of r factors of integer polynomial u modulo p, return an iterator over products of factors from vv. The iterator elements are tuples (n, w), where n is an integer in 0:2^r-1 and w = pprod(vv, n). The elements w have the property deg(w) < deg(u)/2 or deg(w) == deg(u)/2 && ( count_ones(n) < r/2 || count_ones(n) == r/2 && isodd(n) ).

smith_normal_form(matrix)

Calculate Smith normal form including transformation matrices of a matrix over a PID.

Decomposes S * A * T == D where D is a diagonal matrix. See also: SNF

v = splitmod(a, m)

Find v which divides m in a way that gcd(v, m/v) == 1. The input a < m with `gcd(a, m) != 1 serves as a starting point.

splitpoly(p::MultivariatePolynomial, var1, var2)

Construct a new polynomial with variables var1 of polynomials with variables var2.

The sets of variable names var1 and var2 must be disjoint subsets of the varnames of p.

stripzeros(q)

count and remove trailing zero coefficients.

swapcols(A, pc, i, j)

Swap columns A[:,i] with A[:,j] and pc[i] with pc[j]

swaprows(A, pr, i, j, cols)

Swap rows A[i,cols] with A[j,cols] and pr[i] with pr[j]

sylvester_matrix(u::P, v::P) where P<:UnivariatePolynomial

Return sylvester matrix of polynomials u and v.

testrules(io, g)

Test associativity and distributivity for all element combinations from g. Print messages to io if errors found. g can be a collection of Ring elements or a subtype of Ring (which is iterable).

transformation(rnf::RNF)

Return a transformation matrix in the RNF factorization of a square matrix. The transformation matrices are not unique.

transformation(rnf::SNF)

Return a transformation matrices in the Smith normal form a matrix. The transformation matrices are not unique.

transformation(rnf::WNF)

Return a transformation matrix in the RNF or WNF factorization of a square matrix. The transformation matrices are not unique.

uncompress(p, n)

Return polynomial p(x^n).

Same as spread

uptype(a, [T::Type])

promote a to get at least type promote_type(typeof(a), T).

value(a::ZZmod{m,T})

Return unique signed(T) integer in the range [-m/2, m/2) representing a, where m is the modulus.

varname(P)

Return variable name of univariate polynomial or polynomial type P as a symbol.

varnames(P)

Return array of variable names of polynomial or polynomial type P.

weierstrass_normal_form([rnf,] matrix)

Calculate Weierstrass normal form of a matrix over a field.

If rnfis given, it is assumed, that it is the rational normal form of the same matrix.

yun(u::UnivariatePolynomial)::Vector

Split integer polynomial p into coprime factors u_i for i = 1:e such that p = u_1^1 * u_2^2 * ... * u_e^e.

zassenhaus_irr(u)

Returns true iff the squarefree polynomial u is irreducible.

factor(p::F[:x])

Factorize polynomial in F[X] where F is a field (ZZ/p or GF(p,m) with p prime number).

isprime(p::R)

Return iff p is neither 0 nor a unit and for any a,b ∈ R if p divides a*b then p divides a or p divides b.