`CommutativeRings.Conway.conway`

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

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

Return a list of conway polynomials for `GF(p^m)`

, length clipped to `nr.

`CommutativeRings.Conway.has_conway_property1`

— Method`has_conway_property1(poly)`

Check if `poly`

is monomial.

`CommutativeRings.Conway.has_conway_property2`

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

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

— Method`isconway(::Type{GaloisField})`

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

`CommutativeRings.Conway.quasi_conway`

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

— Method`B(n), B(n, x)`

Bernoulli-number and Bernoulli-polynomial

`CommutativeRings.SpecialPowerSeries.E`

— Method`E(n), E(n, x)`

Euler-number and Euler-polynomial

`CommutativeRings.SpecialPowerSeries.Ein`

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

— Method`Li(z, n)`

Return value of "polylogarithmic" function `Li`

of order `n`

.

`CommutativeRings.SpecialPowerSeries._stirling2`

— Method`stirling2(n, k)`

Stirling numbers of the second kind. See also `stirling2r`

.

`CommutativeRings.SpecialPowerSeries.lin1p`

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

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

`CommutativeRings.SpecialPowerSeries.podhammer`

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

.

`CommutativeRings.SpecialPowerSeries.power1p`

— Method`power1p(z, p) = (1 + z)^p`

`CommutativeRings.SpecialPowerSeries.sqrt1p`

— Method`sqrt1p(z) = sqrt(1 + z)`

`CommutativeRings.SpecialPowerSeries.stirling1`

— Method`stirling1(n, k)`

Stirling numbers of the first kind. See also `stirling1r`

.

`CommutativeRings.SpecialPowerSeries.stirling1r`

— Method`stirling1r(n, k)`

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

`CommutativeRings.SpecialPowerSeries.stirling2r`

— Method`stirling2r(n, k)`

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

.

`CommutativeRings.SpecialPowerSeries.ver`

— Method`ver(z) = 1 - cos(z)`

Return the versine of `z`

`CommutativeRings.MINPRIME`

— Constant`MINPRIME constant for first prime to try irreducibility`

`CommutativeRings.RingInt`

— Type`RingInt`

Union of system `Integer`

types and any `Ring`

subtype.

`CommutativeRings.FSeries`

— Type`FSeries{T,F}`

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

`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`CommutativeRings.Hom`

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

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

.

`CommutativeRings.Ideal`

— Type`Ideal{R}`

Respresent in Ideal of Ring `R`

. Only Ideals with a finite (Groebner) basis.

`CommutativeRings.IterTerms`

— Type`IterTerms(p::Polynomial)`

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

.

`CommutativeRings.MultivariatePolynomial`

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

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

`CommutativeRings.PowerSeries`

— TypePower 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.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.RNF`

— Type`RNF(polynomials, transformation)`

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

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

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

— Type`VectorSpace{R,V}`

Represent a vector space over a Vfield `R`

.

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

— Type`WNF(polynomials, transformation)`

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

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

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

— Method`reverse(p::UnivariatePolynomial)`

Revert the order of coefficients. If `n = deg(p)`

and `k`

`maximal with`

x^k`divides`

p`, then`

reverse(p) == x^(n + k) * p(1 // x)`. The degree of`

p` is not changed.

`Base.sqrt`

— Method`sqrt(z::GaloisField)`

Calculate a `x`

in the same field with `x ^ 2 == z`

.

Throw `DomainError`

if no solution exists. With `x`

alway `-x`

is a solution. With characteristic 2, every `z`

has a square root`.

`Base.sqrt`

— Method`sqrt(s::PowerSeries)`

For power series `s`

with constant term `1`

calculate the powerseries `p`

with `p^2 == s`

and constant term `1`

.

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

— Method`CC(p::UnivariatePolynomial)`

Return the constant coefficient of polynomial.

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

— Function`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.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(r::Ring)`

Return the leading coefficient of `r`

. For non-polynomials return `r`

itself.

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

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

— Method`absprecision(s::PowerSeries)`

Return absolute precision of a power series element.

Essentially: `ord(s) + precision(s)`

`CommutativeRings.adjugate`

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

— Method`allpf(n::Integer)`

Return ordered vector of prime factors of `n`

.

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

— Method`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_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.butterfly2!`

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

.

`CommutativeRings.carmichael`

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

— Method`coeffs(p::UnivariatePolynomial)`

Return vector of length `deg(p)+1`

with all coefficients of polynomial. First vector element is constant term of polynomial.

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

Return a complementary space of vector space.

`CommutativeRings.compose_inv`

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

— Method`compress(p, n)`

Return polynomial `q`

with `q(x^n) == p(x)`

.

Assuming `p`

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

.

`CommutativeRings.content`

— Method`CommutativeRings.content_primpart`

— Method`content_primpart(p::UnivariatePolynomial{<:QQ})`

Return content and primpart of a polynomial.

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

— Method`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) == 0`and`

mod(z - y, q) == 0`. The result type is widened to avoid overflows.

`CommutativeRings.cyclotomic`

— Method`cyclotomic(P, n)`

Calculate `n`

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

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

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

— Methoddiscriminant(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.divremv`

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

— Method`exponents(u::UnivariatePolynomial)`

Return the list of exponents with non-zero coefficient.

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

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

