Gauss's lemma (polynomials)

In algebra, Gauss's lemma, named after Carl Friedrich Gauss, is a statement about polynomials over the integers, or, more generally, over a unique factorization domain (that is, a ring that has a unique factorization property similar to the fundamental theorem of arithmetic). Gauss's lemma underlies all the theory of factorization and greatest common divisors of such polynomials. Gauss's lemma asserts that the product of two primitive polynomials is primitive (a polynomial with integer coefficients is primitive if it has 1 as a greatest common divisor of its coefficients). A corollary of Gauss's lemma, sometimes also called Gauss's lemma, is that a primitive polynomial is irreducible over the integers if and only if it is irreducible over the rational numbers. More generally, a primitive polynomial has the same complete factorization over the integers and over the rational numbers. In the case of coefficients in a unique factorization domain R, "rational numbers" must be replaced by "field of fractions of R". This implies that, if R is either a field, the ring of integers, or a unique factorization domain, then every polynomial ring (in one or several indeterminates) over R is a unique factorization domain. Another consequence is that factorization and greatest common divisor computation of polynomials with integers or rational coefficients may be reduced to similar computations on integers and primitive polynomials. This is systematically used (explicitly or implicitly) in all implemented algorithms (see Polynomial greatest common divisor and Factorization of polynomials). Gauss's lemma, and all its consequences that do not involve the existence of a complete factorization remain true over any GCD domain (an integral domain over which greatest common divisors exist). In particular, a polynomial ring over a GCD domain is also a GCD domain. If one calls primitive a polynomial such that the coefficients generate the unit ideal, Gauss's lemma is true over every commutative ring.

ON THE DISCRETE LOGARITHM PROBLEM IN FINITE FIELDS OF FIXED CHARACTERISTIC

Robert Granger, Thorsten Kleinjung, Jens Markus Zumbrägel

For~

q

a prime power, the discrete logarithm problem (DLP) in~

\F_{q}

consists in finding, for any

g \in \mathbb{F}_{q}^{\times}

and

h \in \langle g \rangle

, an integer~

x

such that

g^x = h

. We present an algorithm for computing discrete logarithm ...

2016

Automorphisms of even unimodular lattices and equivariant Witt groups

ON THE DISCRETE LOGARITHM PROBLEM IN FINITE FIELDS OF FIXED CHARACTERISTIC

Automorphisms of even unimodular lattices and equivariant Witt groups

ON THE DISCRETE LOGARITHM PROBLEM IN FINITE FIELDS OF FIXED CHARACTERISTIC