The theory of finite fields, whose origins can be traced back to the works of Gauss and Galois, has played a part in various branches of mathematics.
Due to the applicability of the concept in other topics of mathematics and sciences like computer science there has been a resurgence of interest in finite fields and this is partly due to important applications in coding theory and cryptography.
Applications of finite fields introduce some of these developments in cryptography, computer algebra and coding theory.
For each prime power q = pr, there exists exactly one finite field with q elements, up to isomorphism.
In fact, for a prime power q, let Fq be the finite field with q elements, unique up to isomorphism.
It follows that, to compute in a finite field of non prime order, one needs to generate an irreducible polynomial.
For this, the common method is to take a polynomial at random and test it for irreducibility.
For sake of efficiency of the multiplication in the field, it is usual to search for polynomials of the shape xn + ax + b.
[citation needed][1] Irreducible polynomials over finite fields are also useful for pseudorandom number generators using feedback shift registers and discrete logarithm over F2n.
The cost of a polynomial greatest common divisor between two polynomials of degree at most n can be taken as O(n2) operations in Fq using classical methods, or as O(nlog2(n) log(log(n)) ) operations in Fq using fast methods.
The algorithm determines a square-free factorization for polynomials whose coefficients come from the finite field Fq of order q = pm with p a prime.
This algorithm works also over a field of characteristic zero, with the only difference that it never enters in the blocks of instructions where pth roots are computed.
However, in this case, Yun's algorithm is much more efficient because it computes the greatest common divisors of polynomials of lower degrees.
As all of the remaining factors have multiplicity divisible by p, meaning they are powers of p, one can simply take the pth square root and apply recursion.
The algorithm computes first Since the derivative is non-zero we have w = f/c = x2 + 2 and we enter the while loop.
Using the fact that the qth power is a linear map over Fq we may compute its matrix with operations.
Then at each iteration of the loop, compute the product of a matrix by a vector (with O(deg(f)2) operations).
each of degree d. We first describe an algorithm by Cantor and Zassenhaus (1981) and then a variant that has a slightly better complexity.
For more factorization algorithms see e.g. Knuth's book The Art of Computer Programming volume 2.
The correctness of this algorithm relies on the fact that the ring Fq[x]/f is a direct product of the fields Fq[x]/fi where fi runs on the irreducible factors of f. As all these fields have qd elements, the component of g in any of these fields is zero with probability This implies that the polynomial gcd(g, u) is the product of the factors of g for which the component of g is zero.
[3] In the typical case where dlog(q) > n, this complexity may be reduced to by choosing h in the kernel of the linear map and replacing the instruction by The proof of validity is the same as above, replacing the direct product of the fields Fq[x]/fi by the direct product of their subfields with q elements.
For Shoup's algorithm, the input is restricted to polynomials over prime fields Fp.
The worst case time complexity of Shoup's algorithm has a factor
Let g = g1 ... gk be the desired factorization, where the gi are distinct monic irreducible polynomials of degree d. Let n = deg(g) = kd.
We consider the ring R = Fq[x]/g and denote also by x the image of x in R. The ring R is the direct product of the fields Ri = Fq[x]/gi, and we denote by pi the natural homomorphism from the R onto Ri.
The Galois group of Ri over Fq is cyclic of order d, generated by the field automorphism u → up.
The existence of a deterministic algorithm with a polynomial worst-case complexity is still an open problem.
Distinct-degree factorization algorithm tests every d not greater than half the degree of the input polynomial.
by repeated squaring or using the Frobenius automorphism, and then to take the correspondent gcd.
Using the elementary polynomial arithmetic, the computation of the matrix of the Frobenius automorphism needs