SMS scnews item created by Bill Unger at Thu 19 Oct 2017 1139
Type: Seminar
Distribution: World
Expiry: 27 Oct 2017
Calendar1: 26 Oct 2017 1505-1600
CalLoc1: Carslaw 535A
CalTitle1: Computational Algebra Seminar - Joux

Computational Algebra Seminar: Joux -- A crossbred algorithm for solving Boolean polynomial systems

Speaker: Antoine Joux
Title: A crossbred algorithm for solving Boolean polynomial systems
Time & Place: 3-4pm, Thursday 26 October

We consider the problem of solving multivariate systems of Boolean polynomial
equations: starting from a system of m polynomials of degree at most d in
n variables, we want to find its solutions over F_2. Except for d=1, the
problem is known to be NP-hard, and its hardness has been used to create public
cryptosystems; this motivates the search for faster algorithms to solve this
problem. After reviewing the state of the art, we describe a new algorithm and
show that it outperforms previously known methods in a wide range of relevant
parameters. In particular, it can be used to solve all the Fukuoka Type I MQ
challenges, culminating with the resolution of a system of 148 quadratic
equations in 74 variables in less than a day (and quite a lot of luck).

ball Calendar (ICS file) download, for import into your favourite calendar application
ball UNCLUTTER for printing
ball AUTHENTICATE to mark the scnews item as read
School members may try to .