$ rings.repl
Loading...
Rings 2.5.5: efficient Java/Scala library for polynomial rings

@ implicit val ring = MultivariateRing(Z, Array("x", "y", "z"))
ring: MultivariateRing[IntZ] = MultivariateRing(Z, Array("x", "y", "z"), LEX)

@ val poly1 = ring("x + y - z").pow(8) 
poly1: MultivariatePolynomial[IntZ] = z^8-8*y*z^7+28*y^2*z^6-56*y^3*z^5+70*...

@ val poly2 = ring("x - y + z").pow(8) 
poly1: MultivariatePolynomial[IntZ] = z^8-8*y*z^7+28*y^2*z^6-56*y^3*z^5+70*...

@ Factor(poly1 - poly2)
res13: FactorDecomposition[MultivariatePolynomial[IntZ]] = 
       16*(x)*((-1)*z+y)
       *(z^4-4*y*z^3+6*y^2*z^2-4*y^3*z+y^4+6*x^2*z^2-12*x^2*y*z+6*x^2*y^2+x^4)
       *(z^2-2*y*z+y^2+x^2)

libraryDependencies += "cc.redberry" %% "rings.scaladsl" % "2.5.5"

<dependency>
    <groupId>cc.redberry</groupId>
    <artifactId>rings</artifactId>
    <version>2.5.5</version>
</dependency>

@
import cc.redberry.rings
import cc.redberry.rings.primes.{SmallPrimes, BigPrimes}
import rings.{bigint, primes, linear, poly}
import poly.{univar, multivar}
import poly.PolynomialMethods._
import multivar.MonomialOrder._
import multivar.GroebnerMethods
import rings.scaladsl._
import util._
import syntax._

@ implicit val ring = MultivariateRing(Z, Array("x", "y", "z"))
ring: MultivariateRing[IntZ] = MultivariateRing(Z, Array("x", "y", "z"), LEX)

@ val poly1 = ring("x + y - z").pow(8) 
poly1: MultivariatePolynomial[IntZ] = z^8-8*y*z^7+28*y^2*z^6-56*y^3*z^5+70*...

@ val poly2 = ring("x - y + z").pow(8) 
poly1: MultivariatePolynomial[IntZ] = z^8-8*y*z^7+28*y^2*z^6-56*y^3*z^5+70*...

@ Factor(poly1 - poly2)
res13: FactorDecomposition[MultivariatePolynomial[IntZ]] = 
       16*(x)*((-1)*z+y)
       *(z^4-4*y*z^3+6*y^2*z^2-4*y^3*z+y^4+6*x^2*z^2-12*x^2*y*z+6*x^2*y^2+x^4)
       *(z^2-2*y*z+y^2+x^2)

import cc.redberry.rings

import rings.poly.PolynomialMethods._
import rings.scaladsl._
import syntax._

// Ring Z[x]
UnivariateRing(Z, "x")
// Ring Z[x, y, z]
MultivariateRing(Z, Array("x", "y", "z"))
// Ring Q[a, b, c]
MultivariateRing(Q, Array("a", "b", "c"))

// Ring Z/3[x]
UnivariateRingZp64(3, "x")
// Ring Z/3[x, y, z]
MultivariateRingZp64(3, Array("x", "y", "z"))
// Ring Z/p[x, y, z] with p = 2^107 - 1 (Mersenne prime)
MultivariateRing(Zp(Z(2).pow(107) - 1), Array("x", "y", "z"))

// Galois field with cardinality 7^10 
// (irreducible polynomial will be generated automatically)
GF(7, 10, "x")
// GF(7^3) generated by irreducible polynomial "1 + 3*z + z^2 + z^3"
GF(UnivariateRingZp64(7, "z")("1 + 3*z + z^2 + z^3"), "z")

// Field of fractions of univariate polynomials Z[x]
Frac(UnivariateRing(Z, "x"))
// Field of fractions of multivariate polynomials Z/19[x, y, z]
Frac(MultivariateRingZp64(19, Array("x", "y", "z")))

// Galois field GF(17, 9) with irreducible 
// poly in Z/17[t] generated automaticaly
implicit val ring = GF(17, 9, "t")

