See also Section Generic Element Functions.
True if and only if the element a of F is a primitive element for F (i.e., if and only if the multiplicative order of a is #F - 1).
Given a univariate polynomial f in F[x], over a finite field F, such that the degree of f is greater than or equal to 1, this function returns true if and only if f defines a primitive extension G=F[x]/f of F (that is, x is primitive in G).
True if and only if the element a of F generates a normal basis for the field over the ground field, that is, if and only if a, a^q, ..., a^(q^(n - 1)) form a basis for F over the ground field G=GF(q).
True if and only if the element a of F=GF(q^n) generates a normal basis for F over its subfield E=GF(q), that is, if and only if a, a^q, ..., a^(q^(n - 1)) form a basis for F over E.
Given a finite field element a in F, this function returns either true and an element b in F such that b^2=a, or it returns false in the case that such an element does not exist.
The minimal polynomial of the element a of the field F, relative to the ground field of F. This is the unique minimal-degree monic polynomial with coefficients in the ground field, having a as a root.
The minimal polynomial of the element a of the field F, relative to the subfield E of F. This is the unique minimal-degree monic polynomial with coefficients in E, having a as a root.
Given an element a of a finite field F, return the characteristic polynomial of a with respect to the ground field of F. (This polynomial is the characteristic polynomial of the companion matrix of a written as a polynomial over the ground field, and is a power of the minimal polynomial.)
Given an element a of a finite field F, return the characteristic polynomial of a with respect to the subfield E of F. (This polynomial is the characteristic polynomial of the companion matrix of a written as a polynomial over E, and is a power of the minimal polynomial over E.)
The norm of the element a from the field F to the ground field of F.
The relative norm of the element a from the field F, with respect to the subfield E of F. The result is an element of E.
The absolute norm of the element a, that is, the norm to the prime subfield of the parent field F of a.
The trace of the element a from the field F to the ground field of F.
The relative trace of the element a from field F, with respect to the subfield E of F. The result is an element of E.
The trace of the element a, that is, the trace to the prime subfield of the parent field F of a.
Given a finite field K and an element y of a subfield S of K, return whether an element x in K exists such that Norm(x, S) = y, and, if so, such an element x (in K).
The discrete logarithm of the non-zero element x from the field F, i.e., the unique integer k such that x = w^k and 0 <= k < (#F - 1), where w is the primitive element of F (as returned by PrimitiveElement). See also SetPrimitiveElement.There are a couple different algorithms that may be used here. If the field has degree larger than 1, then the Pohlig-Hellman algorithm, combined with the Shanks baby-step/giant-step and Pollard-rho algorithms, is employed, so that the time taken to compute the logarithm of an arbitrary element is usually proportional to the square root of the largest prime dividing the order of the multiplicative group of the field. The same will be used if the field is GF(p) for prime p and the largest prime factor of p - 1 is no more than 32-bits in length. Otherwise, Magma will attempt to use an index calculus method, which will either be the Gaussian integer sieve or the linear sieve. The Gaussian integer sieve will be used if p has at least 4 bits but no more than 400 bits, p - 1 is not a square, and one of the following is a quadratic residue modulo p: -1, -2, -3, -7, or -11. The linear sieve will be used if the Gaussian integer sieve cannot be used, and if p is no more than 300-bits. If neither of the index calculus methods can be used, Magma returns to the Pohlig-Hellman strategy.
When an index-calculus method is first used for some finite field, a precomputation stage takes place which may require a lot of memory for large fields. This precomputation stage also requires a lot more time than computing individual logarithms. Thus, the first call to Log may take much more time than subsequent calls. Also, in comparison to the Gaussian method, the linear sieve requires much more time and memory for the precomputation stage in large fields, and therefore it is only used when no other alternative is available.
The discrete logarithm to the base b of the non-zero element x from the field F, i.e., the unique integer k such that x = b^k and 0 <= k < (#F - 1). If b is not a primitive element, then in some unusual cases the algorithm may take much longer than normal. See also SetPrimitiveElement.
(Procedure.) Set the verbose printing level for the finite field logarithm algorithm to be v. Currently the legal values for v are 0, 1, and 2. If the level is 1, information is printed whenever the logarithm of an element is computed (unless the field is very small, in which case a lookup table is used). The value of 2 will print much more information than most users will ever care to see.
The multiplicative order of the non-zero element a of the field F.
The multiplicative order of the non-zero element a of the field F as a factorization sequence.
The square root of the non-zero element a from the field F, i.e., an element y of F such that y^2 = a. An error results if a is not a square.
The n-th root of the non-zero element a from the field F, i.e., an element y of F such that y^n = a. An error results if no such root exists.
Given a finite field element a in F, and an integer n>0, this function returns either true and an element b in F such that b^n=a, or it returns false in the case that such an element does not exist.
Given a finite field element a in F, and an integer n>0, return a sequence containing all of the n-th roots of a which lie in the same field F.
> F7 := FiniteField(7); > F49<w> := ext< F7 | 2 >; > F<z> := ext< F49 | 2 >; > Root(z^73, 7); z^1039 > Trace(z^73); 0 > Trace(z^73, F49); w^44 > Norm(z^73); 3 > Norm(z^73, F49); w^37 > Norm(w^37); 3 > MinimalPolynomial(z^73); x^2 + w^20*x + w^43 > MinimalPolynomial(z^73, F7); x^4 + 4*x^2 + 4*x + 3We now demonstrate the Log function.
> PrimitiveElement(F); z; > Log(z); 1 > Log(z^2); 2 > Log(z + 1); 419 > z^419 eq z + 1; true > b := z + 1; > b; z^419 > Log(b, b); 1 > Log(b, z); 779 > b^779 eq z; trueWe now demonstrate the NormEquation function.
> Norm(z); 3 > NormEquation(F, F7!3); true z > Norm(z^30, F49); w^30 > Parent(z) eq F; true > NormEquation(F, w^30); true z^30
Let K be a finite field. A polynomial representing a bijection of K into itself is known as a permutation polynomial. The Dickson polynomials of the first and second kind are permutation polynomials when certain conditions are satisfied.
Given a positive integer n, this function constructs the Dickson polynomial of the first kind D_n (x, a) of degree n, where D_n (x, a) is defined by D_n(x, a) = sum_(i=0)^( Floor(n/2)) (n /(n - i)) ((n - i) choose i) ( - a)^i x^(n - 2i).
Given a positive integer n, this function constructs the Dickson polynomial of the second kind E_n (x, a) of degree n, where E_n (x, a) is defined by E_n(x, a) = sum_(i=0)^( Floor(n/2)) ((n - i) choose (i)) ( - a)^i x^(n - 2i).
NumAttempts: RngIntElt Default: 100
Let p denote a polynomial defined over a finite field K. A probabilistic test is applied to determine whether the mapping on K defined by p is a bijection. The function returns true if the test succeeds for each of n attempts, otherwise false. By default, n is taken to be 100; a different value for n can be specified by use of the parameter NumAttempts.
> Factorization(16^2 - 1); [ <3, 1>, <5, 1>, <17, 1> ]
Thus, D_n (x, a) will be a permutation polynomial for K providing that n is coprime to 3, 5 and 17.
> K<w> := GF(16);
> R<x> := PolynomialRing(K);
> a := w^5;
> p1 := DicksonFirst(3, a);
> p1;
x^3 + w^5*x
> #{ Evaluate(p1, x) : x in K };
11
> IsProbablyPermutationPolynomial(p1);
false
So D_3 (x, a) is not a permutation polynomial. However, D_4 (x, a) is a permutation polynomial:
> p1 := DicksonFirst(4, a);
> p1;
x^7 + w^5*x^5 + x
> #{ Evaluate(p1, x) : x in K };
16
> IsProbablyPermutationPolynomial(p1);
true
[Next][Prev] [Right] [Left] [Up] [Index] [Root]