Type: Seminar

Distribution: World

Expiry: 12 Feb 2009

Auth: billu@renoir.maths.usyd.edu.au

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.