`CommutativeRings.RingInt`

— Type`RingInt`

Union of system `Integer`

types and any `Ring`

subtype.

`CommutativeRings.Frac`

— Type`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.FractionRing`

— Type`FractionRing{S<:RingInt,T<:FractionRingClass}`

Rational extension of elements of ring `S`

. Example the field of rational numbers.

`CommutativeRings.GaloisField`

— Type`G[num::Integer] 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 `G[0:p-1]`

correspond to the base field, and `G[p]`

to the polynomial `x`

in the representation of `Q`

.

`CommutativeRings.Hom`

— Type`Hom{function,R,R'}`

Represent a ring homomorphism `function:R -> R'`

.

`CommutativeRings.Ideal`

— Type`Ideal{R}`

Respresent in Ideal of Ring `R`

. Only Ideals with a finite (Groebner) basis.

`CommutativeRings.MultivariatePolynomial`

— Type`MultivariatePolynomial{S<:RingInt,N,Id}`

Polynomials of ring elemets `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.Polynomial`

— Type`Polynomial{S<:Ring,T<:PolyRingClass}`

`CommutativeRings.QQ`

— Type`QQ{S<:Integer}`

`CommutativeRings.Quotient`

— Type`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.QuotientRing`

— Type`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.Ring`

— Type`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.UnivariatePolynomial`

— Type`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.UnivariatePolynomial`

— Method`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.VectorSpace`

— Method`VectorSpace(v::AbstractVector...)`

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

.

`CommutativeRings.ZZ`

— Type`ZZ{S<:Signed}`

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

.

`CommutativeRings.ZZmod`

— Type`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.intersect`

— Method`intersect(v1::V, v2::V)::V where V<:VectorSpace`

Intersection of two vector spaces.

`Base.log`

— Method`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.reverse`

— Method`reverse(p::UnivariatePolynomial)`

Revert the order of coefficients. decrease degree if `p(0) == 0`

.

`Base.sum`

— Method`sum(v1::V, v2::V)::V where V<:VectorSpace`

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

`CommutativeRings.GCD`

— Method`GCD(u::P, v::P) where P<:UnivariatePolynomial`

Calculate `g = gcd(u, v) and return`

gcd(u, v), u / g, v / g`.

`CommutativeRings.GFImpl`

— Function`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.LC`

— Method`LC(p::Polynomial)`

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

`CommutativeRings.LC`

— Method`LC(r::Ring)`

Return the leading coefficient of `r`

. For non-polynomials return `r`

itself.

`CommutativeRings.LT`

— Method`LT(p::Polynomial)`

Return leading term of polynomial `p`

. Coefficient is taken from `p`

.

`CommutativeRings.SPOL`

— Method`SPOL(f, g)`

Calculate the S-polynomial (`SPOL`

) of the polynomials `f`

, `g`

.

`CommutativeRings.adjugate`

— Method`adjugate(A::AbstractMatrix{<:Ring})`

The adjugate of matrix `A`

. Invariant is `det(A) * I == adjugate(A) * A == det(A) * I(n)`

.

`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.allgcdx`

— Method`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.allzeros`

— Method`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.aroot`

— Method`aroot(s, n)`

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

`CommutativeRings.axspace`

— Method`axspace(A, u, n)`

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

`CommutativeRings.bezout_sum`

— Method`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.cbin`

— Method`cbin(n, d)`

Calculate the greatest integer `c`

such that `binomial(c, d) <= n`

`CommutativeRings.characteristic`

— Method`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.characteristic`

— Method`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_polynomial`

— Function`characteristic_polynomial(A[, P])`

Characteristic polynomial of matrix `A`

. `P`

is an optional univariate polynomial type, defaulting to `eltype(A)[:x]`

`CommutativeRings.coeffbounds`

— Method`coeffbounds(u::Polygon, 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.combinefactors`

— Method`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). Return vector of tuples containing integer polynomial factors `U`

, `V`

vector with corresponding factorization, and `A`

corresponding factors. 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.companion`

— Method`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.complement`

— Method`complement(v::V)::V where V<:VectorSpace`

Complementary space of vector space.

`CommutativeRings.content`

— Method`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`

.

`CommutativeRings.cyclotomic`

— Method`cyclotomic(P, n)`

Calculate cylotomic polynomial of degree `n`

in polynom ring `P`

. This polynom is defined to be the disisor 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.ddf`

— Method`ddf(p)`

`Distinct-degree factorization`

. Input is a squarefree polynomial. Returns a list of pairs `g_i => d_i`

of polynomials g*i, each of which is a product of all irreducible monic polynomials of equal degree `d*i`. The product of all`

g_i == p`.

`CommutativeRings.deg`

— Method`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.deg_prod`

— Method`deg_prod(v, d)`

Calculate and return `deg(pprod(v, n))`

efficiently.

`CommutativeRings.degree2index`

— Method`degree2index(d)`

For degree `d`

return the index of the first element of that degree.

`CommutativeRings.degree2row`

— Method`degree2row(d)`

For degree `d`

return the row of the first element of that degree. Inverse of `row2degree`

.

`CommutativeRings.derive`

— Method`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.derive`

— Method`derive(p::MultivariatePolynomial, (d1,...dN))`

Derive polynomial with N variables with respect to variables `1`

... `N`

with the respective degrees `d1`

... `dN`

.

`CommutativeRings.det3_new`

— Method`det3(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_Bird`

— Method`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_DJB`

— Method`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_QR`

— Method`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.dimension`

— Method`dimension(::Type)`

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

`CommutativeRings.discriminant`

— Method`discriminant(a)`

Calculate discriminant of a univariate polynomial `a`

.

`CommutativeRings.divides_maybe`

— Method`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.edf`

— Method`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.enumx`

— Method`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.evaluate`

— Method`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.expo2ord`

— Method`expo2ord(a)`

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

The induced order of tuples is `degrevlex`

.

`CommutativeRings.expo2ordblock`

— Method`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.exposum`

— Method`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, return`

maxindex` symbolizing zero.

`CommutativeRings.fact_mult_order`

— Method`fact_mult_order(::Type{<:Ring})`

Return the Primes factorization of the order of the multiplicative group

`CommutativeRings.factormod`

— Method`factormod(u::Polynomial[; p0])`

The procedure may be repeated with increased `p`

. If the vector is empty, `p`

was one of those rare "unlucky" primes, which are not useful for this polynomial.

`CommutativeRings.factors`

— Method```
factors(n)
factors(Primes.factor(n))
```

Return an iterator generating all factors of integer `n`

.

`CommutativeRings.generator`

— Method`generator(::Type{<:GaloisField})`

Return the generator element of this implementation of Galois field.

`CommutativeRings.generators`

— Method`generators(P)`

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

.

`CommutativeRings.gettypevar`

— Method`gettypevar(t::Type)`

Return value, which has previously been associated with this type

`CommutativeRings.groebnerbase`

— Method`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%B6bner*basis http://www.crypto.rub.de/imperia/md/content/may/12/ws1213/kryptanal12/13*buchberger.pdf

`CommutativeRings.hensel_lift`

— Method`hensel_lift(u, v, a) -> V`

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

Assumptions fo the input u = prod(v) mod q sum( a .* prod(v) ./ v) = 1 mod p In the case u is not monic, the factor lc(u) has to be 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.

`CommutativeRings.homomorphism`

— Function`homomorphism(Q, R [,nr=0])`

Return a function `iso: Q -> R`

, which describes an homomorphism between two Galois fields `Q`

and `R`

of the same characteristic. If `Q == R`

that are the Frobenius automorphisms, if `order(Q) == order(R)`

isomorphisms, in the case of `order(R) == order(S)^s`

with s > 1 the (injective) monomorphisms.

The optional `nr ∈ 0:r-1`

produces all possible monomorphisms (automorphisms) between `Q`

and `R`

. In the automorphism case, `nr = 0`

is the identity.co

`CommutativeRings.hypercube`

— Method`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.hypercube`

— Method`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.ilog2`

— Method`ilog2(a::Integer)::Int`

For nonzero integers `a`

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

`CommutativeRings.index2expo`

— Method`index2expo(p::Polynomial, i::Integer)`

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

).

