Computational Algebra Seminar
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.
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.