Rings : an efficient Java/Scala library for polynomial rings
STANISLAV POSLAVSKY, Institute for High Energy Physics NRC ”Kurchatov Institute”, 142281 Protvino,

arXiv:1712.02329v2 [cs.SC] 18 Dec 2017

Russia, email: stvlpos@mail.ru

In this paper we briefly discuss Rings — an efficient lightweight library for univariate and multivariate
polynomial arithmetic over arbitrary coefficient rings. Basic algebra, GCDs and factorization of polynomials
are implemented with the use of modern asymptotically fast algorithms. Rings provides a clean API for algebra
and a fully typed hierarchy of mathematical structures. Scala API additionally brings powerful strongly typed
functional programming model which allows to write short and expressive code for applications. Performance
achieved in Rings is similar to such well known specialized solutions like Singular and considerably better
than in some general-purpose systems like Mathematica .

1

INTRODUCTION

Efficient implementation of polynomial arithmetic is crucial for many applications of modern
computational science. Tools like polynomial GCDs, polynomial factorization, Gröebner bases
became a fundamental component of many academic and applied areas including modern computer algebra, algebraic geometry, algebraic number theory, cryptography etc. Computational
applications of these areas are used more and more often for doing practical calculations in modern
physics. For example, the key ingredient of many computations in high energy physics is the
calculation of multiloop Feynman integrals. The modern developments in this direction are based
on applications of algebraic geometry with the use of Gröebner bases, multivariate residues [1, 2],
Nullstellensatz certificates [3], methods from algebraic number theory [4] etc. There is the same
constantly growing interest to the computational methods of commutative algebra in another
practical fields like cryptography (see e.g. recent developments in homomorphic encryption [5]) or
machine learning [6].
Among the modern open source software there are only few tools, which are able to perform
such fundamental routines as e.g. multivariate polynomial factorization at a speed sufficient for
today’s real world problems. Existing tools with such functionality are commonly implemented
as a computer algebra systems and each has its own interactive interface and domain-specific
programming language as the only means to interact with it (for example Singular [7] is one
of the most comprehensive and performant open-source systems for such type of computations).
Applications which internally use this kind of mathematics has to be dependent on an external largescale system and all the users are forced to have the installation of the system on their machines
which become inconvenient. The above considerations served as a motivation for development of a
new open-source high performance lightweight library (not a full-featured system) for polynomial
arithmetic, written in a high-level programming language with a clean API which meets modern
standards of software development. A good examples of the proof of concept are NTL [8] and FLINT
[9] C/C++ high performance libraries focused on univariate polynomial arithmetic in connection
with number theory which are quite well known and widely used in many research areas. Another
libraries that should be certainly mentioned are GiNaC C++ symbolic library [10] widely used in
high energy physics, SymPy [11] computer algebra library for Python, and JAS [12] library which
was the first successful attempt of implementing commutative algebra in Java.
Rings is a cross platform library written entirely in Java language and thus fully compatible with
any modern JVM-based language (Scala/Closure/Kotlin/Groovy etc.). Scala extension allows for
expressive type-safe interaction with the library from within a custom Scala application as well as

REPL console. Both Java and Scala are strongly and statically typed languages and the mathematical
structures used in Rings also form a fully typed hierarchy in contrast to many computer algebra
systems and libraries that operate either with untyped or weakly typed objects or use duck typing.
This strong typing is manifested e.g. in the fact that polynomials from different rings have different
compile-time component types (example in Scala):
// poly in Z[x]
val polyZ : UnivariatePolynomial[IntZ] = ...
// poly in Q[x] (Q = Frac[Z])
val polyQ : UnivariatePolynomial[Rational[IntZ]] = ...
(in actual Scala code one can omit explicit type annotation in most places having them automatically
inferred at compile time).
In the next section we give an overview of the most important Rings features. Section 3
presents the benchmarks, Section 4 is dedicated to the algorithms and implementation aspects.
All examples in this paper are given in Scala. Examples in Java can be found at Rings website
http://ringsalgebra.io and at http://rings.readthedocs.io. The source code of the library is hosted at
GitHub https://github.com/PoslavskySV/rings.
2

OVERVIEW

In single sentence, Rings allows to construct different rings and perform arithmetic in them,
including both very basic math operations and advanced methods like polynomial factorization or
linear systems solving. Below we’ll illustrate these features by a step-by-step example.
Our starting point is to take some ground ring, for example a finite field GF(17, 3), and perform
some basic math in it:
1
2
3
4
5
6
7
8

// Galois field GF(17, 3)
implicit val gf = GF(17, 3, "t")
// parse ring element from its string representation
val t = gf("t")
// or create element programmatically
val t1 = 1 + t.pow(2)
// do some basic math (+-*/) with elements of gf
val t2 = 3 + t1 - t.pow(22) / (1 + t + t1.pow(999))

It is worth to emphasize that while all explicit type annotations are usually omitted in the code,
Scala compiler will in fact infer them automatically, so the above lines are actually treated as:
implicit val gf : Ring[UnivariatePolynomialZp64]
val t
: UnivariatePolynomialZp64
val t1
: UnivariatePolynomialZp64
val t2
: UnivariatePolynomialZp64

=
=
=
=

...
...
...
...

Here Ring[E] interface is a super type for all rings, so Ring[UnivariatePolynomialZp64] is a
ring of elements of type UnivariatePolynomialZp64. The latter is used for univariate polynomials
over Zp — that is the actual representation of elements of Galois fields (a more elaborate discussion
of rings and polynomials representation is given in Section 4).
In line 4 element is parsed from its string representation. This line is actually a synthetic sugar
for gf.parse("t"). In fact there are several such methods for different conversions which are all
may be called in the same way:
2

// from string
val elem = gf("1 + tˆ2")
// from Int
val unit = gf(1)
// from elements of other GF fields
val elementFromOtherField = GF(19, 5).randomElement()
val cast = gf(elementFromOtherField)
// synthetic sugar for multiple assignment
// val el1 = gf("t + 1"); val el2 = gf("t + 2")
val (el1, el2) = gf("t + 1", "t + 2")
Note that the ring gf in line 2 is defined implicit. This means that Scala compiler will delegate
all math operations on objects of type UnivariatePolynomialZp64 to that implicit ring instance
(with the use of Scala implicit conversions):
t1 - t2 // is equivalent to gf.subtract(t1, t2)
t1 * t2 // is equivalent to gf.multiply(t1, t2)
3 + t1 // is equivalent to gf.add(gf.valueOf(3), t1)
With no implicit keyword specified, math operations will be performed as plain polynomial
operations. For example, (t1 + t2) will be treated as t1.add(t2) instead of gf.add(t1, t2):
obviously, addition of elements in the Galois field is not the same as simple addition of polynomials.
The ground ring GF(17, 3) was chosen only for our illustration purposes. In fact one can use any of
the built-in rings absolutely in the same manner. The built-in rings include Z, Q, Zp , GF(p, k) (with
arbitrary large p), Frac(R), R[x] and R[X® ] where R is an arbitrary ground ring (which may be either
one or any combination of the listed rings). Rings uses a specifically optimized implementations
for some particular rings to achieve the best performance. For example, the ring Zp with p less
than 264 (machine integer) or the same ring with large p have separate implementations. As well
polynomials over Zp with p less than 264 (like UnivariatePolynomialZp64 from our example)
also have separate highly optimized implementations.
Our next step it to define some multivariate polynomial ring over the ground ring GF(17, 3).
Below we define such ring and perform some math operations in the same fashion as we did above:
7
8
9
10
11
12

// multivariate ring GF(17, 3)[x, y, z]
implicit val ring = MultivariateRing(gf, Array("x", "y", "z"), LEX)
val (x, y, z) = ring("x", "y", "z")
// construct multivariate polynomials
val p1 = (t.pow(2) + 1)*x*y.pow(2)*z + (t + 1)*x.pow(5) * z*y.pow(6) + 1
val p2 = p1.pow(2) + (t + 1)*x.pow(2)*y.pow(2) + (t.pow(9) + 1)*z.pow(7)

Again the ring instance is defined implicit, so all math operations with multivariate polynomials
(which have type MultivariatePolynomial[UnivariatePolynomialZp64] in our example) will
be delegated to that instance.
In line 8 we explicitly specified to use LEX monomial order for multivariate polynomials. This
choice affects some algorithms like multivariate division and Gröebner bases. The explicit order
may be omitted (LEX will be used by default). Several mathematical operations are specifically
important in the rings of polynomials:
14 // standard division with remainder
15 val (div, rem) = p2 /% p1
3

16
17
18
19
20
21
22
23

// define a simple ideal (just a tuple of polynomials)
val (i1, i2, i3) = (x + y + z, x - y - z, y.pow(2) - z.pow(2))
// do complete multivariate division with remainder (polynomial reduction)
val (div1, div2, div3, rem1) = p2 /%/% (i1, i2, i3)
assert ( p2 == div1 * i1 + div2 * i2 + div3 * i3 + rem1 )
// or just reduce poly modulo ideal
val p3 = p2 %% (i1, i2, i3)
assert ( p3 == rem1 )

(a full list of operators defined in Scala (like those /%, /%/%, %% used above) can be found in the
online manual).
Simple division with remainder is supported for all Euclidean rings. This and other properties of
rings may be checked by means of the following methods:
ring.isEuclideanRing
ring.isField
ring.isFinite
ring.cardinality
ring.characteristic

//
//
//
//
//

whether ring is Euclidean ring
whether ring is a field
whether ring is finite
ring cardinality (BigInteger)
ring characteristic (BigInteger)

Polynomial greatest common divisors and polynomial factorization work for polynomials over
all available built-in rings. Continue our example:
24
25
26
27
28
29
30
31
32
33
34

// GCD of polynomials from GF(17, 3)[x, y, z]
val gcd1 = PolynomialGCD(p1 * p3, p2 * p3)
assert ( gcd1 % p3 === 0 )
val gcd2 = PolynomialGCD(p1 * p3, p2 * p3 + 1)
assert ( gcd2.isConstant )
// a really huge polynomial from GF(17, 3)[x, y, z]
// with more than 4 × 103 terms and total degree of 145
val hugePoly = p1 * p2.pow(2) * p3.pow(3)
// factorize it
val factors = Factor(hugePoly)

This is one of the key features of Rings library: it does polynomial GCD and factorization of really
huge polynomials over different ground rings robustly and fast. The performance achieved in Rings
is one of the best among the existing software (see Section 3).
To illustrate how the performance of e.g. polynomial GCD is manifested in applications, suppose
we need to solve a system of linear equations with symbolic coefficients — a task which arise
frequently in many applications (whether it is the calculation of Gröbner bases, or the reduction of
loop integrals in high energy physics). In the continuation of our example we use GF(17, 3)[x, y, z]
for the ring of coefficients, so the solution belongs to the field of rational functions over 3 variables
with coefficients from GF(17, 3). This can be accomplished in Rings easily:
35
36
37
38

// field of rational functions Frac(GF(17, 3)[x, y, z])
implicit val ratRing = Frac(ring)
// convert x, y, z and t to elements of Frac(GF(17, 3)[x, y, z])
// that is rationals with unit denominators
4

39
40
41
42
43
44
45
46
47
48
49
50

val (rx, ry, rz, rt) = ratRing(x, y, z, ring(t))
// lhs matrix
val lhs =
Array(
Array(rt + rx + rz, ry * rz, rz - rx * ry),
Array(rx - ry - rt, rx / ry, rz + rx / ry),
Array(rx * ry / rt, rx + ry, rz / rx + ry)
)
// rhs column
val rhs = Array(rx, ry, rz)
// solve the system with Gaussian elimination
val solution = LinearSolver.solve[ratRing.ElementType](ratRing, lhs, rhs)

The standard Gaussian elimination uses O(n 3 ) field operations, which means O(n3 ) multivariate
polynomial GCDs (since each fraction should be reduced). So, the variation of polynomial GCD
speed in two times lead in nearly an order of magnitude variation of time needed to solve the
system.
Line 40 is a synthetic sugar which converts elements of ring (multivariate polynomials) to
elements of ratRing (rational functions), that is:
val rx = Rational(x, 1) // x is numerator and 1 is denominator
val ry = Rational(y, 1) // y is numerator and 1 is denominator
...
The type that will be inferred for variables rx, ry, rz and rt is:
Rational[MultivariatePolynomial[UnivariatePolynomialZp64]]
The last thing we will focus on is that Rings is a library which allows to write short and
expressive code on top of it. Consider the following two-liner example which implements a solver
for Diophantine equations — that is a straightforward generalization of extended GCD on more
than two arguments (algorithm from Sec. 4.5 in [13]):
51 /**
Í
52 * Solves equation
fi si = дcd(f 1 , . . . , f N ) for given fi and unknown si
53 * @return a tuple (gcd, solution)
54 */
55 def solveDiophantine[E](fi: Seq[E])(implicit ring: Ring[E]) =
56
fi.foldLeft((ring(0), Seq.empty[E])) { case ((gcd, seq), f) =>
57
val xgcd = ring.extendedGCD(gcd, f)
58
(xgcd(0), seq.map(_ * xgcd(1)) :+ xgcd(2))
59
}
With this function, it is very easy to implement, for example, efficient algorithm for partial fraction
decomposition with just a few lines of code:
60 /** Computes partial fraction decomposition of given rational */
61 def apart[E](frac: Rational[E]) = {
62
implicit val ring: Ring[E] = frac.ring
63
val facs = ring.factor(frac.denominator).map {case (f, exp) => f.pow(exp)}
5

64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

}

val (gcd, nums) = solveDiophantine(facs(frac.denominator / _))
val (ints, rats) = (nums zip facs)
.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)") )

We defined function apart[E] as a generic function which can be applied to elements of arbitrary
rings (that should be Euclidean rings of course). Returning to our initial example where we’ve
constructed a field GF(17, 3)[x, y, z], let’s adjoin a new variable, sayW , and construct partial fraction
decomposition in this complicated field:
80
81
82
83
84

// partial fraction decomposition of rational functions
// in the ring Frac(GF(17, 3)[x, y, z])[W ]
implicit val uRing = UnivariateRing(ratRing, "W")
val W = uRing("W")
val fracs = apart(Rational(W + 1, (rx/ry + W.pow(2)) * (rz/rx + W.pow(3))))

Function call on the last line involves nearly all main components of Rings library: from very basic
algebra to multivariate factorization over sophisticated rings.
The above example shows how powerful features of Rings in a combination with expressive and
type-safe Scala syntax may be used to implement quite a non-trivial and generic functionality with
little efforts.
3

BENCHMARKS

The speed of Rings was tested on three important problems: multivariate polynomial GCD, multivariate polynomial factorization and univariate polynomial factorization. The internal implementation of corresponding algorithms uses nearly all components of the library, so it is a good indicator
of the overall performance.
All benchmarks presented below were executed on MacBook Pro (15-inch, 2017), 3,1 GHz Intel
Core i7, 16 GB 2133 MHz LPDDR3. The source code of benchmarks is available at Rings GitHub
page.
3.1

Multivariate GCD and factorization

Two corner cases are important for nearly all algorithms with multivariate polynomials: very
dense problems and very sparse problems. In fact, the most part of problems that arise naturally in
practice are sparse, especially those which arise in physics. On the other hand, dense problems
6

can arise too, e.g. a very sparse polynomial (x 10y 10z 10 + 1) becomes very dense under a simple
substitution x → x + 1, y → y + 1, z → z + 1.
Another important fact is that many multivariate algorithms are quite sensitive to the properties
of the ground ring. For example, the algorithms for GCD or factorization in Z[X® ], Zp [X® ] with
medium p (32-bit) and Zp [X® ] with very small p (e.g. p = 2) are quite different.
Finally, both GCD and factorization may have two results: trivial result (GCD of coprime or
factorization of irreducible polynomial) and non-trivial result. In most practical applications
(especially in physics or calculus) the first case is much more often than the second. So, it is a very
important property of the algorithm to detect the trivial answer as early as possible.
In the below benchmarks we addressed the above considerations and performed separate tests
for sparse and dense inputs over different ground rings with both non-trivial and trivial answers.
Speed was compared with Singular (v4.1.0) and Mathematica 1 (v11.1.1.0)
3.1.1 Multivariate GCD. To test the performance of GCD on sparse polynomials we proceed
as follows. Polynomials a, b and д with 40 terms and degree 30 in each variable were generated at
random. Then the GCDs дcd(aд, bд) (non-trivial, should result in multiple of д) and дcd(aд + 1, bд)
(trivial, coprime) were calculated. The input polynomials had at average about ∼ 103 terms and
degree 60 in each variable (so the total degree of each input was 60n, where n is the number of
variables). Tests were performed for polynomials in 3, 4, 5 and 6 variables over Z and Z2 ground
rings.
The results are summarized in Table 1. All tools have detected trivial answers for дcd(aд + 1, bд)
very fast in all cases (within few milliseconds), so these results are not shown in the table. Figure 1
shows the typical distribution of execution times for non-trivial GCD problems in Z[x 1 , . . . , x 6 ]
(Rings vs Mathematica , left plot) and Z2 [x 1 , . . . , x 4 ] (Rings vs Singular , right plot).
Results can be summarised as follows: Mathematica is several orders of magnitude slower than
Rings over Z2 ground ring and comparably fast over Z, Singular is several orders of magnitude
slower over both Z and Z2 .
# variables
3
3
4
4
5
5
6
6

Ground ring
Rings
Z
0.5s ± 0.1s
Z2
0.4s ± 0.1s
Z
1.1s ± 0.4s
Z2
2.6s ± 0.8s
Z
1.9s ± 0.7s
Z2
2.1s ± 0.6s
Z
1.8s ± 1.0s
Z2
3.0s ± 1.4s

Singular / Rings
9.9 ± 3.2
2.7 ± 0.6
56 ± 53
14.8 ± 5.4
201 ± 137
242 ± 67
> 103
> 103

Mathematica / Rings
1.3 ± 0.4
> 103
2.1 ± 0.8
> 103
2.5 ± 1.2
> 103
4.5 ± 2.6
> 103

Table 1. Polynomial greatest common divisor performance on sparse random polynomials (with non-trivial
GCD). For the running time of Rings and for the ratios the median values and median absolute deviations
(errors) are presented.

To test the performance of GCD on dense problems, we used the following polynomials:
a = (1 + 3x 1 + 5x 2 + 7x 3 + 9x 4 + 11x 5 + 13x 6 + 15x 7 )7 − 1