`CommutativeRings.index2indexdegree`

— Method`index2indexdegree(x) -> (dx, degree)`

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

.

`CommutativeRings.index2row`

— Method`index2row(x)`

For the zero based index `x`

return the row id, in which the element number `x`

is located.

`CommutativeRings.index_of_select`

— Method`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.indexdegree2index`

— Method`indexdegree2index(dx, d) -> index`

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

`CommutativeRings.intpower`

— Method`intpower(a, b)`

Calculate `a ^ b`

in appropriate result type.

`CommutativeRings.inv_hypercube`

— Method`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.invert`

— Method`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.iroot`

— Method`iroot(a::Integer, n::Integer)`

Integer root: the largest integer `m`

such that `m^n <= a`

. Assumes `a >= 0`

and `n > 0`

.

`CommutativeRings.irreducible`

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

Returns an irreducible polynomial with in `P`

with degree `n`

. Skip first `nr`

hits.

`CommutativeRings.irreducibles`

— Method`irreducibles(P, n)`

Returns iterator of all irreducible monic polynomials in `P`

with degree `n`

.

`CommutativeRings.iscoprime`

— Method`iscoprime(a, b)`

Return if there is no non-unit common divisor of `a`

and `b`

.

`CommutativeRings.iscoprime`

— Method`iscoprime(a, b)`

Return if there is a common non-unit divisor of `a`

