Publication
Factorization of polynomials by transcendental evaluation
Related concepts (38)
Stirling's approximation
In mathematics, Stirling's approximation (or Stirling's formula) is an approximation for factorials. It is a good approximation, leading to accurate results even for small values of . It is named after James Stirling, though a related but less precise result was first stated by Abraham de Moivre. One way of stating the approximation involves the logarithm of the factorial: where the big O notation means that, for all sufficiently large values of , the difference between and will be at most proportional to the logarithm.
Asymptote
In analytic geometry, an asymptote (ˈæsɪmptoʊt) of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the x or y coordinates tends to infinity. In projective geometry and related contexts, an asymptote of a curve is a line which is tangent to the curve at a point at infinity. The word asymptote is derived from the Greek ἀσύμπτωτος (asumptōtos) which means "not falling together", from ἀ priv. + σύν "together" + πτωτ-ός "fallen".
Transcendental number theory
Transcendental number theory is a branch of number theory that investigates transcendental numbers (numbers that are not solutions of any polynomial equation with rational coefficients), in both qualitative and quantitative ways. Transcendental number The fundamental theorem of algebra tells us that if we have a non-constant polynomial with rational coefficients (or equivalently, by clearing denominators, with integer coefficients) then that polynomial will have a root in the complex numbers.
Factorization of polynomials over finite fields
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.
Algebraic element
In mathematics, if L is a field extension of K, then an element a of L is called an algebraic element over K, or just algebraic over K, if there exists some non-zero polynomial g(x) with coefficients in K such that g(a) = 0. Elements of L which are not algebraic over K are called transcendental over K. These notions generalize the algebraic numbers and the transcendental numbers (where the field extension is C/Q, C being the field of complex numbers and Q being the field of rational numbers).
Transcendental extension
In mathematics, a transcendental extension is a field extension such that there exists an element in the field that is transcendental over the field ; that is, an element that is not a root of any univariate polynomial with coefficients in . In other words, a transcendental extension is a field extension that is not algebraic. For example, are both transcendental extensions of A transcendence basis of a field extension (or a transcendence basis of over ) is a maximal algebraically independent subset of over Transcendence bases share many properties with bases of vector spaces.
Fermat number
In mathematics, a Fermat number, named after Pierre de Fermat, the first known to have studied them, is a positive integer of the form where n is a non-negative integer. The first few Fermat numbers are: 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, ... . If 2k + 1 is prime and k > 0, then k itself must be a power of 2, so 2k + 1 is a Fermat number; such primes are called Fermat primes. , the only known Fermat primes are F0 = 3, F1 = 5, F2 = 17, F3 = 257, and F4 = 65537 ; heuristics suggest that there are no more.
Pollard's rho algorithm
Pollard's rho algorithm is an algorithm for integer factorization. It was invented by John Pollard in 1975. It uses only a small amount of space, and its expected running time is proportional to the square root of the smallest prime factor of the composite number being factorized. The algorithm is used to factorize a number , where is a non-trivial factor. A polynomial modulo , called (e.g., ), is used to generate a pseudorandom sequence. It is important to note that must be a polynomial.