// pick some random field element
val a = ring.randomElement()
// raise field element to the power of 1000
val b = a.pow(1000)
// reciprocal of field element
val c = 1 / b

assert ( b * c === 1)

// explicitly parse field element from string:
// input poly will be automatically converted to
// element of GF(17, 9) (reduced modulo field generator)
val d = ring("1 + t + t^2 + t^3 + 15 * t^999")
// do some arbitrary math ops in the field
val some = a / (b + c) + a.pow(6) - a * b * c * d

// polynomial ring Z/17[x]
implicit val ring = UnivariateRingZp64(17, "x")
// parse ring element
val x = ring("x")

// construct some polynomials
val poly1 = 1 + x + x.pow(2) + x.pow(3)
val poly2 = 1 + 2 * x + 9 * x.pow(2)

// compute (gcd, s, t) such that s * poly1 + t * poly2 = gcd
val Array(gcd, s, t) = PolynomialExtendedGCD(poly1, poly2)
assert (s * poly1 + t * poly2 == gcd)

println((gcd, s, t))

// polynomial ring Z/17[x]
implicit val ring = UnivariateRingZp64(17, "x")x

// parse polynomial from string
val poly = ring("4 + 8*x + 12*x^2 + 5*x^5 - x^6 + 10*x^7 + x^8")

// factorize poly
val factors = Factor(poly)

println(factors)

// coefficient ring Z/1237940039285380274899124357 (the next prime to 2^100)
val modulus = Z("1267650600228229401496703205653")
val cfRing  = Zp(modulus)

// ring Z/1237940039285380274899124357[x]
implicit val ring = UnivariateRing(cfRing, "x")
val poly = ring("4 + 8*x + 12*x^2 + 5*x^5 + 16*x^6 + 27*x^7 + 18*x^8")

// factorize poly
println(Factor(poly))

// elements of coefficient field GF(7,3) are represented as polynomials
// over "z" modulo irreducible polynomial "1 + 3*z + z^2 + z^3"
val cfRing = GF(UnivariateRingZp64(7, "z")("1 + 3*z + z^2 + z^3"), "z")

assert(cfRing.characteristic().intValue() == 7)
assert(cfRing.cardinality().intValue() == 343)

// polynomial ring GF(7^3)[x]
implicit val ring = UnivariateRing(cfRing, "x")

// parse poly in GF(7^3)[x] from string
// coefficients of polynomials in GF(7,3)[x] are elements
// of GF(7,3) that is polynomials over "z"
val poly = ring("1 - (1 - z^3) * x^6 + (1 - 2*z) * x^33 + x^66")

// factorize poly
val factors = Factor(poly)
println(s"${ring show factors}")

// ring Z[x, y, z]
implicit val ring = MultivariateRing(Z, Array("x", "y", "z")) 
// parse some ring elements
val (x, y, z) = ring("x", "y", "z") 

// construct some polynomials using different math ops
val a = (x + y + z).pow(2) - 1 
val b = (x - y - z - 1).pow(2) + x + y + z - 1 
val c = (a + b + 1).pow(9) - a - b - 1

// reduce c modulo a and b (multivariate division with remainder)
val (div1, div2, rem) = c /%/% (a, b)

// ring Z[a, b, c]
implicit val ring = MultivariateRing(Z, Array("a", "b", "c"))

// parse polynomials from strings
val poly1 = ring("-b-b*c-b^2+a+a*c+a^2")
val poly2 = ring("b^2+b^2*c+b^3+a*b^2+a^2+a^2*c+a^2*b+a^3")

// compute multivariate GCD
val gcd   = PolynomialGCD(poly1, poly2)
assert (poly1 % gcd === 0)
assert (poly2 % gcd === 0)
println(gcd)

// ring Z/2[x, y, z]
implicit val ring = MultivariateRingZp64(2, Array("x", "y", "z"))
val (x, y, z) = ring("x", "y", "z")

// factorize poly
val factors = Factor(1 + (1 + x + y + z).pow(2) + (x + y + z).pow(4))
println(factors)

