Package cc.redberry.rings.poly

Class MultipleFieldExtension<Term extends AMonomial<Term>,mPoly extends AMultivariatePolynomial<Term,mPoly>,sPoly extends IUnivariatePolynomial<sPoly>>

java.lang.Object

cc.redberry.rings.ImageRing<sPoly,mPoly>

cc.redberry.rings.poly.MultipleFieldExtension<Term,mPoly,sPoly>

All Implemented Interfaces:

IParser<mPoly>, Stringifiable<mPoly>, IPolynomialRing<mPoly>, Ring<mPoly>, Serializable, Iterable<mPoly>, Comparator<mPoly>

public class MultipleFieldExtension<Term extends AMonomial<Term>,mPoly extends AMultivariatePolynomial<Term,mPoly>,sPoly extends IUnivariatePolynomial<sPoly>>
extends ImageRing<sPoly,mPoly>
implements IPolynomialRing<mPoly>

Multiple field extension F(α_1, α_2, ..., α_N). Elements are represented as multivariate polynomials over (α_1, α_2, ..., α_N); internally all arithmetic operations are performed by switching to appropriate simple field extension F(γ) (accessible via getSimpleExtension() method) where γ is some primitive element (accessible via getPrimitiveElement() method) computed automatically. Representation of generating algebraic elements α_i as elements of this simple extension can be obtained via getGeneratorRep(int) method. Originally, generators are represented by their minimal polynomials over F(α_1, α_2, ..., α_i) ("tower" representation). To construct multiple field extensions one should use {@link #mkMultipleExtension(...)} and joinAlgebraicElement(UnivariatePolynomial).

Since:

2.5

See Also:

mkMultipleExtension(IUnivariatePolynomial), mkMultipleExtension(IUnivariatePolynomial...), mkSplittingField(IUnivariatePolynomial), Rings.MultipleFieldExtension(IUnivariatePolynomial[]), Rings.SplittingField(IUnivariatePolynomial), Serialized Form

Field Summary

Fields inherited from class cc.redberry.rings.ImageRing

imageFunc, inverseFunc, ring

Constructor Summary

Constructors

Constructor	Description
MultipleFieldExtension(MultipleFieldExtension<Term,mPoly,sPoly>[] tower, UnivariatePolynomial<mPoly>[] minimalPolynomialsOfGenerators, mPoly primitiveElement, sPoly[] generatorsReps, SimpleFieldExtension<sPoly> simpleExtension)

Method Summary

Modifier and Type	Method	Description
mPoly	copy(mPoly element)	Makes a deep copy of the specified element (for immutable instances the same reference returned).
int	degree()	Returns the degree of this filed extension (that is the degree of primitive element)
boolean	equals(Object o)
mPoly[]	extendedGCD(mPoly a, mPoly b)	Returns array of [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b)
mPoly	factorial(long num)	Gives a product of valueOf(1) * valueOf(2) * .... * valueOf(num)
mPoly	factory()	Factory polynomial
mPoly	gcd(Iterable<mPoly> elements)	Returns greatest common divisor of specified elements
mPoly	gcd(mPoly... elements)	Returns greatest common divisor of specified elements
mPoly	gcd(mPoly a, mPoly b)	Returns the greatest common divisor of two elements
UnivariatePolynomial<mPoly>	getGeneratorMinimalPoly(int iGenerator)	Returns minimal polynomial corresponding to i-th generator.
sPoly	getGeneratorRep(int iGenerator)	Returns representation of i-th generator as element of simple field extension generated by primitive element getPrimitiveElement()
sPoly[]	getGeneratorReps()	Returns representation of generators as elements of simple field extension generated by primitive element getPrimitiveElement()
mPoly	getOne()	Returns unit element of this ring (one)
mPoly	getPrimitiveElement()	Returns the primitive element of this multiple field extension
SimpleFieldExtension<sPoly>	getSimpleExtension()	Returns the isomorphic simple field extension generated by getPrimitiveElement()
MultipleFieldExtension<Term,mPoly,sPoly>	getSubExtension(int i)	Returns the i-th extension from the tower
sPoly	getUnivariateFactory()
mPoly	getZero()	Returns zero element of this ring
int	hashCode()
boolean	isOne(mPoly element)	Tests whether specified element is one (exactly)
boolean	isUnit(mPoly element)	Tests whether specified element is a ring unit
boolean	isZero(mPoly element)	Tests whether specified element is zero
MultipleFieldExtension<Term,mPoly,sPoly>	joinAlgebraicElement(UnivariatePolynomial<mPoly> algebraicElement)	Adds algebraic element given by its minimal polynomial (not checked that it is irreducible) to this.
MultipleFieldExtension<Term,mPoly,sPoly>	joinAlgebraicElement(sPoly minimalPoly)	Adds algebraic element given by its minimal polynomial (not checked that it is irreducible) to this.
MultipleFieldExtension<Term,mPoly,sPoly>	joinRedundantElement(mPoly element)	Adds algebraic element given by its minimal polynomial (not checked that it is irreducible) to this.
mPoly	lcm(mPoly a, mPoly b)	Returns the least common multiple of two elements
static <Term extends AMonomial<Term>,mPoly extends AMultivariatePolynomial<Term,mPoly>,sPoly extends IUnivariatePolynomial<sPoly>> MultipleFieldExtension<Term,mPoly,sPoly>	mkMultipleExtension(SimpleFieldExtension<sPoly> ext)
static <Term extends AMonomial<Term>,mPoly extends AMultivariatePolynomial<Term,mPoly>,sPoly extends IUnivariatePolynomial<sPoly>> MultipleFieldExtension<Term,mPoly,sPoly>	mkMultipleExtension(sPoly a)
static <Term extends AMonomial<Term>,mPoly extends AMultivariatePolynomial<Term,mPoly>,sPoly extends IUnivariatePolynomial<sPoly>> MultipleFieldExtension<Term,mPoly,sPoly>	mkMultipleExtension(sPoly... minimalPolynomials)	Creates multiple field extension F(α_1, α_2, ..., α_i) where α_i are specified by their minimal polynomials over F.
static <Term extends AMonomial<Term>,mPoly extends AMultivariatePolynomial<Term,mPoly>,sPoly extends IUnivariatePolynomial<sPoly>> MultipleFieldExtension<Term,mPoly,sPoly>	mkSplittingField(sPoly poly)	Constructs splitting field for a given polynomial.
int	nVariables()	Number of polynomial variables
int	signum(mPoly element)	Returns -1 if element < 0, 0 if element == 0 and 1 if element > 0, where comparison is specified by Comparator.compare(Object, Object)
String	toString()
String	toString(IStringifier stringifier)	convert this to string with the use of stringifier
String	toString(String... variables)
mPoly	valueOf(long val)	Returns ring element associated with specified long
mPoly	valueOfBigInteger(BigInteger val)	Returns ring element associated with specified integer
mPoly	variable(int variable)	Creates poly representing a single specified variable

Methods inherited from class cc.redberry.rings.ImageRing

abs, add, add, cardinality, characteristic, compare, decrement, divideAndRemainder, factor, factorSquareFree, image, image, increment, inverse, inverse, isEuclideanRing, isField, isPerfectPower, iterator, multiply, multiply, negate, parse, perfectPowerBase, perfectPowerExponent, pow, pow, pow, quotient, randomElement, reciprocal, remainder, subtract, valueOf

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Comparator

compare, reversed, thenComparing, thenComparing, thenComparing, thenComparingDouble, thenComparingInt, thenComparingLong

Methods inherited from interface cc.redberry.rings.poly.IPolynomialRing

mkCoder, parse

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Methods inherited from interface cc.redberry.rings.Ring

abs, add, add, addMutable, cardinality, characteristic, createArray, createArray, createArray, createArray, createArray2d, createArray2d, createZeroesArray, createZeroesArray2d, decrement, divideAndRemainder, divideExact, divideExactMutable, divideOrNull, factor, factorSquareFree, fillZeros, firstBezoutCoefficient, getNegativeOne, increment, isEuclideanRing, isField, isFinite, isFiniteField, isMinusOne, isPerfectPower, isUnitOrZero, iterator, lcm, lcm, max, min, multiply, multiply, multiply, multiply, multiplyMutable, negate, negateMutable, parse, perfectPowerBase, perfectPowerExponent, pow, pow, pow, quotient, randomElement, randomElement, randomElementTree, randomElementTree, randomNonZeroElement, reciprocal, remainder, setToValueOf, subtract, subtractMutable, valueOf, valueOf

Constructor Detail

MultipleFieldExtension

public MultipleFieldExtension(MultipleFieldExtension<Term,mPoly,sPoly>[] tower,
                              UnivariatePolynomial<mPoly>[] minimalPolynomialsOfGenerators,
                              mPoly primitiveElement,
                              sPoly[] generatorsReps,
                              SimpleFieldExtension<sPoly> simpleExtension)

Method Detail

nVariables

public int nVariables()

Description copied from interface: IPolynomialRing

Number of polynomial variables

Specified by:

nVariables in interface IPolynomialRing<Term extends AMonomial<Term>>

factory

public mPoly factory()

Description copied from interface: IPolynomialRing

Factory polynomial

Specified by:

factory in interface IPolynomialRing<Term extends AMonomial<Term>>

variable

public mPoly variable(int variable)

Description copied from interface: IPolynomialRing

Creates poly representing a single specified variable

Specified by:

variable in interface IPolynomialRing<Term extends AMonomial<Term>>

getUnivariateFactory

public sPoly getUnivariateFactory()

getPrimitiveElement

public mPoly getPrimitiveElement()

Returns the primitive element of this multiple field extension

degree

public int degree()

Returns the degree of this filed extension (that is the degree of primitive element)

getSimpleExtension

public SimpleFieldExtension<sPoly> getSimpleExtension()

Returns the isomorphic simple field extension generated by getPrimitiveElement()

getGeneratorMinimalPoly

public UnivariatePolynomial<mPoly> getGeneratorMinimalPoly(int iGenerator)

Returns minimal polynomial corresponding to i-th generator.

getSubExtension

public MultipleFieldExtension<Term,mPoly,sPoly> getSubExtension(int i)

Returns the i-th extension from the tower

getGeneratorRep

public sPoly getGeneratorRep(int iGenerator)

Returns representation of i-th generator as element of simple field extension generated by primitive element getPrimitiveElement()

getGeneratorReps

public sPoly[] getGeneratorReps()

Returns representation of generators as elements of simple field extension generated by primitive element getPrimitiveElement()

joinAlgebraicElement

public MultipleFieldExtension<Term,mPoly,sPoly> joinAlgebraicElement(UnivariatePolynomial<mPoly> algebraicElement)

Adds algebraic element given by its minimal polynomial (not checked that it is irreducible) to this.

joinAlgebraicElement

public MultipleFieldExtension<Term,mPoly,sPoly> joinAlgebraicElement(sPoly minimalPoly)

Adds algebraic element given by its minimal polynomial (not checked that it is irreducible) to this.

joinRedundantElement

public MultipleFieldExtension<Term,mPoly,sPoly> joinRedundantElement(mPoly element)

Adds algebraic element given by its minimal polynomial (not checked that it is irreducible) to this.

valueOf

public mPoly valueOf(long val)

Description copied from interface: Ring

Returns ring element associated with specified long

Specified by:

valueOf in interface Ring<Term extends AMonomial<Term>>

Overrides:

valueOf in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

Parameters:

val - machine integer

Returns:

ring element associated with specified long

valueOfBigInteger

public mPoly valueOfBigInteger(BigInteger val)

Description copied from interface: Ring

Returns ring element associated with specified integer

Specified by:

valueOfBigInteger in interface Ring<Term extends AMonomial<Term>>

Overrides:

valueOfBigInteger in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

Parameters:

val - integer

Returns:

ring element associated with specified integer

getZero

public mPoly getZero()

Description copied from interface: Ring

Returns zero element of this ring

Specified by:

getZero in interface Ring<Term extends AMonomial<Term>>

Overrides:

getZero in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

Returns:

0

getOne

public mPoly getOne()

Description copied from interface: Ring

Returns unit element of this ring (one)

Specified by:

getOne in interface Ring<Term extends AMonomial<Term>>

Overrides:

getOne in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

Returns:

1

copy

public mPoly copy(mPoly element)

Description copied from interface: Ring

Makes a deep copy of the specified element (for immutable instances the same reference returned).

Specified by:

copy in interface Ring<Term extends AMonomial<Term>>

Overrides:

copy in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

Parameters:

element - the element

Returns:

deep copy of specified element

isZero

public boolean isZero(mPoly element)

Description copied from interface: Ring

Tests whether specified element is zero

Specified by:

isZero in interface Ring<Term extends AMonomial<Term>>

Overrides:

isZero in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

Parameters:

element - the ring element

Returns:

whether specified element is zero

isOne

public boolean isOne(mPoly element)

Description copied from interface: Ring

Tests whether specified element is one (exactly)

Specified by:

isOne in interface Ring<Term extends AMonomial<Term>>

Overrides:

isOne in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

Parameters:

element - the ring element

Returns:

whether specified element is exactly one

See Also:

Ring.isUnit(Object)

isUnit

public boolean isUnit(mPoly element)

Description copied from interface: Ring

Tests whether specified element is a ring unit

Specified by:

isUnit in interface Ring<Term extends AMonomial<Term>>

Overrides:

isUnit in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

Parameters:

element - the ring element

Returns:

whether specified element is a ring unit

See Also:

Ring.isOne(Object)

gcd

public mPoly gcd(mPoly a,
                 mPoly b)

Description copied from interface: Ring

Returns the greatest common divisor of two elements

Specified by:

gcd in interface Ring<Term extends AMonomial<Term>>

Overrides:

gcd in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

Parameters:

a - the first element

b - the second element

Returns:

gcd

extendedGCD

public mPoly[] extendedGCD(mPoly a,
                           mPoly b)

Description copied from interface: Ring

Returns array of [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b)

Specified by:

extendedGCD in interface Ring<Term extends AMonomial<Term>>

Overrides:

extendedGCD in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

lcm

public mPoly lcm(mPoly a,
                 mPoly b)

Description copied from interface: Ring

Returns the least common multiple of two elements

Specified by:

lcm in interface Ring<Term extends AMonomial<Term>>

Overrides:

lcm in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

Parameters:

a - the first element

b - the second element

Returns:

lcm

gcd

public mPoly gcd(mPoly... elements)

Description copied from interface: Ring

Returns greatest common divisor of specified elements

Specified by:

gcd in interface Ring<Term extends AMonomial<Term>>

Overrides:

gcd in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

Parameters:

elements - the elements

Returns:

gcd

gcd

public mPoly gcd(Iterable<mPoly> elements)

Description copied from interface: Ring

Returns greatest common divisor of specified elements

Specified by:

gcd in interface Ring<Term extends AMonomial<Term>>

Overrides:

gcd in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

Parameters:

elements - the elements

Returns:

gcd

signum

public int signum(mPoly element)

Description copied from interface: Ring

Returns -1 if element < 0, 0 if element == 0 and 1 if element > 0, where comparison is specified by Comparator.compare(Object, Object)

Specified by:

signum in interface IPolynomialRing<Term extends AMonomial<Term>>

Specified by:

signum in interface Ring<Term extends AMonomial<Term>>

Overrides:

signum in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

Parameters:

element - the element

Returns:

-1 if element < 0, 0 if element == 0 and 1 otherwise

factorial

public mPoly factorial(long num)

Description copied from interface: Ring

Gives a product of valueOf(1) * valueOf(2) * .... * valueOf(num)

Specified by:

factorial in interface Ring<Term extends AMonomial<Term>>

Overrides:

factorial in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

Parameters:

num - the number

Returns:

valueOf(1) * valueOf(2) * .... * valueOf(num)

equals

public boolean equals(Object o)

Specified by:

equals in interface Comparator<Term extends AMonomial<Term>>

Overrides:

equals in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

hashCode

public int hashCode()

Overrides:

hashCode in class ImageRing<sPoly extends IUnivariatePolynomial<sPoly>,mPoly extends AMultivariatePolynomial<Term,mPoly>>

toString

public String toString(IStringifier stringifier)

Description copied from interface: Stringifiable

convert this to string with the use of stringifier

Specified by:

toString in interface Stringifiable<Term extends AMonomial<Term>>

toString

public String toString(String... variables)

toString

public String toString()

Overrides:

toString in class Object

mkMultipleExtension

public static <Term extends AMonomial<Term>,mPoly extends AMultivariatePolynomial<Term,mPoly>,sPoly extends IUnivariatePolynomial<sPoly>> MultipleFieldExtension<Term,mPoly,sPoly> mkMultipleExtension(sPoly a)

mkMultipleExtension

public static <Term extends AMonomial<Term>,mPoly extends AMultivariatePolynomial<Term,mPoly>,sPoly extends IUnivariatePolynomial<sPoly>> MultipleFieldExtension<Term,mPoly,sPoly> mkMultipleExtension(SimpleFieldExtension<sPoly> ext)

mkMultipleExtension

public static <Term extends AMonomial<Term>,mPoly extends AMultivariatePolynomial<Term,mPoly>,sPoly extends IUnivariatePolynomial<sPoly>> MultipleFieldExtension<Term,mPoly,sPoly> mkMultipleExtension(sPoly... minimalPolynomials)

Creates multiple field extension F(α_1, α_2, ..., α_i) where α_i are specified by their minimal polynomials over F.

NOTE: it is not tested that specified minimal polynomials are irreducible

Parameters:

minimalPolynomials - minimal polynomials of algebraic elements

mkSplittingField

public static <Term extends AMonomial<Term>,mPoly extends AMultivariatePolynomial<Term,mPoly>,sPoly extends IUnivariatePolynomial<sPoly>> MultipleFieldExtension<Term,mPoly,sPoly> mkSplittingField(sPoly poly)

Constructs splitting field for a given polynomial.