Wednesday, March 19, 2008 at 3:00 PM in HA 335
Stephen M. Watt, University of Western Ontario
Advances in Algorithms for Symbolic Polynomials
We wish to work with polynomials where the exponents are not known in advance,
such as $x^{2n} - 1$. There are various operations we will want to be able
to do, such as squaring the value to get $x^{4n}-2x^{2n}+1$, or differentiating
it to get $2nx^{2n-1}$. Expressions of this sort arise frequently in practice,
for example in the analysis of algorithms, and it is difficult to work with
them effectively with current computer algebra software.
We consider the case where multivariate polynomials can have exponents that are
themselves integer-valued multivariate polynomials. and we present algorithms
to compute their GCD and factorization. The algorithms fall into two families:
algebraic extension methods and interpolation methods. The first family of
algorithms uses the algebraic independence of $x$, $x^n$, $x^{n^2}$, $x^{nm}$,
etc, to solve related problems with more indeterminates. Some subtlety is
needed to treat fixed divisors of the exponent polynomials. We present a
recent result showing how to treat fixed divisors while preserving sparsity.
The second family of algorithms uses evaluation and interpolation of the
exponent polynomials. Additionally, we also explore the case of symbolic
exponents on rational coefficients (e.g. $4^{n^2+n}-81$) and show how to avoid
integer factorization.
Wednesday, March 26, 2008 at 3:00 PM in HA 335
Eric Schost, University of Western Ontario
Point counting in genus 2: towards 128 bits
Recent work on the efficiency of group operations shows that genus 2 cryptosystems can be competitive with, or faster than, their elliptic analogues, for a similar level of security. One of the last missing steps is the determination of a suitable secure curve over a prime field of size about 2^128.
I will describe ongoing work with Pierrick Gaudry towards this goal, and review some of the underlying algorithms, from factorization in high degree extensions to lifting techniques for triangular sets.Wednesday, April 16, 2008 at 3:00 PM in HA 335
Robert Quinn, NCSU
Connectivity in Semialgebraic Sets
A semialgebraic set is a subset of real space defined by polynomial equations and inequalities. A semialgebraic set is a union of finitely many maximally connected components. In this talk, we consider the problem of deciding whether two given points in a semialgebraic set are connected, that is, whether the two points lie in the same connected component. In particular, we consider the semialgebraic set defined by f not equal 0 where f is a given bivariate polynomial. The motivation comes from the observation that many important/non-trivial problems in science and engineering can be often reduced to that of connectivity. Due to its importance, there has been intense research effort on the problem. We will describe a method based on gradient fields and provide a sketch of the proof of correctness based on the Morse complex. The method seems to be more efficient than the previous methods in practice.Thursday, April 17, 2008 at 3:00 PM in HA 330
Professor Wlodek Bryc, University of Cincinnati
Spectra of Large Random Toeplitz Matrices
As the dimension tends to infinity, spectral measures of large random Toeplitz matrices with independent identically distributed entries that have finite second moments converge to the \\\"universal\\\" measure on R. I will review the main ideas in the proof, and what is known as well as what is not known about the limiting measure. I will also talk about similar results for other \\\"structured\\\" ensembles of symmetric random matrices, including the \\\"trivial cases\\\" of symmetric circulant and \\\"reversed circulant\\\" matrices.
If time permits, I will then talk about \\\"block-Toeplitz\\\" matrices where the limits of spectral measures are determined from the system of equations stated by Girko, and which in \\\"modern approach\\\" arises from matrix-valued free probability.
Wednesday, May 7, 2008 at 3:00 PM in HA 335
Prof. Maki Iwami, Osaka University of Economics and Law, Japan
Breaking the Akiyama-Goto Algebraic Surface Public-key Cryptosystem and a Short Introduction to Multivariate Analytic Factorization
I had suggested algorithms for multivariate analytic factorization
which is a factorizaion over ring of formal power series, fixing an
expansion point. And in recent years, I have studied application
possibilities for cryptosystems.
I'll talk about my recent works about breaking the Akiyama-Goto
algebraic surface pulic-key cryptosystem (ASC) whose security is
related to a problem of finding sections on fibered algebraic
surfaces.
The original ASC was proposed in 2004.
There is Uchiyama-Tokunaga attack using reductions for some special
cases on January 2007, and I generalized it to all the cases by
extending it to be able to perform in the polynomial ring over
rational function field on July 2007, and also perform in the
polynomial ring over $F_p$ using Groebner bases techniques on November
2007. There is also Inanov & Voloch trace map attack. I also propose
breaking the improved ASC proposed on January 2008. Therefore we need
a significant improvement to be a secure one, and I explain it from
the viewpoint of symbolic computation.
Note: Fresh Japanese sweets will be available at the seminar.
You can add or remove yourself from a seminar mailing list by visiting this link.
Seminar Organizer: Agnes Szanto