// ring Z[a, b, c]
implicit val ring = MultivariateRing(Z, Array("a", "b", "c"))
val (a, b, c) = ring("a", "b", "c")

// factorize poly
val factors = Factor(1 - (1 + a + b + c).pow(2) - (2 + a + b + c).pow(3))
println(ring show factors)

// ring Q[x, y, z]
implicit val ring = MultivariateRing(Q, Array("x", "y", "z"))

// parse some poly from string
val poly = ring(
  """
    |(1/6)*y*z + (1/6)*y^3*z^2 - (1/2)*y^6*z^5 - (1/2)*y^8*z^6
    |-(1/3)*x*z - (1/3)*x*y^2*z^2 + x*y^5*z^5 + x*y^7*z^6
    |+(1/9)*x^2*y^2*z - (1/3)*x^2*y^7*z^5 - (2/9)*x^3*y*z
    |+(2/3)*x^3*y^6*z^5 - (1/2)*x^6*y - (1/2)*x^6*y^3*z
    |+x^7 + x^7*y^2*z - (1/3)*x^8*y^2 + (2/3)*x^9*y
  """.stripMargin)

// factorize poly
val factors = Factor(poly)
println(factors)

// elements of GF(7,3) are represented as polynomials
// over "z" modulo irreducible polynomial "1 + 3*z + z^2 + z^3"
val cfRing = GF(UnivariateRingZp64(7, "z")("1 + 3*z + z^2 + z^3"), "z")
// ring GF(7,3)[a,b,c]
implicit val ring = MultivariateRing(cfRing, Array("a", "b", "c"))

// parse poly in GF(7^3)[a,b,c] from string
// coefficients of polynomials in GF(7,3)[a,b,c] are elements
// of GF(7,3) that is polynomials over "z"
val poly = ring("1 - (1 - z^3) * a^6*b + (1 - 2*z) * c^33 + a^66")

//factorize poly
println(Factor(poly))

// Frac(Z[x,y,z])
implicit val field = Frac(MultivariateRing(Z, Array("x", "y", "z")))

// parse some math expression from string
// it will be automatically reduced to a common denominator
// with the gcd being automatically cancelled
val expr1 = field("(x/y/(x - z) + (x + z)/(y - z))^2 - 1")

// do some math ops programmatically
val (x, y, z) = field("x", "y", "z")
val expr2 = expr1.pow(2) + x / y - z

// bind expr1 and expr2 to variables to use them further in parser
field.coder.bind("expr1", expr1)
field.coder.bind("expr2", expr2)

// parse some complicated expression from string
// it will be automatically reduced to a common denominator
// with the gcd being automatically cancelled
val expr3 = field(
  """
     expr1 / expr2 - (x*y - z)/(x-y)/expr1
     + x / expr2 - (x*z - y)/(x-y)/expr1/expr2
     + x^2*y^2 - z^3 * (x - y)^2
  """)

// export expression to string
println(field.stringify(expr3))

// take numerator and denominator
val num = expr3.numerator()
val den = expr3.denominator()
// common GCD is always cancelled automatically
assert( field.ring.gcd(num, den).isOne )

// compute unique factor decomposition of expression
val factors = field.factor(expr3)
println(field.stringify(factors))

// ring Z/17[x,y,z]
implicit val ring = MultivariateRingZp64(17, Array("x", "y", "z"))
val (x, y, z) = ring("x", "y", "z")

// create ideal with two generators using GREVLEX monomial order for underlying Groebner basis
val I = Ideal(ring, Seq(x.pow(2) + y.pow(12) - z, x.pow(2) * z + y.pow(2) - 1), GREVLEX)
// I is proper ideal
assert(I.isProper)

// get computed Groebner basis
val gb = I.groebnerBasis
println(gb)

// check some ideal properties
assert(I.dimension == 1)
assert(I.degree == 36)

// create another ideal with only one generator
val J = Ideal(ring, Seq(x.pow(4) * y.pow(4) + 1), GREVLEX)
// J is principal ideal
assert(J.isPrincipal)

val union = I union J
// union is zero dimensional ideal
assert(union.dimension == 0)