and `b`

.

`CommutativeRings.isdiv`

— Method`isdiv(a, b)`

Return if ring element `a`

is dividable by `b`

without remainder.

`CommutativeRings.isfield`

— Method`isfield(::Type{<:Ring})`

Return iff type is a field (all elements except `zero`

are invertible).

`CommutativeRings.isinvertible`

— Method`isinvertible(a, b)`

Return if there is an inverse of `a`

mod `b`

.

`CommutativeRings.isirreducible`

— Method`isirreducible(p::F[X])`

Returns iff `p`

is an irreducible (prime) polynomial over field `F`

. See also `factor`

.

`CommutativeRings.ismonic`

— Method`ismonic(p::Polynomial)`

Return iff leading coefficient of polynomial `p`

is one.

`CommutativeRings.ismonom`

— Method`ismonom(p::Polynomial)`

Return iff polynomial `p`

consists is identical to its leading term.

`CommutativeRings.isnegative`

— Method`isnegative(a::Ring)`

Check if a < 0.

`CommutativeRings.isprimitive`

— Method`isprimitive(g::G)`

Return iff `g`

is a primitive element of its ring (its powers form the complete multiplicative subgroup of `G`

)

`CommutativeRings.isreducible`

— Method`isreducible(p::F[X])`

Returns iff `p`

is a reducible (prime) polynomial over field `F`

. See also `factor`

.

`CommutativeRings.iszerodiv`

— Method`iszerodiv(q::R) where R<:Ring`

Return true iff q is not a zero divisor in `R`

`CommutativeRings.l0prod`

— Method`l0prod(v, n)`

Return `pprod(v, n)[0]`

efficiently.

`CommutativeRings.l1prod`

— Method`l1prod(v, n)`

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

efficiently.

`CommutativeRings.lcunit`

— Method`lcunit(r::Ring)`

Return `one(r)`

if it's a unit, otherwise 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.

`CommutativeRings.leftfactor`

— Method`leftfactor(u)`

Find greatest integer `g`

such that `g^k`

divides `u[k]`

for all `k = 1:deg(u)`

`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.log_zech`

— Method`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.logmonom`

— Methodlogmonom(::Type{<:GaloisField})

Return numeric representation of generator (in range `0:order(G)-1`

). Ideally `== characteristic(G)`

.

`CommutativeRings.lu_axu`

— Method`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.minimal_polynomial`

— Method`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_polynomial`

— Method`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.monom`

— Method`monom(<:MultivariatePolynomial, expos::Vector{Int})`

Return monic monomial with given exponents. (`[1,0,...]`

corresponds to first variable).

`CommutativeRings.mult_order`

— Method`mult_order(R::Type{<:Ring})`

order of multiplicative subgroup of `R`

.

`CommutativeRings.multideg`

— Method`multideg(p::Polynomial)`

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

.

`CommutativeRings.necklace`

— Method`necklace(q, n)`

Return the value of the `necklace polynomial`

Count of irreducible monic polynomials of degree n over Z/q.

`CommutativeRings.new_class`

— Method`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.normalbase`

— Method`normalbase(::Type{Q})`

Find the first `a in Q`

for which `normalmatrix(a)`

is regular.

`CommutativeRings.normalmatrix`

— Method`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.normalmatrix`

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

Return `normalmatrix(a, m)`

for the first `a`

in `Q`

for which this ihas maximal rank.

`CommutativeRings.normgcd`

— Method`g, ag, bg = normgcd(a, b)`

Divided `a`

and `b`

by the gcd of their contents.

`CommutativeRings.num_irreducibles`

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

Number of irreducible polynomials over `F`

of degree `r`

.

`CommutativeRings.num_primitives`

— Method`num_primitives(::Type{G})`

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

.

`CommutativeRings.ord2expo`

— Method`ord2expo(n, d)`

bijective mapping from integers to `d`

-tuples of integers.

The induced order of tuples is `degrevlex`

.

`CommutativeRings.order`

— Method`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.order`

— Method`order(::Type)`

Returns the number of elements of (finite) ring `Z`

or `0`

if `|Z| == inf`

.

`CommutativeRings.pade`

— Method`pade(m, n, p)`

Calculate Padé approximation of order `n / m`

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`

, `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`

at `0`

.

`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.pdivrem`

— Method`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.pgcd`

— Method`pgcd(a, b)`

Pseudo gcd of univariate polynomials gcd`a`

and `b`

. Uses subresultant sequence to accomplish non-field coeffient types.

`CommutativeRings.pgcdx`

— Method`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.pivot`

— Function`pivot(A, i, j)`

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

`CommutativeRings.positionsin`

— Method`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.powerdiv`

— Method`powerdiv(s::Integer, x::Integer, p::Integer)`

Calculate `div(s, x^p)`

`without overflow for`

s, x, p >= 0`. Terminate calculation as soon as it is evident that the result will be zero.

