Fall 2021 Projects
Cracking the Enigma Heading link
Project Supervisor: James Freitag
The Enigma was a device used by German forces to send and recieve encrypted messages during World War II. It is estimated that around 40,000 of the machines were built during the war. A team of British scientists including the famous mathematician Alan Turing used a combination of computers and mathematics to build electronic machines capable of decrypting the secret messages encoded by Enigma machines. The goal of this project is to build programs to decode several enigma-type cryptography machines. We may not have the quite as big a team as the British did at Bletchley park, but we’ll benefit from 80 years of computer hardware and software development. The stakes of our main decryption project don’t involve the outcome of a major war and none of us is likely to appear on a fifty pound note, but there is a small cash prize that we will win if successful.
For our research project we were faced with deciphering an unknown message encrypted by a device based on the Enigma Machines used in WW2; with a prize of $150 offered to the first group to successfully decrypt it. Our plan was to use modern computing power and statistical filters to automatically search the entire space of possible decryptions. Our hope was that we could return a reasonably small number of promising candidates. With some 266 billion possible decryptions, totalling to more than 47 terabytes of possible solutions, this was a large task. By the end of semester we had successfully implemented a proof of concept, and we are currently able to automatically produce candidates and apply filters to them. Unfortunately the difficulties of finding powerful yet still safe to use filters has been more difficult than anticipated, and we still produce too many results for a human to check. We are still investigating better methods of filtering, and hope to eventually claim the prize. Though our computers are much faster than those used in WW2, the Enigma Machine has still proved to be a formidable challenge.
Finding roots of matrix polynomials Heading link
Project Supervisor: Wouter Van Limbeek
By the Fundamental Theorem of Algebra, a polynomial with real coefficients has only finitely many roots, and their number is at most the degree of the polynomial. In this project, we study polynomials whose coefficients are not real numbers, but matrices. In this case, the roots are much less understood. This project will implement numerical methods for finding the roots of such polynomials, and use these results to study the geometry of the solutions of such equations.
Outcomes: The outcome is finding the existence of matrix polynomials using a computer program that belongs to a nontrivial Galois group. An ancillary goal accomplished was a method to graph matrix polynomials by SVD-decomposition.