Master

Keywords: factorization, prime numbers, number theory

Prerequisites: 01018: Discrete Mathematics 2

The security of the RSA cryptosystem depends on the hardness of the integer factoring problem. In general this is a hard problem for which no fast algorithms are known. More precisely, given a natural number \(N \le 10^n\) there currently does not exist an algorithm that would for any such \(N\) finds all its prime factors in time polynomial in n.

While naïve algorithms such as finding prime factors of n by trial and error, have exponential running time in \(n\), there also exist factoring algorithms that have so-called subexponential running time in \(n\). One example of such an integer factoring algorithm is the quadratic sieve.

The currently fastest integer factoring algorithm is the famous number field sieve. The name of this algorithm comes from number fields: finite dimensional algebraic extension fields of \(\mathbb{Q}\). In this project you will learn about number fields and several rings contained in them as well as their relation to the number field sieve.

Keywords: coding theory, root finding, decoding, fast algorithms

Prerequisites: 01405: Algebraic Coding Theory

In hardware implementations of BCH decoders, error location is bottleneck, i.e. finding the error-locator polynomial and afterwards, the roots of the error locator polynomial. In high-density optical transmission, one would like to be able to correct up to 5 errors as fast as possible. In this project we will consider the following question:

How can we perform decoding for a 5-error-correcting BCH code as fast as possible?

A strategy to answer this question is the following: To speed up finding the error-locator polynomial, one can precompute a so-called generic error-locator polynomial, i.e. one can find an expression containing the syndromes as additional variables, such that for each actual value of the syndromes one obtains the correct error-locator polynomial from the generic error-locator polynomial by substituting the syndrome values.

Such expressions are too lengthy in general, but if the number of errors one needs to correct is modest this is more feasible.. To find the roots of the polynomial of degree 5, the strategy is to use suitably chosen transformations to bring any given polynomial in a standard form. Tricks similar (but algebraically more interesting) to completing the square are generalized and used for this purpose. Afterwards a strategy will be developed to solve the remaining standard cases, among others using table lookup for special cases.

Keywords: factorization, prime numbers, number theory

Prerequisites: 01018: Discrete Mathematics 2

Description coming soon.

Mathematics of Origami

Keywords: origami, galois theory, algorithms, group theory, graph theory

Prerequisites: 01018: Discrete Mathematics 2

Origami is the art of paper folding: starting with a square piece of paper, one can make wondrous shapes simply by folding the paper. Many intriguing mathematical questions naturally present themselves. Here are a few examples, but searches on Google reveal many more, and there are even conferences devoted to the topic.

• It is common to use only exact folding, i.e. where e.g. a fold is defined by a know point be sent on top of another known point. A point is “known” when it is the intersection of two exact folds that were made. A natural question in
  this context is therefore:

  What set of points can become known by a finite sequence of exact folds?

  This question is similar to classical geometric questions such as “Using only compass and straight-edge, can you double the square or trisect an angle?”. To answer it, one delves into beautiful algebraic theory initiated by Galois.

• If one completely unfolds an origami shape, the folds left on the paper is called a crease pattern. A natural question is therefore, given a crease pattern, is it possible to fold along exactly those lines and end up with a flat figure? If so, what sequence of folds should one perform? These questions turn out to be computationally hard! In fact, it is often posed to Origami enthusiast as interesting puzzles. A necessary, known condition for flat-foldability, however, is e.g. Kawasaki’s Theorem. Inquiries such as these lead one into combinatorics, discrete algorithms and perhaps meta-heuristics.
• Modular Origami is the practice of using many simple units, each folded from one pieces of paper, together to form a large, complex shape, e.g. stars and bucky balls. A classical example is the Sonobe star made of 30 pieces of paper. Here, 20 small triangular pyramids are arranged on an icosahedron to make the star. Each pyramid is composed of three halves of units.Classical geometric–algebraic questions arise in new light in this setting: if I take 3 colours, and fold 10 units of each colour, is it possible to assemple the Sonobe star such that each pyramid has exactly those three colours? The answer is yes, but it is tricky to accomplish. One can therefore ask how many solutions there are, or perhaps which one is *best* (e.g. most symmetrical). These questions are group theoretic in nature.