val intersection = I intersection J
// intersection is still 2-dimensional
assert(intersection.dimension == 2)

// yet another ideal
val K = Ideal(ring, Seq(z * x.pow(4) - z * y.pow(14) + y * z.pow(16), (x + y + z).pow(4)), GREVLEX)
// compute complicated quotient ideal
val quotient = (I * J * K) :/ times
assert(quotient == K) 

// ring Q[a, b, c]
implicit val ring = MultivariateRing(Q, Array("x", "y", "z"))

// parse some polynomials from strings
val a = ring("8*x^2*y^2 + 5*x*y^3 + 3*x^3*z + x^2*y*z")
val b = ring("x^5 + 2*y^3*z^2 + 13*y^2*z^3 + 5*y*z^4")
val c = ring("8*x^3 + 12*y^3 + x*z^2 + 3")
val d = ring("7*x^2*y^4 + 18*x*y^3*z^2 + y^3*z^3")

// construct ideal with Groebner basis in LEX order
val ideal = Ideal(ring, Seq(a, b, c, d), LEX)
// it is very simple: <z^2, x, 1+4*y^3>
println(ideal)

/**
  * Solves equation \sum f_i s_i  = gcd(f_1, \dots, f_N) for given f_i and unknown s_i
  * @return a tuple (gcd, solution)
  */
def solveDiophantine[E](fi: Seq[E])(implicit ring: Ring[E]) =
  fi.foldLeft((ring(0), Seq.empty[E])) { case ((gcd, seq), f) =>
    val xgcd = ring.extendedGCD(gcd, f)
    (xgcd(0), seq.map(_ * xgcd(1)) :+ xgcd(2))
  }

/** Computes partial fraction decomposition of given rational */
def apart[E](frac: Rational[E]) = {
  implicit val ring: Ring[E] = frac.ring
  val factors = ring.factor(frac.denominator).map {case (f, exp) => f.pow(exp)}
  val (gcd,  nums) = solveDiophantine(factors.map(frac.denominator / _))
  val (ints, rats) = (nums zip factors)
    .map { case (num, den) => Rational(frac.numerator * num, den * gcd) }
    .flatMap(_.normal)       // extract integral parts from fractions
    .partition(_.isIntegral) // separate integrals and fractions
  rats :+ ints.foldLeft(Rational(ring(0)))(_ + _)
}

// partial fraction decomposition for rationals
// gives List(184/479, (-10)/13, 1/8, (-10)/47, 1)
val qFracs = apart( Q("1234213 / 2341352"))

// partial fraction decomposition for rational functions
val ufRing = Frac(UnivariateRingZp64(17, "x"))
// gives List(4/(16+x), 1/(10+x), 15/(1+x), (14*x)/(15+7*x+x^2))
val pFracs = apart( ufRing("1 / (3 - 3*x^2 - x^3 + x^5)") )

/** Lagrange polynomial interpolation formula */
def interpolate[Poly <: IUnivariatePolynomial[Poly], Coef]
    (points: Seq[(Coef, Coef)])
    (implicit ring: IUnivariateRing[Poly, Coef]) = {
      // implicit coefficient ring (setups algebraic operators on type Coef)
      implicit val cfRing: Ring[Coef] = ring.cfRing
      if (!cfRing.isField) throw new IllegalArgumentException
      points.indices
        .foldLeft(ring(0)) { case (sum, i) =>
          sum + points.indices
            .filter(_ != i)
            .foldLeft(ring(points(i)._2)) { case (product, j) =>
              product * (ring.`x` - points(j)._1) / (points(i)._1 - points(j)._1)
            }
        }
    }

// coefficient ring Frac(Z/13[a,b,c])
val cfRing = Frac(MultivariateRingZp64(2, Array("a", "b", "c")))
val (a, b, c) = cfRing("a", "b", "c")

implicit val ring = UnivariateRing(cfRing, "x")
// interpolate with Lagrange formula
val data = Seq(a -> b, b -> c, c -> a)
val poly = interpolate(data)
assert(data.forall { case (p, v) => poly.eval(p) == v })