factorize polynomial `u(x^a)`

over `ZZ`

.

`CommutativeRings.factors`

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

th 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.fft2`

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

th 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.fibonacci`

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

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

Return the generator element of this implementation of Galois field.

`CommutativeRings.generator`

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

Return the first primitive element of given iterable ring.

`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::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_form`

— Method`CommutativeRings.homomorphism`

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

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

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

For nonzero integers `a`

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

`CommutativeRings.ilog3`

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

For nonzero integers `a > 0`

return Int(floor(log(abs(a)) / log(3))) 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.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.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::R)`

Return iff `p`

is neither `0`

nor a unit nor a product of non-units of `R`

.

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

of polynomial `p`

is one.

`CommutativeRings.ismonom`

— Method`ismonom(p::Polynomial)`

Return iff polynomial `p`

is identical to its leading term ond not `0`

.

`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::R)`

Return iff `p`

is neither `0`

nor a unit nor irreducible in `R`

.

`CommutativeRings.iszerodiv`

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

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

`CommutativeRings.jacobi`

— Method`jacobi(k, n)`

Calculate Jacobi symbol of `k`

over `n`

. `0 < n && isodd(n)`

, `jacobi(k, n) ∈ {-1, 0, 1}`

.

`CommutativeRings.joinpoly`

— Method`joinpoly(p::Polynomial{<:Polynomial}, var)`

Convert polynomial of polynomials to multivariate polynomial with variables `var`

.

`CommutativeRings.killmemo!`

— Method`killmemo!(mf::Function)`

Empty memory of memoized function `mf`

.

`CommutativeRings.kronecker`

— Method`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.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(p::Polynomial)`

Returns leading coefficient `lco`

if that is a unit, otherwise `lcunit(lco)`

.

`CommutativeRings.lcunit`

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

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

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

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

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

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

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

— Function`mfactor(p::UnivariatePolynomial)`

Like `factor`

. Memoize all intermediate results.

Memory is reset using `killmemo!(mfactor)`

.

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

— Method`moebius(n)`

Calculate Moebius function of `n`

.

`CommutativeRings.monom`

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

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

)

`CommutativeRings.monom`

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

Return monic monomial of degree `n`

.

`CommutativeRings.mult_by_monom`

— Method`mult_by_monom(p, k)`

Return a new polynomial with the same coefficient vector, and `ord`

increased by `k`

.

`CommutativeRings.mult_by_monom`

— Method`mult_by_monom(p, k)`

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

.

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

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_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 has maximal rank.

`CommutativeRings.normgcd`

— Methodg, 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.ofindex`

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

— Method`ord(p::UnivariatePolynomial)`

Return the multiplicity of `0`

as a root of `p`

. For `p == 0`

return `0`

.

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

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

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

— Methodpgcd(a, b)

Pseudo gcd of univariate polynomials `a`

and `b`

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

`CommutativeRings.pgcdx`

— Methodg, 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.polynomials`

— Method`polynomials(rnf::RNF)`

Return the sequence of minimal polynomials `P`

with `P[1]`

multiple of `P[2]`

...

`CommutativeRings.polynomials`

— Method`polynomials(rnf::WNF)`

Return the sequence of pairs of irreducible polynomials and powers.

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

— Methodpresultant_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.primefactors`

— Method`primefactors(n::Integer)`

Return an iterator over the prime factors of `n`

, sorted.

`CommutativeRings.primpart`

— Method`primpart(p::Polynomial)`

The primitive part of the polynomial `p`

, equals `p / content(p)`

. If the basetype is `QQ`

, returned polynomial has basetype `ZZ`

.

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

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

— Method`pushmemo!(f::Function, v)`

Push `v`

to memory of memoized function.

`CommutativeRings.randlattice`

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

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

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

d.

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

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

— Methodresultant(a, b)

Calculate resultant of two univariate polynomials of general coeffient types.

`CommutativeRings.resultant_naive`

— Methodresultant_naive(u, v)

Reference implementation of resultant (determinant of sylvester matrix)

`CommutativeRings.revert`

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

— Method`revert(a::Int, b::Int)`

Return `a`

with bits `0:n-1`

in reverse order.

`CommutativeRings.revert`

— Method`revert(a::Int, v::Vector)`

Represent `a`

in a digit system given by `v`

, revert positions and return "reverse" of `a`

.

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

— MethodMultiply 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_strassen`

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

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

— Method`shiftleft(vector, integer)`

Increase size of vector by `s`

, copy content and fill lower indices with zeros.

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

— Methodsigned*subresultant*polynomials(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.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.smith_normal_form`

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

`CommutativeRings.splitmod`

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

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

— 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.sylvester_matrix`

— Methodsylvester_matrix(u::P, v::P) where P<:UnivariatePolynomial

Return sylvester matrix of polynomials `u`

and `v`

.

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

— Method`transformation(rnf::RNF)`

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

`CommutativeRings.transformation`

— Method`transformation(rnf::SNF)`

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

`CommutativeRings.transformation`

— Method`transformation(rnf::WNF)`

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

`CommutativeRings.uncompress`

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

— Method`weierstrass_normal_form([rnf,] matrix)`

Calculate Weierstrass normal form of a matrix over a field.

If `rnf`

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

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

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

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

.