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

Click For Summary
SUMMARY

The fastest known algorithm for constructing irreducible polynomials of degree n over any finite field is detailed in the paper by Shoup (1993). This algorithm was the benchmark until the advancements presented by Couveignes and Lercier (2009). The discussion highlights the significance of these papers in the field of computational algebra and suggests that further exploration of these algorithms can yield improved methods for polynomial construction.

PREREQUISITES
  • Understanding of finite fields and their properties
  • Familiarity with polynomial algebra
  • Knowledge of asymptotic analysis in algorithms
  • Basic comprehension of computational complexity
NEXT STEPS
  • Read Shoup's 1993 paper on fast construction of irreducible polynomials
  • Examine Couveignes and Lercier's 2009 paper for advancements in polynomial algorithms
  • Research additional algorithms for polynomial factorization in finite fields
  • Explore computational tools for implementing polynomial construction algorithms
USEFUL FOR

Mathematicians, computer scientists, and students involved in algebraic structures, particularly those focusing on finite fields and polynomial algorithms.

burritoloco
Messages
81
Reaction score
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.
 
Physics news on Phys.org
Just found this paper by Jean-Marc Couveignes and Reynald Lercier (2009):

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

Similar threads

Graduate Fast Construction of Irreducible Polynomials of degree n over any Finite Field
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Irreducible Polynomials over Finite Fields
  • · Replies 5 ·
Replies
5
Views
3K
Graduate Irreducibility test for polynomials over Fp
  • · Replies 4 ·
Replies
4
Views
6K
Graduate Is There an Algebraic Closure for Every Field?
  • · Replies 1 ·
Replies
1
Views
3K
Irreducible polynomial over finite field
  • · Replies 12 ·
Replies
12
Views
8K
Constructing a Finite Field of Order 16 and Finding Primative Element
  • · Replies 3 ·
Replies
3
Views
3K
Admissions Honest opinions and advice on Statement of Purpose requested
  • · Replies 1 ·
Replies
1
Views
3K
Admissions Statement of purpose critique request (high-energy theory PhD application)
  • · Replies 7 ·
Replies
7
Views
4K
Irreducibility of a general polynomial in a finite field
  • · Replies 3 ·
Replies
3
Views
3K
Admissions Could I please get critique on my SOP? (Experimental Biophysics)
  • · Replies 9 ·
Replies
9
Views
2K