1a

(1)

b = (1 − 3x 1 − 5x 2 − 7x 3 + 9x 4 − 11x 5 − 13x 6 + 15x 7 ) + 1

(2)

д = (1 + 3x 1 + 5x 2 + 7x 3 + 9x 4 + 11x 5 + 13x 6 − 15x 7 )7 + 3

(3)

7

single Mathematica Home Desktop license was at our disposal

7

���
��������� ��

������������ ��

�� ���
����
����
����
����
�
�

���

GCD in Z[x1 ,x2 ,x3 ,x4 ,x5 ,x6 ]
����

����

����

����

���

GCD in Z2 [x1 ,x2 ,x3 ,x4 ]
���

�� ���

������ ��

���

���

������ ��

Fig. 1. The typical distributions of execution times for polynomial greatest common divisor on sparse random
polynomials in Z[x 1 , . . . , x 6 ] (left, Rings vs Mathematica ) and Z2 [x 1 , . . . , x 4 ] (right, Rings vs Singular ).

and computed дcd(aд, bд) and дcd(aд, bд + 1) over Z and Z524287 ground rings. The results are
shown in Table 2. It is seen, that all tools have comparable performance on such dense problems.
Ground ring
Problem
Rings
Z
дcd(aд, bд)
128s
Z
дcd(aд, bд + 1) 0.4s
Z524287
дcd(aд, bд)
21s
Z524287
дcd(aд, bд + 1) 0.4s

Singular
142s
0.2s
46s
0.3s

Mathematica
116s
4s
34s
2s

Table 2. Time to compute дcd(aд, bд) and дcd(aд, bд + 1) for dense polynomials given in (1), (2), (3).

3.1.2 Multivariate factorization. To test the performance of multivariate factorization on
sparse polynomials we proceed as follows. Three polynomials a, b and c with 20 terms and degree
15 in each variable were generated at random. Then the factorizations of (abc) (non-trivial, should
give at least three factors) and (abc + 1) (trivial, irreducible) were calculated. The input polynomials
had at average 8 × 103 terms and degree 45 in each variable (so the total degree of input was 45n,
where n is the number of variables). Tests were performed for polynomials in 3, 4, 5, 6 and 7
variables over Z, Z2 , and Z524287 ground rings.
Table 3 summarizes the results for polynomials over 6 and 7 variables (for less number of
variables summary is similar, though timings are of course smaller). Mathematica does not
support factorization in finite fields. For tests over Z it failed to solve any of the input problems
in less than 103 seconds (our timeout value), so it is not shown here. Figure 1 shows the typical
distributions of execution times for factorization problems.
Results can be summarised as follows: both Rings and Singular has comparable performance,
though Rings is distinctly faster for problems with trivial factorization patterns, while Mathematica is just unsuitable for even quite medium-sized problems of polynomial factorization.
To test the performance of factorization on dense problems, we tested factorization of the
following polynomials:
p1 = (1 + 3x 1 + 5x 2 + 7x 3 + 9x 4 + 11x 5 + 13x 6 + 15x 7 )15 − 1
p2 = −1 + (1 + 3x 1x 2 + 5x 2x 3 + 7x 3x 4 + 9x 4x 5 + 11x 5x 6 + 13x 6x 7 + 15x 7x 1 )3
×(1 + 3x 1x 3 + 5x 2x 4 + 7x 3x 5 + 9x 6x 5 + 11x 7x 6 + 13x 6x 1 + 15x 7x 2 )3
×(1 + 3x 1x 4 + 5x 2x 5 + 7x 3x 6 + 9x 6x 7 + 11x 7x 1 + 13x 6x 2 + 15x 7x 3 )3
8

(4)

(5)

# variables
6
6
6
6
6
6
7
7
7
7
7
7

Problem
Ground ring
f actor (abc)
Z
f actor (abc)
Z2
f actor (abc)
Z524287
f actor (abc + 1)
Z
f actor (abc + 1)
Z2
f actor (abc + 1)
Z524287
f actor (abc)
Z
f actor (abc)
Z2
f actor (abc)
Z524287
f actor (abc + 1)
Z
f actor (abc + 1)
Z2
f actor (abc + 1)
Z524287

Rings time
12.7s ± 4.6s
2.5s ± 0.8s
1.8s ± 0.2s
0.3s ± 0.0s
0.5s ± 0.2s
0.4s ± 0.0s
41.7s ± 28.s
5.9s ± 1.7s
5.8s ± 2.2s
0.9s ± 0.1s
1.1s ± 0.3s
0.9s ± 0.1s

Singular / Rings
0.4 ± 0.2
0.8 ± 0.6
1.7 ± 0.7
4.5 ± 0.5
1.4 ± 0.6
3.8 ± 1.0
0.3 ± 0.3
1.4 ± 1.1
1.6 ± 1.4
5.6 ± 0.8
3.8 ± 2.7
4.7 ± 0.6

Table 3. Polynomial factorization performance on sparse random polynomials. For the running time of Rings
and for the ratios the median values and median absolute deviations (errors) are presented.

���

��������� ��

��������� ��

���

���

���

��� �
��

Factorization in Z[x1 ...x7 ]
���

���

���
���
���
��� �
��

���

Factorization in Z[x1 ...x7 ]
���

���

���

���

���

���
���
��� �
��

Factorization in Z2 [x1 ...x7 ]
���

���

���

���

���

������ ��

��������� ��

��������� ��

������ ��

���

���
���
��� �
��

���

������ ��

Factorization in Z2 [x1 ...x7 ]
���

���

���

���

������ ��

Fig. 2. The typical distributions of execution times for polynomial factorization on sparse random polynomials
(Rings vs Singular ). Upper left plot is for f actor (abc) (non-trivial) in Z[x 1 , . . . , x 7 ], upper right — for
f actor (abc + 1) (trivial) in Z[x 1 , . . . , x 7 ], bottom left — f actor (abc) (non-trivial) in Z2 [x 1 , . . . , x 7 ], bottom right
— for f actor (abc + 1) (trivial) in Z2 [x 1 , . . . , x 7 ].

