CommutativeRings.Conway.conwayFunction
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.

CommutativeRings.Conway.has_conway_property2Method
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.

CommutativeRings.Conway.has_conway_property3Method
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.

CommutativeRings.Conway.quasi_conwayFunction
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.

CommutativeRings.SpecialPowerSeries.EinMethod
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)| < π
CommutativeRings.SpecialPowerSeries.lin1pMethod
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
CommutativeRings.FracType
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}.

CommutativeRings.FractionRingType
FractionRing{S<:RingInt,T<:FractionRingClass}

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

CommutativeRings.MultivariatePolynomialType
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.

CommutativeRings.PowerSeriesType

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

CommutativeRings.QuotientType
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.

CommutativeRings.QuotientRingType
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.

CommutativeRings.RNFType
RNF(polynomials, transformation)

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

CommutativeRings.RingType
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.

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

CommutativeRings.UnivariatePolynomialType
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.

CommutativeRings.UnivariatePolynomialMethod
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.

CommutativeRings.VectorSpaceMethod
VectorSpace(v::AbstractVector...)

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

CommutativeRings.WNFType
WNF(polynomials, transformation)

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

CommutativeRings.ZZType
ZZ{S<:Signed}

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

CommutativeRings.ZZmodType
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.

Base.intersectMethod
intersect(v1::V, v2::V)::V where V<:VectorSpace

Intersection of two vector spaces.

Base.logMethod
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.

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

Base.reverseMethod
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.

Base.sqrtMethod
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.

Base.sqrtMethod
sqrt(s::PowerSeries)

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

Base.sumMethod
sum(v1::V, v2::V)::V where V<:VectorSpace

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

CommutativeRings.GCDMethod
GCD(u::P, v::P) where P<:UnivariatePolynomial

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

CommutativeRings.GFFunction
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.

CommutativeRings.GFImplFunction
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])
CommutativeRings.LCMethod
LC(r::Ring)

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

CommutativeRings.LCMethod
LC(p::Polynomial)

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

CommutativeRings.LTMethod
LT(p::Polynomial)

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

CommutativeRings.SPOLMethod
SPOL(f, g)

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

CommutativeRings._divremMethod
_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.

CommutativeRings.adjugateMethod
adjugate(A::AbstractMatrix{<:Ring})

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

CommutativeRings.all_factors_irreducible!Method
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.

CommutativeRings.allgcdxMethod
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.

CommutativeRings.allzerosMethod
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.

CommutativeRings.bestpowersMethod
bestpowers(n::Integer, p::Vector{Integer})

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

CommutativeRings.bezout_sumMethod
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.

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

CommutativeRings.characteristicMethod
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.

CommutativeRings.characteristicMethod
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.

CommutativeRings.characteristic_polynomialFunction
characteristic_polynomial(A[, P])

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

CommutativeRings.coeffboundsMethod
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.

CommutativeRings.coeffsMethod
coeffs(p::UnivariatePolynomial)

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

CommutativeRings.combinefactorsMethod
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.

CommutativeRings.companionMethod
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.

CommutativeRings.compose_invMethod
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".

CommutativeRings.compressMethod
compress(p, n)

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

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

CommutativeRings.convolute_all!Method
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.

CommutativeRings.convolute_j!Method
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.

CommutativeRings.crtMethod
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.

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

CommutativeRings.ddfMethod
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.

CommutativeRings.degMethod
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.

CommutativeRings.degMethod
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.

CommutativeRings.degree2rowMethod
degree2row(d)

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

CommutativeRings.deriveMethod
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.

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

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

CommutativeRings.det_BirdMethod
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

CommutativeRings.det_DJBMethod
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.

CommutativeRings.det_MVMethod
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

CommutativeRings.det_QRMethod
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.

CommutativeRings.dimensionMethod
dimension(::Type)

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

CommutativeRings.divides_maybeMethod
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.

CommutativeRings.divremvMethod
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.

CommutativeRings.edfMethod
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.

CommutativeRings.enumxMethod
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.

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

CommutativeRings.expo2ordMethod
expo2ord(a)

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

The induced order of tuples is degrevlex.

CommutativeRings.expo2ordblockMethod
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.

CommutativeRings.exposumMethod
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.

CommutativeRings.factorsMethod
factors(n)
factors(Primes.factor(n))

Return an iterator generating all factors of integer n.

CommutativeRings.fft!Method
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).

CommutativeRings.fft2Method
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)].

CommutativeRings.fibonacciMethod
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

CommutativeRings.groebnerbaseMethod
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

CommutativeRings.hensel_liftMethod
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.

CommutativeRings.hermite_normal_formMethod
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.

CommutativeRings.homomorphismFunction
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.

CommutativeRings.hypercubeMethod
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.

CommutativeRings.hypercubeMethod
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.

CommutativeRings.ilogMethod
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

CommutativeRings.ilog2Method
ilog2(a::Integer)::Int

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

CommutativeRings.ilog3Method
ilog3(a::Integer)::Int

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

