Computational Algebra

The following sections are included:

• Contents
• Introduction

The method of Gröbner bases is a powerful effective technique for solving problems in commutative algebra and algebraic geometry that was coined by Bruno Buchberger in his PhD thesis. Roughly speaking, a Gröbner basis G for a system S of polynomials is an equivalent system (i.e., generating the same ideal) that possesses useful properties, for example, that another polynomial f is a combination of those in S iff the remainder of f on division by G is 0 (a monomial order being chosen). In the univariate case, a Gröbner for S is nothing but the gcd of the elements of S. Buchberger’s algorithm for computing Gröbner bases can be seen as both multivariate and nonlinear generalization of the Euclidean algorithm for computing polynomial gcd and Gaussian elimination for solving linear systems. Gröbner bases provide a uniform approach for solving problems that can be expressed in terms of systems of multivariate polynomial equations. It happens that many practical problems, e.g. in signal processing and cryptanalysis, can be transformed into sets of polynomials, thus solved using Gröbner bases technique…

The richness of algebraic geometry as a mathematical discipline comes from the interplay of algebra and geometry, as its basic objects are both geometrical and algebraic. The strong intuition of geometry translates into manipulation of algebraic objects via symbolic computation. In this chapter, we are going to study this correspondence between ideals and varieties. In Section 2.1, we will prove the celebrated Hilbert’s Nullstellensatz that translates (in its weak form) when an algebraic variety is empty in algebraic terms. This is the cornerstone to the algebra-geometry dictionary we will present translating any statement about varieties into a statement about ideals (and vice versa). This correspondence being established, Gröbner bases come to perform the necessary algebraic computations.

Finite field are algebraic structure which are both rich and easily manipulated. For these reasons they have numerous applications most notably in cryptography and coding theory.

Cryptography is the science of encryption and decryption of messages. The characters of the original text are often transformed, for transmission, into numbers. Cryptography has been used well before our era. For example, during the reign of Julius Caesar, the Romans used the following method that one will seize by the deciphering of the following short message: YHQL YLGL YLFL.

We try to replace each letter by its predecessor in the alphabet (by circular permutation) until we find a meaningful text. We find successively: XGPK XKFK XKEK, WFOJ WJEJ WJDJ, VENI VIDI VICI,

(I came, I saw, I won)…

In this chapter, K denotes a (commutative) field and $\overline{\text{K}}$ an algebraic closure of K. This chapter relies essentially on [9, 61].

An elliptic curve is a particular case of an algebraic curve equipped, among other properties, with a geometric addition of its points. Formally, an elliptic curve is a projective smooth algebraic curve of genus 1 over a field with a rational point. Elliptic curves have numerous applications in widely different fields of mathematics. For example, they were used in the proof, by Andrew Wiles, of Fermat’s Last Theorem. They also find applications in elliptic curve cryptography and integer factorization (the elliptic-curve factorization method, see Remark 403). One of the main reasons for interest in cryptosystems based on elliptic curves is that these curves are a source of a considerable number of finite Abelian groups providing the same security with smaller key size (compared to the multiplicative group of a finite field)…

The following sections are included:

• Index
• Bibliography