A session with Fermat usually starts by choosing rational or modular "mode" to establish the ground field (or ground ring) as or . On top of this may be attached any number of symbolic variables thereby creating the polynomial ring and its quotient field. Further, some polynomials involving some of the can be chosen to mod out with, creating the quotient ring Finally, it is possible to allow Laurent polynomials, those with negative as well as positive exponents. Once the computational ring is established in this way, all computations are of elements of this ring. The computational ring can be changed later in the session.
The polynomial gcd procedures, which call each other in a highly recursive manner, are about 7000 lines of code.
The basic data item in Fermat is a multivariate rational function or quolynomial. The numerator and denominator are polynomials with no common factor. Polynomials are implemented recursively as general linked lists, unlike some systems that implement polynomials as lists of monomials. To implement (most) finite fields, the user finds an irreducible monic polynomial in a symbolic variable, say and commands Fermat to mod out by it. This may be continued recursively, etc. Low level data structures are set up to facilitate arithmetic and gcd over this newly created ground field. Two special fields, and are more efficiently implemented at the bit level.
History
With Windows 10, and thanks to Bogdan Radu, it is now possible (May 2021) to run Fermat Linux natively on Windows. See the main web page http://home.bway.net/lewis
Fermat was last updated on 20 May 2020 (Mac and Linux; latest Windows version: 1 November 2011).
In an earlier version, called FFermat (Float Fermat), the basic number type is floating point numbers of 18 digits. That version allows for numerical computing techniques, has extensive graphics capabilities, no sophisticated polynomial gcd algorithms, and is available only for Mac OS 9.
Fermat was originally written in Pascal for a DECVAX, then for the classic Mac OS during 1985–1996. It was ported to Microsoft Windows in 1998. In 2003 it was translated into C and ported to Linux (Intel machines) and Unix (Sparc/Sun). It is about 98,000 lines of C code.
The FFermat and (old) Windows Fermat Pascal source code have been made available to the public under a restrictive license.
The manual was extensively revised and updated on 25 July 2011 (latest small revision in June 2016, apparently another revision on 25 March 2020).
Algebraic geometry is a branch of mathematics, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical problems about these sets of zeros.
In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements . It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.
In mathematics, a polynomial is an expression consisting of indeterminates and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example of a polynomial of a single indeterminate x is x2 − 4x + 7. An example with three indeterminates is x3 + 2xyz2 − yz + 1.
In mathematics, factorization or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, 3 × 5 is a factorization of the integer 15, and (x – 2)(x + 2) is a factorization of the polynomial x2 – 4.
In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that
In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted for the possible factors, that is, the field to which the coefficients of the polynomial and its possible factors are supposed to belong. For example, the polynomial x2 − 2 is a polynomial with integer coefficients, but, as every integer is also a real number, it is also a polynomial with real coefficients. It is irreducible if it is considered as a polynomial with integer coefficients, but it factors as if it is considered as a polynomial with real coefficients. One says that the polynomial x2 − 2 is irreducible over the integers but not over the reals.
In algebraic geometry, an affine variety, or affine algebraic variety, over an algebraically closed field k is the zero-locus in the affine space kn of some finite family of polynomials of n variables with coefficients in k that generate a prime ideal. If the condition of generating a prime ideal is removed, such a set is called an (affine) algebraic set. A Zariski open subvariety of an affine variety is called a quasi-affine variety.
In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring K[x1, ..., xn] over a field K. A Gröbner basis allows many important properties of the ideal and the associated algebraic variety to be deduced easily, such as the dimension and the number of zeros when it is finite. Gröbner basis computation is one of the main practical tools for solving systems of polynomial equations and computing the images of algebraic varieties under projections or rational maps.
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.
In mathematics, an algebraic equation or polynomial equation is an equation of the form
In mathematics, the resultant of two polynomials is a polynomial expression of their coefficients, which is equal to zero if and only if the polynomials have a common root, or, equivalently, a common factor. In some older texts, the resultant is also called the eliminant.
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. Gauss's lemma underlies all the theory of factorization and greatest common divisors of such polynomials.
In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems.
In mathematics, a square-free polynomial is a polynomial defined over a field that does not have as a divisor any square of a non-constant polynomial. A univariate polynomial is square free if and only if it has no multiple root in an algebraically closed field containing its coefficients. This motivates that, in applications in physics and engineering, a square-free polynomial is commonly called a polynomial with no repeated roots.
In mathematics, and more specifically in analysis, a holonomic function is a smooth function of several variables that is a solution of a system of linear homogeneous differential equations with polynomial coefficients and satisfies a suitable dimension condition in terms of D-modules theory. More precisely, a holonomic function is an element of a holonomic module of smooth functions. Holonomic functions can also be described as differentiably finite functions, also known as D-finite functions. When a power series in the variables is the Taylor expansion of a holonomic function, the sequence of its coefficients, in one or several indices, is also called holonomic. Holonomic sequences are also called P-recursive sequences: they are defined recursively by multivariate recurrences satisfied by the whole sequence and by suitable specializations of it. The situation simplifies in the univariate case: any univariate sequence that satisfies a linear homogeneous recurrence relation with polynomial coefficients, or equivalently a linear homogeneous difference equation with polynomial coefficients, is holonomic.
In mathematics, particularly computational algebra, Berlekamp's algorithm is a well-known method for factoring polynomials over finite fields. The algorithm consists mainly of matrix reduction and polynomial GCD computations. It was invented by Elwyn Berlekamp in 1967. It was the dominant algorithm for solving the problem until the Cantor–Zassenhaus algorithm of 1981. It is currently implemented in many well-known computer algebra systems.
In computational algebra, the Cantor–Zassenhaus algorithm is a method for factoring polynomials over finite fields.
In algebra, the greatest common divisor of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common divisor of two integers.
In algebra, the content of a polynomial with integer coefficients is the greatest common divisor of its coefficients. The primitive part of such a polynomial is the quotient of the polynomial by its content. Thus a polynomial is the product of its primitive part and its content, and this factorization is unique up to the multiplication of the content by a unit of the ring of the coefficients.
In mathematics and computer algebra the factorization of a polynomial consists of decomposing it into a product of irreducible factors. This decomposition is theoretically possible and is unique for polynomials with coefficients in any field, but rather strong restrictions on the field of the coefficients are needed to allow the computation of the factorization by means of an algorithm. In practice, algorithms have been designed only for polynomials with coefficients in a finite field, in the field of rationals or in a finitely generated field extension of one of them.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