CommutativeRings.index2rowMethod
index2row(x)

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

CommutativeRings.index_of_selectMethod
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.

CommutativeRings.insert_zeros!Method
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.

CommutativeRings.inv_hypercubeMethod
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))
CommutativeRings.invertMethod
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.

CommutativeRings.irootMethod
iroot(a::Integer, n::Integer)

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

CommutativeRings.irreducibleMethod

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

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

CommutativeRings.isirreducibleMethod
isirreducible(p::F[X])

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

CommutativeRings.ismonomMethod
ismonom(p::Polynomial)

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

CommutativeRings.isprimitiveMethod
isprimitive(g::G)

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

CommutativeRings.jacobiMethod
jacobi(k, n)

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

CommutativeRings.joinpolyMethod
joinpoly(p::Polynomial{<:Polynomial}, var)

Convert polynomial of polynomials to multivariate polynomial with variables var.

CommutativeRings.kroneckerMethod
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}

CommutativeRings.lcunitMethod
lcunit(p::Polynomial)

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

CommutativeRings.lcunitMethod
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.

CommutativeRings.lift!Method
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.

CommutativeRings.lll_repeatedFunction
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.

CommutativeRings.log_zechMethod
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.

CommutativeRings.logmonomMethod

logmonom(::Type{<:GaloisField})

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

CommutativeRings.lu_axuMethod
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.

CommutativeRings.lu_total!Method
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

CommutativeRings.lucasMethod
lucas(n)

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

CommutativeRings.matrixMethod
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.

CommutativeRings.matrixMethod
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.

CommutativeRings.matrixMethod
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.

CommutativeRings.memoizeMethod
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.

CommutativeRings.minimal_polynomialMethod
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.

CommutativeRings.minimal_polynomialMethod
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

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

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

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

CommutativeRings.new_classMethod
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
CommutativeRings.normalmatrixMethod
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).

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

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

CommutativeRings.ofindexMethod
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.

CommutativeRings.ordMethod
ord(p::UnivariatePolynomial)

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

CommutativeRings.ord2expoMethod
ord2expo(n, d)

bijective mapping from integers to d-tuples of integers.

The induced order of tuples is degrevlex.

CommutativeRings.orderMethod
order(z::Ring)

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

CommutativeRings.orderMethod
order(::Type)

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

CommutativeRings.padeFunction
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 Padé 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.

CommutativeRings.pade_normal!Method
pade_normal!(p::Frac)

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

CommutativeRings.pdivremMethod
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.

CommutativeRings.pgcdMethod

pgcd(a, b)

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

CommutativeRings.pgcdxMethod

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.

CommutativeRings.polynomialsMethod
polynomials(rnf::RNF)

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

CommutativeRings.positionsinMethod
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.

CommutativeRings.powerdivMethod
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.

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

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

CommutativeRings.presultant_seqMethod

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.

CommutativeRings.prod_pmvMethod
prod_pvm(p, A, v)

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

CommutativeRings.prototypeMethod
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.

CommutativeRings.randlatticeMethod
randlattice([rng,] n, p)

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

CommutativeRings.randmMethod
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.

CommutativeRings.rational_normal_formMethod
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

CommutativeRings.rational_relationshipMethod
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.

CommutativeRings.reducibleMethod
reducible(P, n, nr=0)

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

CommutativeRings.reductionMethod
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.

CommutativeRings.reindex2Method
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.

CommutativeRings.remove_subset!Method
remove_subset(v::Vector, bitmask::BitVector)

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

CommutativeRings.revertMethod
revert(a::Int, n::Int, base::Int)

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

CommutativeRings.revertMethod
revert(a::Int, v::Vector)

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

CommutativeRings.row2degreeMethod
row2degree(r)

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

CommutativeRings.rowdivgcd!Method
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

CommutativeRings.scale!Method

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

CommutativeRings.schoenhage_strassen!Method
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.

CommutativeRings.schoenhage_strassenMethod
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.

CommutativeRings.schoenhage_strassen_algoMethod
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.

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

CommutativeRings.settypevar!Method
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).

CommutativeRings.settypevar!Method
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).

CommutativeRings.sffMethod
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.

CommutativeRings.shrink!Method
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.

CommutativeRings.signed_subresultant_polynomialsMethod

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

CommutativeRings.sizedMethod
sized(a::Vector, r)

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

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

CommutativeRings.splitmodMethod
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.

CommutativeRings.splitpolyMethod
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.

CommutativeRings.swapcolsMethod
swapcols(A, pc, i, j)

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

CommutativeRings.swaprowsMethod
swaprows(A, pr, i, j, cols)

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

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

CommutativeRings.transformationMethod
transformation(rnf::RNF)

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

CommutativeRings.transformationMethod
transformation(rnf::WNF)

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

CommutativeRings.valueMethod
value(a::ZZmod{m,T})

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

CommutativeRings.weierstrass_normal_formMethod
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.

CommutativeRings.yunMethod
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.

Primes.factorMethod
factor(p::F[:x])

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

Primes.isprimeMethod
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.