|
Primitive Element (finite Field)
In field theory, a primitive element of a finite field is a generator of the multiplicative group of the field. In other words, is called a primitive element if it is a primitive th root of unity in ; this means that each non-zero element of can be written as for some natural number . If is a prime number, the elements of can be identified with the integers modulo . In this case, a primitive element is also called a primitive root modulo . For example, 2 is a primitive element of the field and , but not of since it generates the cyclic subgroup of order 3; however, 3 is a primitive element of . The minimal polynomial of a primitive element is a primitive polynomial. Properties Number of primitive elements The number of primitive elements in a finite field is , where is Euler's totient function, which counts the number of elements less than or equal to that are coprime In number theory, two integers and are coprime, relatively prime or mutually prime i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Simple Extension
In field theory, a simple extension is a field extension that is generated by the adjunction of a single element, called a ''primitive element''. Simple extensions are well understood and can be completely classified. The primitive element theorem provides a characterization of the finite simple extensions. Definition A field extension is called a simple extension if there exists an element in ''L'' with :L = K(\theta). This means that every element of can be expressed as a rational fraction in , with coefficients in ; that is, it is produced from and elements of by the field operations +, −, •, / . Equivalently, is the smallest field that contains both ' and . There are two different kinds of simple extensions (see below): # The element may be transcendental over , which means that it is not a root of any polynomial with coefficients in . In this case K(\theta) is isomorphic to the field of rational functions K(X). # Otherwise, is algebraic over ; that is, i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Minimal Polynomial (field Theory)
In field theory, a branch of mathematics, the minimal polynomial of an element of an extension field of a field is, roughly speaking, the polynomial of lowest degree having coefficients in the smaller field, such that is a root of the polynomial. If the minimal polynomial of exists, it is unique. The coefficient of the highest-degree term in the polynomial is required to be 1. More formally, a minimal polynomial is defined relative to a field extension and an element of the extension field . The minimal polynomial of an element, if it exists, is a member of , the ring of polynomials in the variable with coefficients in . Given an element of , let be the set of all polynomials in such that . The element is called a root or zero of each polynomial in More specifically, ''J''''α'' is the kernel of the ring homomorphism from ''F'' 'x''to ''E'' which sends polynomials ''g'' to their value ''g''(''α'') at the element ''α''. Because it is the kernel of a ring homom ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Zech's Logarithm
Zech logarithms are used to implement addition in finite fields when elements are represented as powers of a generator \alpha. Zech logarithms are named after Julius Zech, and are also called Jacobi logarithms, after Carl G. J. Jacobi who used them for number theoretic investigations. Definition Given a primitive element \alpha of a finite field, the Zech logarithm relative to the base \alpha is defined by the equation :\alpha^ = 1 + \alpha^n, which is often rewritten as :Z_\alpha(n) = \log_\alpha(1 + \alpha^n). The choice of base \alpha is usually dropped from the notation when it is clear from the context. To be more precise, Z_\alpha is a function on the integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...s modular arithmetic, modulo the multiplicative order of \alph ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Primitive Element Theorem
In field theory, the primitive element theorem states that every finite separable field extension is simple, i.e. generated by a single element. This theorem implies in particular that all algebraic number fields over the rational numbers, and all extensions in which both fields are finite, are simple. Terminology Let E/F be a ''field extension''. An element \alpha\in E is a ''primitive element'' for E/F if E=F(\alpha), i.e. if every element of E can be written as a rational function in \alpha with coefficients in F. If there exists such a primitive element, then E/F is referred to as a '' simple extension''. If the field extension E/F has primitive element \alpha and is of finite degree n = :F/math>, then every element \gamma\in E can be written in the form :\gamma =a_0+a_1+\cdots+a_^, for unique coefficients a_0,a_1,\ldots,a_\in F. That is, the set :\ is a basis for ''E'' as a vector space over ''F''. The degree ''n'' is equal to the degree of the irreducible poly ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Simple Extension
In field theory, a simple extension is a field extension that is generated by the adjunction of a single element, called a ''primitive element''. Simple extensions are well understood and can be completely classified. The primitive element theorem provides a characterization of the finite simple extensions. Definition A field extension is called a simple extension if there exists an element in ''L'' with :L = K(\theta). This means that every element of can be expressed as a rational fraction in , with coefficients in ; that is, it is produced from and elements of by the field operations +, −, •, / . Equivalently, is the smallest field that contains both ' and . There are two different kinds of simple extensions (see below): # The element may be transcendental over , which means that it is not a root of any polynomial with coefficients in . In this case K(\theta) is isomorphic to the field of rational functions K(X). # Otherwise, is algebraic over ; that is, i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
 |
Field (mathematics)
In mathematics, a field is a set (mathematics), set on which addition, subtraction, multiplication, and division (mathematics), division are defined and behave as the corresponding operations on rational number, rational and real numbers. A field is thus a fundamental algebraic structure which is widely used in algebra, number theory, and many other areas of mathematics. The best known fields are the field of rational numbers, the field of real numbers and the field of complex numbers. Many other fields, such as field of rational functions, fields of rational functions, algebraic function fields, algebraic number fields, and p-adic number, ''p''-adic fields are commonly used and studied in mathematics, particularly in number theory and algebraic geometry. Most cryptographic protocols rely on finite fields, i.e., fields with finitely many element (set), elements. The theory of fields proves that angle trisection and squaring the circle cannot be done with a compass and straighte ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
 |
Coprime
In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivalent to their greatest common divisor (GCD) being 1. One says also ''is prime to'' or ''is coprime with'' . The numbers 8 and 9 are coprime, despite the fact that neither—considered individually—is a prime number, since 1 is their only common divisor. On the other hand, 6 and 9 are not coprime, because they are both divisible by 3. The numerator and denominator of a reduced fraction are coprime, by definition. Notation and testing When the integers and are coprime, the standard way of expressing this fact in mathematical notation is to indicate that their greatest common divisor is one, by the formula or . In their 1989 textbook '' Concrete Mathematics'', Ronald Graham, Donald Knuth, and Oren Patashnik proposed an alte ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
 |
Euler's Totient Function
In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In other words, it is the number of integers in the range for which the greatest common divisor is equal to 1. The integers of this form are sometimes referred to as totatives of . For example, the totatives of are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, since and . Therefore, . As another example, since for the only integer in the range from 1 to is 1 itself, and . Euler's totient function is a multiplicative function, meaning that if two numbers and are relatively prime, then . This function gives the order of the multiplicative group of integers modulo (the group of units of the ring \Z/n\Z). It is also used for defining the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
Primitive Polynomial (field Theory)
In field theory (mathematics), finite field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial (field theory), minimal polynomial of a primitive element (finite field), primitive element of the finite field . This means that a polynomial of degree with coefficients in is a ''primitive polynomial'' if it is monic polynomial, monic and has a root in such that \ is the entire field . This implies that is a primitive root of unity, primitive ()-root of unity in . Properties * Because all minimal polynomials are irreducible polynomial, irreducible, all primitive polynomials are also irreducible. * A primitive polynomial must have a non-zero constant term, for otherwise it will be divisible by ''x''. Over GF(2), is a primitive polynomial and all other primitive polynomials have an odd number of terms, since any polynomial mod 2 with an even number of terms is divisible by (it has 1 as a root). * An irreducible polynomial ''F''(''x'') of degre ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Primitive Root Modulo N
In modular arithmetic, a number is a primitive root modulo if every number coprime to is congruent to a power of modulo . That is, is a ''primitive root modulo'' if for every integer coprime to , there is some integer for which ≡ (mod ). Such a value is called the index or discrete logarithm of to the base modulo . So is a ''primitive root modulo'' if and only if is a generator of the multiplicative group of integers modulo . Gauss defined primitive roots in Article 57 of the '' Disquisitiones Arithmeticae'' (1801), where he credited Euler with coining the term. In Article 56 he stated that Lambert and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a prime . In fact, the ''Disquisitiones'' contains two proofs: The one in Article 54 is a nonconstructive existence proof, while the proof in Article 55 is constructive. A primitive root exists if and only if ''n'' is 1, 2, 4, ''p''''k'' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
 |