`CommutativeRings.powersum`

— Method`powersum(h, ex, f)`

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

`CommutativeRings.pprod`

— Method`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_seq`

— Method`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: `https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Subresultant_pseudo-remainder_sequence`

and TAoCP 2nd Ed. 4.6.1.

`CommutativeRings.primpart`

— Method`primpart(p::Polynomial)`

The primitive part of the polynomial `p`

, equals `p / content(p)`

.

`CommutativeRings.prod_pmv`

— Method`prod_pvm(p, A, v)`

Calculate `p(A) * v`

where `p`

is a polynomial, `A`

a matrix, and `v`

an array.

`CommutativeRings.rational_normal_form`

— Method`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.reducible`

— Method`reducible(P, n, nr=0)`

Returns a reducible polynomial with in `P`

with degree `n`

. Skip first `nr`

hits.

`CommutativeRings.reducibles`

— Methodreducibles(P, n)

Returns iterator of all reducible monic polynomials in `P`

with degree `n`

.

`CommutativeRings.reindex2`

— Method`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.resultant`

— Method`resultant(a, b)`

Calculate resultant of two univariate polynomials of general coeffient types.

`CommutativeRings.resultant_naive`

— Method`resultant_naive(u, v)`

Reference implementation of resultant (determinant of sylvester matrix)

`CommutativeRings.rightfactor`

— Method`rightfactor(u)`

Find greatest integer `g`

such that `g^k`

divides `u[deg(u)-k]`

for all `k = 1:deg(u)`

`CommutativeRings.rnf_matrix`

— Method`rnf_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 `rnf_polynomials`

.

`CommutativeRings.rnf_polynomials`

— Method`rnf_polynomials(rnf::RNF)`

Return the sequence of minimal polynomials `P`

with `P[1]`

multiple of `P[2]`

...

`CommutativeRings.rnf_transformation`

— Method`rnf_transformation(rnf::RNF)`

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

`CommutativeRings.row2degree`

— Method`row2degree(r)`

Return the maximal degree of elements in row number `r`

. This is the fundamantal definition of the shape of the table.

`CommutativeRings.row2index`

— Method`row2index(r)`

For row id `r`

return index of degree `0`

element of that row. Rows are zero-based.

`CommutativeRings.select_k_from_n`

— Method`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.sff`

— Method`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.signed_subresultant_polynomials`

— Method`signed_subresultant_polynomials(P::T, Q::T) where {S,T<:UnivariatePolynomial{S}}`

This code is taken from "Algorithm 8.76 (Signed Subresultant Polynomials)" "Algorithms in Real Algebraic Geometry" by Basu, Pollak, Roy - 2016. Its use is restricted to the case of `S`

is an integral domain (there is no non-trivial divisor of zero).

`CommutativeRings.sintern`

— Method`sintern(a)`

Return a symbol, which uniquly identifies the argument.

`CommutativeRings.sized`

— Method`sized(a::Vector, r)`

Return a vector of length `r`

, which starts with `a`

and is filled up with zeros if required.

`CommutativeRings.smallfactors`

— Method`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.splitmod`

— Method`v = splitmod(a, m)`

Assume `gcd(a, m) != 1`

. Find `v`

in a way that `gcd(v, m/v) == 1`

.

`CommutativeRings.stripzeros!`

— Method`stripzeros!(q)`

count and remove trailing zero coefficients.

`CommutativeRings.swapcols`

— Method`swapcols(A, pc, i, j)`

Swap columns `A[:,i]`

with `A[:,j]`

and `pc[i]`

with `pc[j]`

`CommutativeRings.swaprows`

— Method`swaprows(A, pr, i, j, cols)`

Swap rows `A[i,cols]`

with `A[j,cols]`

and `pr[i]`

with `pr[j]`

`CommutativeRings.testrules`

— Method`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.uptype`

— Method`uptype(a, [T::Type])`

promote `a`

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

.

`CommutativeRings.value`

— Method`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.varname`

— Method`varname(P)`

Return variable name of univariate polynomial or polynomial type `P`

as a symbol.

`CommutativeRings.varnames`

— Method`varnames(P)`

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

.

`CommutativeRings.yun`

— Method`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`

.

`CommutativeRings.zassenhaus_irr`

— Method`zassenhaus_irr(u)`

Returns true iff the squarefree polynomial `u`

is irreducible.

`LinearAlgebra.sylvester`

— Method`sylvester(u::P, v::P) where P<:UnivariatePolynomial`

Return sylvester matrix of polynomials `u`

and `v`

.

`Primes.factor`

— Method`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.factor`

— Method`factor(u::UnivariatePolynomial, a::Integer)`

factorize `u(x^a)`

. `u`

squarefree and `content(u) == 1`