Projects

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: number theory, prime numbers, algorithms

Prerequisites: (01018: Discrete Mathematics 2)

How do you check whether, say 73 is prime? You could try dividing with all primes greater than 1 and up to \(\sqrt{73} < 9\) and verify that none of them divides. This has the advantage of helping you factor 73 as well as answering the primality question. It has the disadvantage that if 73 was a much, much larger number, you would never finish the exciting task of testing potential divisors.

To the best of our current knowledge, it is much easier to check for primality, than it is to actually factor a number. Case in point: my computer algebra system answered within 1 second that \(10^{23423}+1\) is not prime, but it is still busy attempting to find a factorization.

This project is about those clever algorithms for primality testing. The famous, and shockingly simple, Rabin–Miller test is a randomized algorithm which can only prove non-primality: it answers either “definitely not prime” or “perhaps prime”. It works well for almost all non-primes, though, so it can usually be quite well trusted. The project might also touch upon the landmark paper of Agrawal et. al that can prove both primality and non-primality in polynomial time.

The project would involve implementing one or more of the investigated methods in a computer algebra system or a favourite programming language.

Keywords: polynomials, finite fields, implementation

Prerequisites: (01018: Discrete Mathematics 2)

“Interpolation” is when one approximates some unknown function by seeing only its evaluations at certain input. It’s a central concept in countless applications.

If the unknown function is a polynomial then it is not too difficult to see that one can perfectly reconstruct the polynomial using $n+1$ evaluations, where $n$ is the degree of the polynomial. However, what can be done if the polynomial has a huge degree, but only very few non-zero coefficients? The answer here is much less straightforward, and very surprising: if the polynomial has $t$ non-zero coefficients, the $2t+1$ evaluations is all it takes, no matter what the degree of the polynomial is! Even more bizarre, this procedure can be efficiently carried out using the Euclidean algorithm for computing the greatest common divisor.

In this project you will learn about this “sparse interpolation”, and you will investigate and prove how the Euclidean algorithm can solve the problem. You will also implement the algorithm. If time permits, you can investigate other algorithms for solving the problem, or you can consider what one can do if one or more of the evaluations may be wrong!

This project can be scaled to fit one or multiple students.

Keywords: coding theory, decoding, polynomials

Prerequisites: 01018: Discrete Mathematics 2, (01405: Algebraic Coding Theory)

Locally decodable codes are a type of error-correcting code for encoding and storing information in a reliable way and such that you can “locally” get the information back: you can retrieve just a single symbol of the original information at a time by looking at only very few symbols of the encoded data, and those symbols can be chosen basically randomly! Even more, we still have error-correction so even if some of the retrieved symbols were wrong, we still correctly obtain the information symbol we were looking for.

These codes are useful for privacy services in distributed storage, and have also had a huge theoretical impact in proof theory as enablers of probabilistically checkable proofs.

The constructions are algebraic and rely on evaluation and interpolation of multivariate polynomials over finite fields. The proofs that they exhibit “random” local reconstruction draw on algebraic geometry.

The project could be purely theoretic, by studying the basic constructions and more recent proposals in research papers, or it can be made more practical by implementing one or more of the schemes.

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.

Keywords: continued fractions, rational approximations

Prerequisites: None

The current rule for leap years is that year \(N\) is a leap year if 4 divides \(N\), except if 100 but not 400 divides \(N\). What is the rationale behind this rule? Could a better, more precise rule be made up?

The secret behind solving this problem is to approximate a real number, here the exact number of days it takes Earth to orbit the sun, by a fraction with a relatively small denominator. This is called rational approximation, and can be done by using continued fractions, which is, surprisingly, computable by the Euclidean algorithm.

A more complicated example comes from the “tempered” musical scale that was introduced in the 17th century. To fit the ear, tone frequencies should be related by exact fractions with small denominators. But to allow playing in multiple scales without retuning the instrument, one should use the same ratio between all consecutive notes. The latter requirement means that certain tonal intervals will be slightly off, and might sound bad to the trained ear. The 12 tones of our tonal system was chosen solely to minimise this error! But could we get a better system by choosing 10, 15 or 19 notes? Solving this problem requires simultaneous approximation of multiple real numbers by fractions all having the same denominator!

In this project you will be investigating the mathematics behind continued fractions and rational approximation, and you will derive a better leap year system than what we currently have. If time permits, you can investigate the tonal system problem.

This problem can be scaled to fit one or multiple students.

Keywords: modules, linear algebra, normal forms

Prerequisites: (01018: Discrete Mathematics 2)

Description coming soon

Keywords:

Prerequisites: (01018: Discrete Mathematics 2)

Description coming soon