Skip to content

Only monic polynomials allowed when trying to factor multivariate polynomial #74

@flipchart

Description

@flipchart

Trying to factor a multivariate polynomial in GF2[x1,x2,x3,x4]/[x1+x1^2,...] but getting the error "Only monic polynomials allowed"

I'm using the poly (x1 + x2 + x3)*(x2 + x4)*(x1 + x4) as an example, but I can't load it like that because it keeps the exponents (higher than 1) and solves it fine. In my application all my polys have exponents no greater than 1 (hence the quotient ring). So I load x1*x2*x3 + x1*x3*x4 + x2*x3*x4 + x3*x4 which is the poly mod the ideal

Repro:

val cfRing = GF(UnivariateRingZp64(2, "z")("z + z^2"), "z")
implicit val ring = MultivariateRing(cfRing, Array("x1", "x2", "x3", "x4"))
val poly = ring("x1*x2*x3 + x1*x3*x4 + x2*x3*x4 + x3*x4")
println(Factor(poly))

Stack trace:

java.lang.IllegalArgumentException: Only monic polynomials allowed. Input: x^2+(1+x)*x^3
  cc.redberry.rings.poly.univar.UnivariateDivision.fastDivisionPreConditioning(UnivariateDivision.java:836)
  cc.redberry.rings.poly.univar.IrreduciblePolynomials.finiteFieldIrreducibleBenOr(IrreduciblePolynomials.java:144)
  cc.redberry.rings.poly.univar.IrreduciblePolynomials.finiteFieldIrreducibleQ(IrreduciblePolynomials.java:45)
  cc.redberry.rings.poly.univar.IrreduciblePolynomials.irreducibleQ(IrreduciblePolynomials.java:33)
  cc.redberry.rings.poly.univar.IrreduciblePolynomials.randomIrreduciblePolynomial(IrreduciblePolynomials.java:186)
  cc.redberry.rings.poly.multivar.MultivariateFactorization.factorInExtensionField(MultivariateFactorization.java:340)
  cc.redberry.rings.poly.multivar.MultivariateFactorization.factorInExtensionFieldGeneric(MultivariateFactorization.java:1382)
  cc.redberry.rings.poly.multivar.MultivariateFactorization.factorPrimitiveInGF0(MultivariateFactorization.java:1725)
  cc.redberry.rings.poly.multivar.MultivariateFactorization.factorPrimitiveInGF0(MultivariateFactorization.java:1658)
  cc.redberry.rings.poly.multivar.MultivariateFactorization.factorPrimitiveInGF(MultivariateFactorization.java:1506)
  cc.redberry.rings.poly.multivar.MultivariateFactorization.factorPrimitiveInGF(MultivariateFactorization.java:1484)
  cc.redberry.rings.poly.multivar.MultivariateFactorization.Factor(MultivariateFactorization.java:212)
  cc.redberry.rings.poly.multivar.MultivariateFactorization.FactorInGF(MultivariateFactorization.java:184)
  cc.redberry.rings.poly.multivar.MultivariateFactorization.Factor(MultivariateFactorization.java:43)
  cc.redberry.rings.poly.PolynomialMethods.Factor(PolynomialMethods.java:30)
  ammonite.$sess.cmd6$.<init>(cmd6.sc:1)
  ammonite.$sess.cmd6$.<clinit>(cmd6.sc)

Apologies if I got the math terms wrong/mixed up - still learning :)

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions