Computational Algebra Seminar: Brent, Nakamula

Speaker: Richard Brent (ANU, joint work with Paul Zimmermann, INRIA) 

Title: Three ways to test irreducibility 

Time & Place: 3:05-3:50pm, Thursday 12 Feb, Carslaw 535.  

Abstract: We consider several algorithms for testing irreducibility of sparse
polynomials over finite fields of small characteristic.  The algorithms that are fastest
in theory turn out not to be best in practice.  A hybrid algorithm that combines the
classical approach with modular composition is suggested.  As an application, we
describe a search for irreducible trinomials (over GF(2)) whose degree is a large
Mersenne exponent.  

-------------------------------------------------------------------------------- 

Speaker: Ken Nakamula (Tokyo Metropolitan University) 

Title: Quantum Public Key Cryptosystem and Implementation over Imaginary Quadratic
Fields 

Time & Place: 4:10-4:55pm, Thursday 12 Feb, Carslaw 535.  

Abstract: First, a brief summary of the Quantum Public Key Cryptosystem (QPKC) and its
concrete scheme proposed in 2000 will be given.  The scheme uses quantum computers only
to generate public keys from private keys, but there are several practical problems even
in generating private keys.  To solve them, we propose a refined algorithm for
implementing on classical computers.  We propose an idea to increase the density or the
pseudo-density of generated knapsack problems.  We discuss how to generate public keys
without quantum computers.  We explain why we implement over imaginary quadratic fields
and what are the practical difficulties.