It is worth to admit that the first polynomial has unit leading coefficient with respect to any of
its variables, while the second has not (these two corner cases are very differently treated by
9

many known factorization algorithms). The results are listed in Table 4. It is seen, that Rings and
Singular has comparable performance2 .
Ground ring
Z
Z2
Z524287
Z
Z2
Z524287

Problem Rings
f actor (p1 )
55s
f actor (p1 ) 0.25s
f actor (p1 )
28s
f actor (p2 )
23s
f actor (p2 )
6s
f actor (p2 )
26s

Singular
20s
¿ 1h
109s
12s
3s
9s

Mathematica
271s
N/A
N/A
206s
N/A
N/A

Table 4. Time to compute factorization of dense polynomials given in (4) and (5).

3.2

Univariate factorization in finite fields

Efficient univariate polynomial arithmetic is very important for applications in number theory and
cryptography, not to mention the fact that most multivariate algorithms use univariate in the basis.
Univariate factorization in finite fields actually covers almost all low-level aspects of univariate
arithmetic, so it is a quite good indicator of its overall performance.
To test the univariate factorization performance we used the following polynomials:
pdeg [x] = 1 +

iÕ
≤deg

i × xi

(6)

i=1

and measured time to factor over Z17 and Z231 −1 . The speed was compared to NTL (v10.4.0) and
FLINT (v2.5.2). Results are shown in Figure 3. It is clearly seen, that while Rings has better
performance than Mathematica , it has worse asymptotic at large degrees than NTL and FLINT.
Rings uses the same algorithms for univariate polynomial factorization as NTL and FLINT (see
next Section), so the difference is due to the more advanced algorithms used by NTL/FLINT for
univariate polynomial arithmetic.
���

���
���

���

����� ��

����� ��

���

���

���

�����

��

�����
�����������

�

���

���

���

�����

��

�����
�����������

�

������������� �� ��� [�]

��-�
�

���

����

����

����

������������� �� ����������� [�]
����

�

������

���

����

����

����

����

������

Fig. 3. Univariate factorization performance on polynomials (6) over Z17 (left) and Z231 −1 (right).

2 except

one case when Singular failed to obtain result in less than an hour, probably due some bug; we have sent the bug
report to the developers

10

4

IMPLEMENTATION NOTES

Rings is separated into several main components. They include:
• rings.bigint: arbitrary precision arithmetic
• rings.primes: prime numbers, prime factorization and primality testing
• rings.poly.univar: univariate polynomials and related algorithms
• rings.poly.multvar: multivariate polynomials and related algorithms
• rings.scaladsl: type classes and syntax definitions for Scala API
In the subsequent sections we briefly discuss each component, but before it is worth to make some
notes about the general design of the library.
4.1

General design

Rings is written in object oriented paradigm with a deep use of abstraction, inheritance and
generic programming. On top of Java API the Scala API brings powerful strongly typed functional
programming model which allows to write short and expressive code for applications.
The central top level interface Ring[E] defines ring operations on elements of type E (addition,
multiplication etc.) and ring properties (cardinality, characteristic etc.). All built-in rings in the
library are a subtypes of Ring[E], e.g. IPolynomialRing[Poly, Coef] is a subtype which is a
super type for all polynomial rings. The second central interface is IPolynomial[Poly], which
is a top level interface for all polynomial types (Rings uses several different implementations
of polynomials discussed in the below subsections). The following example illustrates generic
programming with abstract mathematical types in Rings with the use of functional programming
in Scala:
Í
x −x
/** Lagrange univariate polynomial interpolation: p(x) = i p(x i )Π j,i x i −x jj */
def interpolate[Poly <: IUnivariatePolynomial[Poly], Coef]
(points: Seq[Coef], values: Seq[Coef])
(implicit ring: IUnivariateRing[Poly, Coef]) : Poly = {
// 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(values(i)) ) { case (product, j) =>
product * (ring.`x` - points(j)) / (points(i) - points(j))
}
}
}

Function interpolate from the above example is a generic function which applies to a sequence
of interpolation points and polynomial values at these points. Note, that all types of objects
(which are omitted in code) are inferred at compile time. This powerful feature allows to use two
distinct implicit rings in the function body: ring which defines algebraic operations on type Poly
(polynomial algebra) and cfRing which defines algebraic operations on type Coef (coefficients
algebra). Function interpolate(points, values) can be applied in any ring of univariate
polynomials:
11

// coefficient field Frac( Z2 [a, b, c] )
val cfRing = Frac(MultivariateRingZp64(2, Array("a", "b", "c")))
val (a, b, c) = cfRing("a", "b", "c")
// univariate ring Frac( Z2 [a, b, c] )[x]
implicit val ring = UnivariateRing(cfRing, "x")
// interpolate with Lagrange formula
val data = Seq(a -> b, b -> c, c -> a)
val poly = interpolate(data.map(_._1), data.map(_._2))
assert(data.forall { case (p, v) => poly.eval(p) == v })
In this example, the compile-time type of poly (which is again omitted for shortness) will be
automatically inferred as UnivariatePolynomial[Rational[MultivariatePolynomialZp64]].
4.2

Arithmetic with integers

Java has out of the box support for arbitrary precision arithmetic with integer and floating point
numbers via BigInteger and BigDecimal classes. Historically, Java’s built-in implementation
was much less performant than, for example, the well known GNU Multiple Precision Arithmetic
Library (GMP) [14] which became de-facto a standard in the multiprecision software. This difference
was really noticeable in the real-world computing applications. The situation got much better
with the release of Java 8 which contained Karatsuba and Toom-Cook [15] methods for integer
multiplication. Rings uses a further improved implementation of BigInteger3 with the support of
Schnhage-Strassen [15] multiplication and Barrett [16] division for very large integers. With these
improvements, performance of arbitrary precision arithmetic has ceased to be a bottleneck and
now has a little impact on a high-level methods like polynomial GCD or factorization (although it
is still not so performant as in GMP).
Another important implementation aspect concerns arithmetic in the ring Zp with p < 264 , that
is integer arithmetic modulo some machine number. Though it may be hidden from the user’s eye,
arithmetic in this ring actually lies in the basis of the most part of fundamental algorithms and
directly affects performance of nearly all computations. On the CPU level the modulo operation is
implemented via DIV instruction (integer division) which is known to be very slow: for example on
the recent Intel Skylake architecture DIV has 20-80 times worse throughput than MUL instruction
[17]. Hopefully, arithmetic operations in Zp are done modulo a fixed modulus p which allows
to make some preconditioning on p and reduce DIV operations to MUL. The idea is the following
[16]: given a fixed p we compute once the value of maдic = [2n /p] with a sufficiently large
n (so that maдic is some non-zero machine number), and then for arbitrary integer a we have
[a/p] = (a × maдic)/2n , so DIV instruction is replaced with one MUL and one SHIFT (division by a
power of two is just a bitwise shift, very fast). The actual implementation in fact requires some
more work to do (for details see Chapter 10 in [18]). The implementation used in Rings gained
3-fold increase in speed for modular arithmetics arithmetic in comparison to the implementation
via native CPU instructions4 .
4.3