Field Theory (mathematics)
In mathematics, a field is a set (mathematics), set on which addition, subtraction, multiplication, and division (mathematics), division are defined and behave as the corresponding operations on rational number, rational and real numbers. A field is thus a fundamental algebraic structure which is widely used in algebra, number theory, and many other areas of mathematics. The best known fields are the field of rational numbers, the field of real numbers and the field of complex numbers. Many other fields, such as field of rational functions, fields of rational functions, algebraic function fields, algebraic number fields, and p-adic number, ''p''-adic fields are commonly used and studied in mathematics, particularly in number theory and algebraic geometry. Most cryptographic protocols rely on finite fields, i.e., fields with finitely many element (set), elements. The theory of fields proves that angle trisection and squaring the circle cannot be done with a compass and straighte ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
 |
Integers Modulo N
In mathematics, modular arithmetic is a system of arithmetic operations for integers, other than the usual ones from elementary arithmetic, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book '' Disquisitiones Arithmeticae'', published in 1801. A familiar example of modular arithmetic is the hour hand on a 12-hour clock. If the hour hand points to 7 now, then 8 hours later it will point to 3. Ordinary addition would result in , but 15 reads as 3 on the clock face. This is because the hour hand makes one rotation every 12 hours and the hour number starts over when the hour hand passes 12. We say that 15 is ''congruent'' to 3 modulo 12, written 15 ≡ 3 (mod 12), so that 7 + 8 ≡ 3 (mod 12). Similarly, if one starts at 12 and waits 8 hours, the hour hand will be at 8. If one instead waited twice as long, 16 hours, the hour hand would be on 4. This can b ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |