Algebra and Cryptography Seminar, Spring 2010

Organizers: Robert Gilman, Alexei Myasnikov, and Vladimir Shpilrain


2:30-3:30 pm
Room 8405, CUNY Graduate Center
365 Fifth Avenue at 34th Street


11:00 am-12:00 pm
Room Peirce 220, Stevens Institute of Technology
Hoboken, NJ


January 29, Graduate Center: Alexander A. Mikhalev (Moscow State University), Automorphisms of free algebras of Schreier varieties
Abstract: A variety of algebras over a field is called Schreier if any subalgebra of a free algebra of this variety is free in the same variety of algebras. The main examples of Schreier varieties of algebras are: the variety of all algebras, the variety of all commutative algebras, the variety of all anti-commutative algebras, varieties of all Lie algebras and superalgebras, varieties of all restricted Lie algebras and superalgebras. In this talk we consider automorphisms of free algebras of Schreier varieties. The automorphism groups of these free algebras of finite rank are generated by elementary automorphisms. Recently U.U.Umirbaev gave a presentation of the automorphism groups of free algebras of Schreier varieties by generators and defining relations.
We then consider automorphic orbits of elements of free algebras. We show that if two finite sets of elements of a free algebra of a Schreier variety are stably equivalent, then they are equivalent. A system of elements of a free algebra is said to be primitive if it is a subset of a free generating set of this free algebra. Primitive elements distinguish automorphisms in the following sense: endomorphisms sending primitive elements to primitive elements are automorphisms. Moreover, if some endomorphism preserves the automorphic orbit of a nonzero element, then it is an automorphism. Using free differential calculus we present an algorithm to find the rank of a system of elements and matrix criteria for a system of elements to be primitive. Based on these results we obtain fast algorithms to recognize primitive systems of elements of free algebras of Schreier varieties. Algorithms to construct complements of primitive systems of elements with respect to free generating sets are constructed and implemented. We consider isomorphisms of free algebras with one defining relation.
We also discuss automorphisms of polynomial algebras, free associative algebras, Leibniz algebras, free Poisson algebras.

February 5, Graduate Center: Alexander Grishkov (University of Sao Paulo, Brazil), Groups with triality and their applications
Abstract: A group G possessing automorphisms r and s that satisfy r^3=s^2=(rs)^2=1 is called a group with triality (r, s) if
[x, s] [x, s]^r [x, s]^{r^2}=1
for every x in G, where [x, s]=x^{-1}x^s. If M=M(G)={[x, s], x in G}, then M is a Moufang loop with multiplication m.n=m^{-r}nm^{-r^2}, and a loop M is called a Moufang loop if xy \cdot zx = (x\cdot yz)x for all x,y,z in M. We use this correspondence to prove some results in the theory of Moufang loops, such as Lagrange theorem, Sylow's theorem, etc.

February 19, Graduate Center: Gregory Bard (Fordham University), Polynomials in Characteristic 2 and Logical Satisfiability: The Connections between Algebraic Cryptanalysis and SAT-Solvers
Abstract: Algebraic Cryptanalysis is the two-step process of converting a cipher system (usually a block cipher or a stream cipher) into a polynomial system of equations over a finite field; next one solves the system of equations to find the secret key of the cipher. I will use as an extended example of this the block cipher Keeloq, which I broke in the opening chapter of my dissertation, and describe how I use SAT-solvers to solve polynomial systems of equations. If time permits, I will describe other applications.

[CANCELED because of snow]  February 26, Graduate Center: Frantisek Marko (Penn State), Schur superalgebras and polynomial invariants of general linear supergroups

March 26, Graduate Center: Frantisek Marko (Penn State), Schur superalgebras and polynomial invariants of general linear supergroups

April 9, Graduate Center: Lavinia Ciungu (SUNY Buffalo), Cryptographic Boolean functions: Thue-Morse sequences, weight and nonlinearity

April 23, Graduate Center: Igor Lysenok (Moscow Steklov Institute and Stevens Institute), Quadratic equations in free groups and free monoids
Abstract: An equation in a group or monoid is called quadratic if every variable occurs in it exactly twice. Quadratic equations are a very special case of equations but in a sense, they form an important class of building blocks for equations of general form. On the other hand, they are closely related to compact surfaces and thus provide a nice geometric view. In my talk, I will discuss complexity of decision problems related to quadratic equations in free groups and free monoids.

To subscribe to the seminar mailing list, click here

Fall 2009 talks

Spring 2009 talks

Fall 2008 talks

Spring 2008 talks

Fall 2007 talks

Spring 2007 talks

Fall 2006 talks

Spring 2006 talks

Fall 2005 talks