Prime numbers

Problems with prime numbers (primality test, integer factorization, generating primes etc.) are a
key computational problems of modern number theory and cryptography. Though Rings doesn’t
3a

fork of https://github.com/tbuktu/bigint
https://github.com/PoslavskySV/libdivide4j which is a Java port of well known C/C++ libdivide library (https:
//libdivide.com)
4 see

12

Fig. 4. Inheritance tree of polynomial types.

address these problems rigorously, it contains methods that are required for efficient implementation
of some high-level algorithms with polynomials. These methods include:
• SmallPrimes – factorization and primality test for integers less than 232 . It uses MillerRabin [19, 20] probabilistic primality test in such a way that result is always guaranteed5
and trial divisions for integer factorization (which is very fast for such small inputs).
• BigPrimes – factorization and primality test for arbitrary large integers. It switches
between Pollard-ρ [21], Pollard-P1 [22] and Quadratic Sieve [23, 24] algorithms for prime
factorization and uses Miller-Rabin probabilistic and Lucas [24] strong primality tests.
• SieveOfAtkin and PrimesIterator — simple implementation of sieve of Atkin [25] and
methods for primes generation.
4.4

Univariate polynomials

Univariate polynomials are implemented as a dense arrays of coefficients. There are two distinct
implementations (see Fig. 4): polynomials over generic ground rings (UnivariatePolynomial[E])
and polynomials over Zp with p < 264 (UnivariatePolynomialZp64). The latter one uses primitive long integers to store coefficient data, that’s why it is implemented separately: to avoid a
considerable cost of Java’s boxing and unboxing.
Multiplication of polynomials — the most used and time consuming primitive operation — is
handled via Karatsuba method, which reduces the cost of single multiplication from O(n2 ) to
O(nlog2 3 ). The counterpart of multiplication – polynomial division with remainder — switches
between classical division and division via Newton’s iteration (see Sec. 9 in [13]). The Newton’s
iteration is essentially similar to the trick Rings uses for fast arithmetic in Zp : it allows to reduce
the division to multiplication by a some precomputed “inverse” polynomial followed by some trivial
coefficients rearrangement. This techniques becomes especially useful when several divisions
5 code

is adapted from Apache Commons Math library http://commons.apache.org/proper/commons-math/

13

by a fixed polynomial required (case arising in many algorithms): one can compute the inverse
only once and use it in all further divisions. This is also used in the implementation of Galois
fields GF(p, q) which are represented as univariate polynomials over Zp reduced modulo some
irreducible polynomial r (x) with deg(r ) = q (that is Zp [x]/hr (x)i). Fast division is easily accessible
via high-level interface:
// some univariate polynomials
val divider = ... ; val dividend = ...
// quotient and remainder using classical division methods
val (divPlain, remPlain) = dividend /% divider
// precomputed Newton's inverses
implicit val inverse = divider.precomputedInverses
// quotient and remainder using Newton's iteration (fast)
val (divFast, remFast) = dividend /%% divider
assert((divPlain, remPlain) == (divFast, remFast))
Univariate GCD is implemented with the use of several different methods. For polynomials
over finite fields it switches between classical Euclid algorithm (for small polynomials) and a fast
Half-GCD algorithm (for medium and large polynomials, see Sec. 11 in [13]). For polynomials over
Z and Q the small primes version of Brown’s modular GCD algorithm [26] is used. In all other
cases, the subresultant GCD algorithm is used.
Univariate polynomial factorization is implemented with the use of Cantor-Zassenhaus approach.
Factorization over finite fields is done either via plain Cantor-Zassenhaus algorithm [27] (for
medium sized polynomials) or Shoup’s baby-step giant-step algorithm [28] (for large polynomials or
for finite fields of large characteristic). Factorization of polynomials over Z is done first by factoring
modulo some 32-bit prime followed by a true factor reconstruction via Hensel lifting. Reconstruction
of true factors from the modular ones is actually dominates in the timing of factorization over Z.
Rings uses a mixed variant of linear and quadratic Hensel lifting (see Sec. 6 in [29]) in order to lift
modular factors up to sufficiently large modulus. The true factors are then finally reconstructed
by a brute-force enumeration of all possible factor combinations (“naive” recombination). This
techniques is quite fast for practical applications: e.g. on randomized inputs the most time is spent
in actual Hensel lifting, while final recombination takes much less time. Nevertheless, the bad case
has exponential complexity. It takes place on a special class of polynomials — Swinnerton-Dyer
polynomials [30] — which have nontrivial factorization over Zp (for any p) but irreducible over Z.
On these inputs the algorithm degrades to enumeration of all possible modular factor combinations
which are O(2r ) (r is a number of modular factors). The drawback is fixed by van Hoeij’s algorithm
[31] which uses LLL lattice reduction [32] to reconstruct true factors in O(r 3 ), but this algorithm is
not implemented in Rings yet.
4.5

Multivariate polynomials

Rings uses a sparse distributed representation of multivariate polynomials. The underlying data
structure is a red-black map of degree vectors to monomials: Java’s built-in TreeMap[DegreeVector,
Monomial] is used. As in the case of univariate polynomials, there are two distinct implementations (see Fig. 4): polynomials over generic ground rings (MultivariatePolynomial[E]) and
polynomials over Zp with p < 264 (MultivariatePolynomialZp64).
Multiplication of multivariate polynomials is done via Kronecker substitution (see e.g. Sec. 8.4 in
[13] and [33]), i.e. by reducing multivariate multiplication to a multiplication of sparse univariate
14

