Loading...
Please wait, while we are loading the content...
S C ] 8 M ar 2 01 9 Quadratic Probabilistic Algorithms for Normal Bases
| Content Provider | Semantic Scholar |
|---|---|
| Author | Giesbrecht, Mark Jamshidpey, Armin Schost, Éric Cheriton, David R. |
| Copyright Year | 2019 |
| Abstract | It is well known that for any finite Galois extension field K/F, with Galois group G = Gal(K/F), there exists an element α ∈ K whose orbit G · α forms an F-basis of K. Such an element α is called normal and G · α is called a normal basis. In this paper we introduce a probabilistic algorithm for finding a normal element when G is either a finite abelian or a metacyclic group. The algorithm is based on the fact that deciding whether a random element α ∈ K is normal can be reduced to deciding whether ∑ σ∈G σ(α)σ ∈ K[G] is invertible. In an algebraic model, the cost of our algorithm is quadratic in the size of G for metacyclic G and slightly subquadratic for abelian G. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://arxiv-export-lb.library.cornell.edu/pdf/1903.03278 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
