Seminar • Symbolic Computation — Probabilistic Algorithms for Normal BasesExport this event to calendar

Friday, March 8, 2019 1:00 PM EST

Armin Jamshidpey, Postdoctoral fellow
David R. Cheriton School of Computer Science

It is well known that for any finite Galois extension field K/F, with Galois group G = Gal(K/F), there exists an element α in 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 talk, 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 α in K is normal can be reduced to deciding whether Σσ in G σ(α)σ in 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.

This is a joint work with Mark Giesbrecht and Eric Schost (both University Waterloo).

Location 
DC - William G. Davis Computer Research Centre
1302
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
  1. 2024 (96)
    1. April (19)
    2. March (27)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)