polynomials by appropriate replacement of variables. Sparse univariate multiplication is done with
a plain O(nm log(nm)) algorithm (where n and m are a numbers of nonzero terms in polynomials
and the logarithm occurs due to search in the tree), so, as result, the complexity of multivariate
multiplication is also O(nm log(nm)). Nevertheless, Kronecker substitution allows to significantly
(up to an order of magnitude) reduce the constant overhead: TreeMap[DegreeVector, Monomial]
(sparse multivariate) is replaced with TreeMap[Long, Monomial] (sparse univariate) which is
significantly faster (both on get() and put() operations) since comparing of long keys is much
faster than comparing of DegreeVectors [33]. Actually, one can speed up even more by using
HashMap instead of TreeMap since order of the intermediate terms is irrelevant. The described
above strategy performs especially well on sparse polynomials (which is the common use case).
It is also satisfactory for a dense ones, while certainly in this case it would be better to switch to
dense recursive representation and use asymptotically fast univariate multiplication.
Multivariate GCD switches between Zippel’s-like sparse interpolation algorithms [34, 35] and
Enhanced Extended Zassenhaus algorithm (EEZ-GCD) [36]. The latter is used only on a very
dense problems (which occur rarely), while the former is actually used in most cases. While sparse
algorithms are designed to perform well on sparse polynomials, they are actually quite fast on
most dense problems too. These algorithms require that the ground ring contains sufficient number
of elements (so they will always fail in e.g. Z2 [X® ]). When the cardinality of a ground ring is not
sufficiently large, Rings switches to a Kaltofen-Monagan generic modular algorithm [37] which
performs very well in practice. We have also implemented Brown’s [26] and Extended Zassenhaus
(EZ-GCD) [38] algorithms, but they are considerably slower both in asymptotic complexity and in
practice. It is worth to mention that the implementation of multivariate GCD in Rings is thoroughly
optimized and takes more than 4,000 lines of code: all corner cases are carefully examined and
specifically optimized and a lot of heuristics is used based on thousands of benchmarks with both
randomized and special input. As result the algorithms actually implemented in Rings are very
different from those described in the original papers and the similarity remains only in the basic
ideas.
The main idea of most factorization algorithms is simple: substitute some values for all variables
but one, then do univariate factorization and finally reconstruct multivariate factors with the
use of Hensel lifting (lift from univariate to multivariate). The differences between algorithms
lies in the details. In particular the common problem, which is addressed differently by different
algorithms, is that for efficient Hensel lifting it is required to precompute somehow the leading
coefficients of true multivariate factors. Rings uses the idea proposed by Kaltofen [39] with major
modifications due to Lee [40]. First, the multivariate case is reduced to bivariate by substituting
all but two variables with some random values (actually, Rings does several substitutions for
different sets of variables to obtain more information about factorization pattern). For factoring
bivariate polynomials, the very efficient Bernardin’s algorithm [41, 42] is used. Additionally, Rings
performs some fast early checks based on Newton polygons to ensure that there is a nontrivial
factorization [43]. Then the leading coefficients of true multivariate factors are precomputed based
on the square-free decomposition of the leading coefficient of the initial polynomial (while in the
original Kaltofen’s paper the distinct-variable decomposition is used). The final Hensel lifting is
then done via Zippel-like sparse method: instead of using variable-by-variable dense ideal-adic
interpolation, the problem of lifting is reduced to a system of (in general non-linear) equations
which we try to solve. If it is not possible to solve the system with the available methods, Rings
switches to a standard ideal-adic Hensel lifting algorithm. The latter one is also optimized by using
the quasi-dense approach, which is a generalization of Bernardin’s bivariate algorithm [40–42]. As
result, the final algorithm for multivariate polynomial factorization implemented in Rings is quite

15

efficient on both sparse and dense inputs. Similarly to the case of univariate factorization, there
is one special bad case — bivariate Swinnerton-Dyer [30] polynomials — which have nontrivial
univariate factorization (for any value substituted for second variable) but still are irreducible. For
these polynomials (which are impossible to imagine occurring in practice) Rings algorithm will
degrade to O(2r ) complexity (r is a number of univariate factors). Again, the drawback may be
fixed by the analog of van Hoeij’s algorithm [31, 40] which uses LLL lattice reduction [32], but it is
not implemented in Rings yet.
5

CONCLUSION AND FUTURE WORK

Rings is a high-performance and lightweight library for polynomial algebra that provides both
basic methods for manipulating with polynomials and high-level methods like polynomial GCD and
factorization over sophisticated ground rings. Two primary focuses were addressed in the library:
high performance and a well designed API. High performance is crucial for today’s computational
problems that arise in many research areas including high energy physics, commutative algebra,
cryptography etc. Rings performance is similar of even better than in many modern open-source
and commercial software. The API provided by the library allows to write short and expressive
code on top of the library using both object oriented and functional paradigms in a completely
type-safe manner.
Some of the planned future work for Rings includes improvement of Gröebner bases algorithms,
optimization of univariate polynomials with more advanced methods for fast multiplication, specific
optimized implementation of GF(2, k) fields which are frequently arise in cryptography and support
for algebraic extension fields.
Rings is an open-source library licensed under Apache 2.0. The source code and comprehensive
online manual can be found at http://ringsalgebra.io.
6

ACKNOWLEDGEMENTS

