Fast Construction of Irreducible Polynomials of degree n over any Finite Field

In summary, irreducible polynomials are polynomials that cannot be factored into smaller polynomials over a given field. They are important in various areas of mathematics and can be constructed using algorithms such as Berlekamp's or Cantor-Zassenhaus. The degree of a polynomial refers to the highest power of the variable, and the Lenstra-Lenstra-Lovász algorithm is a general technique for constructing irreducible polynomials of any degree over a finite field.
  • #1
burritoloco
83
0
Hello, I'm currently doing an undergrad project on this topic and I was wondering if any of you guys know what is the fastest algorithm (asymptotically) that has been discovered so far, for such purpose. Here is paper by Shoup (1993) which gave the fastest algorithm up to then.

http://www.shoup.net/papers/fastirred.pdf

After that, I'm not really sure. Any ideas? Thank you.
 
Mathematics news on Phys.org
  • #2
Just found this by Jean-Marc Couveignes and Reynald Lercier (2009):

http://www.math.univ-toulouse.fr/~couveig/publi/couveignes-lercier.pdf
 
Last edited by a moderator:

1. What are irreducible polynomials?

Irreducible polynomials are polynomials that cannot be factored into smaller polynomials over a given field. In other words, they do not have any non-trivial factors.

2. Why is constructing irreducible polynomials important?

Irreducible polynomials are useful in many areas of mathematics, including coding theory and cryptography. They also have applications in other fields, such as computer science and engineering.

3. What does "degree n" mean in the context of this topic?

Degree n refers to the highest power of the variable in the polynomial. For example, a polynomial with degree 3 would have the form a0 + a1x + a2x2 + a3x3.

4. How are irreducible polynomials constructed over a finite field?

There are various methods for constructing irreducible polynomials over a finite field, including the Berlekamp's algorithm and the Cantor-Zassenhaus algorithm. These algorithms involve finding a suitable root for the polynomial and then factoring it to determine its irreducible factors.

5. Is there a specific technique for constructing irreducible polynomials of any degree over a finite field?

Yes, the Lenstra-Lenstra-Lovász (LLL) algorithm is a general technique for constructing irreducible polynomials of any degree over a finite field. This algorithm uses lattice reduction techniques to efficiently find roots and factors of polynomials, making it a popular method for fast construction of irreducible polynomials.

Similar threads

Replies
1
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
12
Views
3K
Replies
1
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • STEM Academic Advising
Replies
1
Views
879
  • Linear and Abstract Algebra
Replies
5
Views
3K
  • Calculus and Beyond Homework Help
Replies
12
Views
6K
  • Calculus and Beyond Homework Help
Replies
3
Views
3K
  • Calculus and Beyond Homework Help
Replies
2
Views
5K
Back
Top