Tutte seminar - Bruce RichmondExport this event to calendar

Friday, July 6, 2012 — 3:30 PM to 4:30 PM EDT

Factoring Polynomials over a Finite Field

Speaker: Bruce Richmond
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

The basic algorithms for factoring polynomials over a finite field go back two hundred years, according to the book Modern Computer Algebra by Joachim von zur Gathen and Jürgen Gerhard. It seems Galois first publised an algorithm but this algorithm was given previously by Gauss in sources unpublished until after his death.

There has been rapid progress in the last 20 years. There is now an algorithm of von zur Gathen and Gerhard that factored a pseudorandom polynomial of degree more than 1,000,000 in four days of CPU time on a Linux PC with four Pentium III processors clocked at 500 MHz (whatever that means).

Recently von zur Gathen, Panario and I published a paper in Algorithmica (2012) 63:363-397 analyzing a factoring method of Cantor and Zassenhaus. This algorithm partitions the set of potential factor degrees into intervals [sk-1+1,sk]. It turns out that the optimal choice for sk is sk=k1/3. In this case a polynomial of degree n requires calculating n1/3 gcds.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
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
1
2
  1. 2021 (90)
    1. October (2)
    2. September (12)
    3. August (7)
    4. July (10)
    5. June (12)
    6. May (7)
    7. April (9)
    8. March (13)
    9. February (8)
    10. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)