The author would like to thank Dmitry Bolotin and Andrei Kataev for stimulating discussions. The
work was supported by the Russian Foundation of Basic Research grant #16-32-60017.
REFERENCES
[1] Kasper J. Larsen and Yang Zhang. Integration-by-parts reductions from unitarity cuts and algebraic geometry. Phys.
Rev., D93(4):041701, 2016.
[2] Kasper J. Larsen and Robbert Rietkerk. MultivariateResidues: a Mathematica package for computing multivariate
residues. Comput. Phys. Commun., 222:250–262, 2018.
[3] Christoph Meyer. Transforming differential equations of multi-loop Feynman integrals into canonical form. JHEP,
04:006, 2017.
[4] Andreas von Manteuffel and Robert M. Schabinger. A novel approach to integration by parts reduction. Phys. Lett.,
B744:101–104, 2015.
[5] Abbas Acar, Hidayet Aksu, A. Selcuk Uluagac, and Mauro Conti. A survey on homomorphic encryption schemes:
Theory and implementation. CoRR, abs/1704.03578, 2017.
[6] Risi Kondor. Group theoretical methods in machine learning. PhD thesis, COLUMBIA UNIVERSITY, 2008. thesis.
[7] Wolfram Decker, Gert-Martin Greuel, Gerhard Pfister, and Hans Schönemann. Singular 4-1-0 — A computer algebra
system for polynomial computations. http://www.singular.uni-kl.de, 2016.
[8] V. Shoup. NTL: A Library for doing Number Theory. http://www.shoup.net/ntl.
[9] W. Hart, F. Johansson, and S. Pancratz. FLINT: Fast Library for Number Theory. http://flintlib.org.
[10] Christian Bauer, Alexander Frink, and Richard Kreckel. Introduction to the ginac framework for symbolic computation
within the c++ programming language. Journal of Symbolic Computation, 33(1):1 – 12, 2002. https://www.ginac.de.
[11] Meurer et al. Sympy: symbolic computing in python. PeerJ Computer Science, 3:e103, January 2017.
[12] H. Kredel. JAS: Java Algebra System. http://krum.rz.uni-mannheim.de/jas/.
[13] Joachim von zur Gathen and Jürgen Gerhard. Modern computer algebra (2. ed.). Cambridge University Press, 2003.
16

[14] Torbjorn Granlund and the GMP development team. GNU MP: The GNU Multiple Precision Arithmetic Library, 6.1.2
edition, 2017. http://gmplib.org/.
[15] Donald E. Knuth. The Art of Computer Programming, Volume 2 (3rd Ed.): Seminumerical Algorithms. Addison Wesley
Longman Publishing Co., Inc., Redwood City, CA, USA, 1997. Section 4.3.3.
[16] Paul Barrett. Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital
Signal Processor, pages 311–323. Springer Berlin Heidelberg, Berlin, Heidelberg, 1987.
[17] Agner Fog. Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs,
2017. http://www.agner.org/optimize/instruction tables.pdf.
[18] Henry S. Warren. Hacker’s Delight (2nd Edition). Addison Wesley - Pearson Education, Inc, 2012.
[19] Gary L. Miller. Riemann’s hypothesis and tests for primality. In Proceedings of the Seventh Annual ACM Symposium on
Theory of Computing, STOC ’75, pages 234–239, New York, NY, USA, 1975. ACM.
[20] Michael O Rabin. Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1):128 – 138, 1980.
[21] J. M. Pollard. A monte carlo method for factorization. BIT Numerical Mathematics, 15(3):331–334, Sep 1975.
[22] J. M. Pollard. Theorems on factorization and primality testing. Mathematical Proceedings of the Cambridge Philosophical
Society, 76(3):521fi?!528, 1974.
[23] Carl Pomerance. Analysis and comparison of some integer factoring algorithms. Mathematisch Centrum Computational
Methods in Number Theory, Pt. 1 p 89-139(SEE N 84-17990 08-67), 1982.
[24] R. Crandall and C.B. Pomerance. Prime Numbers: A Computational Perspective. Lecture notes in statistics. Springer
New York, 2006.
[25] D.J. Bernstein A.O.L. Atkin. Prime sieves using binary quadratic forms. Math. Comp., 73:1023–1030, 2004.
[26] W. S. Brown. On euclid’s algorithm and the computation of polynomial greatest common divisors. J. ACM, 18(4):478–
504, October 1971.
[27] Hans Cantor, David G.; Zassenhaus. A new algorithm for factoring polynomials over finite fields. Mathematics of
Computation, 36(154):587fi?!592, 1981.
[28] Victor Shoup. A new polynomial factorization algorithm and its implementation. J. Symb. Comput., 4(20):363–397,
1995.
[29] Keith O. Geddes, Stephen R. Czapor, and George Labahn. Algorithms for Computer Algebra. Kluwer Academic
Publishers, Norwell, MA, USA, 1992.
[30] Richard Zippel. Effective Polynomial Computation. Kluwer Academic Publishers, Boston, 1993.
[31] Mark van Hoeij. Factoring polynomials and the knapsack problem. Journal of Number Theory, 95(2):167 – 189, 2002.
[32] A. K. Lenstra, H. W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen,
261(4):515–534, Dec 1982.
[33] Michael Monagan and Roman Pearce. Sparse polynomial multiplication and division in maple 14. ACM Commun.
Comput. Algebra, 44(3/4):205–209, January 2011.
[34] R. E. Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposiumon on
Symbolic and Algebraic Computation EUROSAM’79, pages 216–226, London, UK, 1979. Springer-Verla.
[35] M. B. Monagan J. de Kleine and A. D. Wittkopf. Algorithms for the non-monic case of the sparse modular gcd algorithm.
In Proceeding of ISSAC’05, pages 124–131. ACM Press, 2005.
[36] P. S. Wang. The eez-gcd algorithm. ACM SIGSAM Bull., (14):50–60, 1980.
[37] E. Kaltofen and M. B. Monagan. On the genericity of the modular polynomial gcd algorithm. In Proceeding of ISSAC’99,
pages 59–66. ACM Press, 1999.
[38] J. Moses and D. Y. Y. Yun. The ezgcd algorithm. In Proceeding of ACM Annual Conference, pages 159–166. ACM, 1973.
[39] E. Kaltofen. Sparse hensel lifting. In Proceeding of EUROCAL’85, volume 2, pages 4–17. Comput. Algebra Proc., 1985.
[40] M. M.-D. Lee. Factorization of multivariate polynomials. PhD thesis, University of Kaiserslautern, 2013. thesis.
[41] L. Bernardin and M.B. Monagan. Efficient multivariate factorization over finite fields. In Proceeding of AAECC’97,
volume 1255, pages 15–28, Berlin, Heidelberg, 1997. Lecture Notes in Computer Science, Springer.
[42] L. Bernardin. Factorization of Multivariate Polynomials over Finite Fields. PhD thesis, ETH Zurich, 1999. thesis.
[43] Shuhong Gao. Absolute irreducibility of polynomials via newton polytopes. Journal of Algebra, 237(2):501 – 520, 2001.

17

