2009 REU Program Information

Program Participants:

Anton Bobkov, University of California Los Angeles
Neal Coleman, Ball State University
TJ Ellis, University of Cincinnati
Katie Jones, Northern Kentucky University
Megan Maguire, University of California Santa Barbara
Jacob Turner, Western Kentucky University

2009 REU in Mathematical Cryptology Problems

Mutant XL Algorithms:  Anton Bobkov and Jacob Turner explored the mutant algorithms MXL, MXL2, and MXL3, the theory behind them and the intuition behind the mutant strategy. They also examined the details of the implementation by M. Mohamed. They explored possible improvements such as partial enlargement based on leading variables, random partial enlargement,  partial reduction based on leading variables, and changes of ordering to produce mutants or sparse polynomials.

Applying Sparse Matrix Algorithms:  TJ Elllis and Katie Jones studied Wiedemann’s algorithm to solve sparse systems of linear equations. They considered its performance with other well known linear algebra solvers such as: conjugate gradient, Lanczos, and Structured Gaussian Elimination.  They explored the feasibility of using Wiedemann’s algorithm in the XL context and in the Mutant XL context.

Exploring Syzygies:  Neal Coleman and Megan Maguire studied the Buchberger criteria and the concept of syzygies and their connection with the Buchberger algorithm. They explored the matrix F5 algorithm for computing Gröbner bases and studied regularity and semiregularity.