- UNSW
- ...
- Our schools
- Mathematics & Statistics
- Engage with us
- Seminars
- 2016
- Multiplication of polynomials over finite fields
- Home
- Our school
- Study with us
- Our research
-
Student life & resources
- Undergraduate
- Honours year
- Postgraduate coursework
-
Postgraduate research
- Info for new students
- Current research students
- Postgraduate conference
- Postgraduate events
- Postgraduate student awards
- Michael Tallis PhD Research Travel Award
- Information about research theses
- Past research students
- Resources
- Entry requirements
- PhD projects
- Obtaining funding
- Application & fee information
-
Student services
- Help for postgraduate students
- Thesis guidelines
- School assessment policies
- Computing information
- Mathematics Drop-in Centre
- Consultation
- Statistics Consultation Service
- Academic advice
- Enrolment variation
- Changing tutorials
- Illness or misadventure
- Application form for existing casual tutors
- ARC grants Head of School sign off
- Computing facilities
- Choosing your major
- Student societies
- Student noticeboard
- Casual tutors
- Engage with us
- News & events
- Contact
- Home
- Our school
- Study with us
- Our research
-
Student life & resources
Postgraduate research
- Info for new students
- Current research students
- Postgraduate conference
- Postgraduate events
- Postgraduate student awards
- Michael Tallis PhD Research Travel Award
- Information about research theses
- Past research students
- Resources
- Entry requirements
- PhD projects
- Obtaining funding
- Application & fee information
Student services
- Help for postgraduate students
- Thesis guidelines
- School assessment policies
- Computing information
- Mathematics Drop-in Centre
- Consultation
- Statistics Consultation Service
- Academic advice
- Enrolment variation
- Changing tutorials
- Illness or misadventure
- Application form for existing casual tutors
- ARC grants Head of School sign off
- Computing facilities
- Choosing your major
- Engage with us
- News & events
- Contact
Abstract:
Computations over finite fields, apart being of interest in their own right, have many applications in error-correcting codes (which usually are linear spaces over finite fields).
Also, there is a very tight relationship between algorithms for polynomial multiplication and error-correcting codes. Namely, each algorithm naturally transforms into a code and, conversely, good codes ``extend'' to fast algorithms.
In addition, all known algorithms for integer multiplications involve polynomial multiplication.
This talk is about the number of algebraic operations, mainly multiplications, involved in computing the coefficients of the product of two polynomials over a finite field.
Multiplications are counted because
- they are much more complex than additions and
- the number of additions usually depends on the number of multiplications.
Based on an upper bound on the minimal distance of some error-correcting codes, we establish a lower bound on the complexity of multiplication over finite fields.
The talk is self-contained and does not presume any acquaintance with complexity of algebraic computations or error-correcting codes.