Bachelor, prosjekt- og masteroppgaver i algebra/anvendt algebra/kryptografi

Her er en liste med noen eksempler på mulige prosjekt- og master-oppgaver. Du oppfordres til å ta kontakt med oss i algebragruppen hvis du vurderer en bachelor-, prosjekt- eller masteroppgave i algebra. Det er mulig å bytte veileder og/eller prosjekt innen algebragruppen etter påmeldingsfristen i januar/februar for studenter i industriell matematikk.

Se hjemmesiden for mer informasjon om algebragruppen.

• Petter A. Bergh
• Aslak B. Buan
• Jiaxin Pan (now in Kassel, Germany)
• Kristian Gjøsteen
• Steffen Oppermann
• Sverre O. Smalø
• Øyvind Solberg
• Sondre Kvamme

Midlertidige ansatte kan også være mulige veiledere:

• Torkil Utvik Stai

Bacheloroppgaver innen algebra vil normalt bygge på et eller flere av kursene MA1301 Tallteori, MA1201 Lineær algebra og geometri, MA1202 Lineær algebra med anvendelser og MA2201 Algebra/TMA4150 Algebra og tallteori og MA3201 Ringer og Moduler.

Prosjektoppgaver innen anvendt algebra vil normalt bygge på et eller flere av kursene MA2201 Algebra/TMA4150 Algebra og tallteori og TMA4160 Kryptografi.

Prosjektoppgaver innen algebra vil normalt bygge på et eller flere av kursene MA1301 Tallteori, MA1201 Lineær algebra og geometri, MA1202 Lineær algebra med anvendelser, MA2201 Algebra/TMA4150 Algebra og tallteori og MA3201 Ringer og Moduler.

Prosjektoppgaver innen anvendt algebra vil normalt bygge på et eller flere av kursene MA2201 Algebra/TMA4150 Algebra og tallteori, TMA4160 Kryptografi og TMA4185 Kodeteori. For kryptografioppgaver kan det lønne seg å følge et seminar i videregående kryptografi.

Masteroppgaver innen algebra vil normalt bygge på et eller flere av kursene MA3201 Ringer og Moduler, MA3202 Galoisteori, MA3203 Ringteori og MA3204 Homologisk algebra.

Masteroppgaver innen anvendt algebra vil normalt bygge på et eller flere av kursene TMA4160 Kryptografi og TMA4162 Beregningsorientert algebra, og det vil være nyttig med MA3201 Ringer og Moduler og/eller MA3202 Galoisteori. For kryptografioppgaver kan det lønne seg å følge et seminar i videregående kryptografi, dersom et slikt arrangeres.

• Algebraisk tallteori (Bergh)
• Komplette snitt (Bergh)
• 4-underromsproblemet] (Smalø)
• Grøbnerbasis (Solberg)
• Triangulated categories (Bergh / Oppermann / Stai)
• General representations (Oppermann)
• Tree modules for quivers (Oppermann)
• Exceptional sequences (Buan)
• Gentle algebras (Buan)
• Exact categories (Kvamme / Stai)
• Advanced group theory (Kvamme / Stai)

• Tight cryptography (Pan/Gjøsteen)
• Post-quantum cryptanalysis (Gjøsteen)
• Key exchange (Pan/Gjøsteen)
• Quantum computing and cryptography (Gjøsteen)
• Cryptographic voting systems (Gjøsteen)
• Provable security of symmetric cryptography (Pan)
• Post-quantum cryptography (Pan/Gjøsteen)
• Functional encryption (Pan)
• Formal security analysis for real-world cryptography (Pan/Gjøsteen)
• Automatic verification of mathematical proofs (Gjøsteen)
• Grøbnerbasis og kryptoanalyse (Buan/Solberg)
• Koder basert på algebraisk geometri (Gjøsteen)
• Koder som idealer i grupperinger og andre ringer (Solberg)
• Polar codes (Gjøsteen, with Kimmo Kansanen at IES)

Algebraisk tallteori er den delen av matematikken hvor man benytter moderne algebraiske teknikker til å studere problemer og utvikle teori som har opphav innen tallteori. Man studerer typisk de algebraiske egenskapene til ringen av algebraiske heltall i en algebraisk tallkropp (en endelig kroppsutvidelse av de rasjonale tallene).

Man finner mange mulige oppgavetemaer innen dette feltet, for eksempel: Tate-kohomologi, ringteoretiske egenskaper ved heltallsringer, Fermats Siste Teorem for regulære primtallseksponenter.

Komplette snitt er en type ringer som stammer fra algebraisk geometri, som koordinatringer til visse pene affine varieteter. Studien av disse kommutative ringene utgjør nå et eget felt, og dette er i dag en meget aktiv gren av kommutativ ringteori. Målet med dette prosjektet er å forstå disse ringene, ved hjelp av relevant litteratur.

La W være et vektorrom og V_1, V_2 og V_3 være tre underrom. Systemet (W; V_1,V_2,V_3) blir kalt dekomponerbart dersom det finnes ikketrivielle underrom W' og W'' i W slik at

W = W' (direkte sum) W'',

og V_i = (W' (snitt) V_i) (direkte sum) (W'' (snitt) V_i)

for i=1,2,3. Det er ikke så vanskelig å vise at dersom systemet (W;V_1,V_2,V_3) ikke dekomponerer, så er dimensjonen til W mindre enn eller lik 2, og at det essensielt bare finnes 9 slike system som ikke dekomponerer.

4-underromsproblemet gikk ut på å beskrive de systemene som ikke dekomponerer når en øker antall underrom fra 3 til 4 som i beskrivelsen ovenfor. Prosjektet går ut på å gå gjennom en løsning av 4-underromsproblemet og relaterte lineæralgebraiske problemer.

Prosjektet passer for opptil tre-fire studenter.

Litteratur: L. A. Nazarova og A. V. Roiter, Representations of Partially Ordered Sets, J. Sov. Math. 3 (1975) 585 - 606.

Forutsetninger: Det er en fordel å ha tatt TMA4150 Algebra og Tallteori/MA2201 Algebra og MA 3201 Ringer og moduler eller tilsvarende.

I 1960-årene ble nye algoritmer for å manipulere polynomer og system av likninger av polynomer oppdaget av Buchberger og Hironaka. Med raskere datamaskiner kunne implementasjoner av disse algoritmene brukes på en effektiv måte. Dette har hatt stor innvirkning på forskningen i ren og anvendt matematikk. Teorien er også blitt utvidet til ikke-kommutative ``polynomringer'', såkalte veialgebraer.

Med dette som utgangspunkt er det forskjellige muligheter for prosjekter om Grøbnerbasis:

• Sette seg inn i teorien bak Grøbner-basis for polynomringer og muligens i tillegg se på anvendelser innen automatisk geometrisk bevisføring, anvendelser på roboter, etc. Eventuelt gå videre til generaliseringer til ikke-kommutative ringer. Prosjektet forutsetter kurset MA3201 Ringer og Moduler. Referanse: Cox, D., Little, J., O'Shea, D., Ideals, varieties and algorithms, UTM, Springer, 1992.
• Sette seg inn i teorien bak Grøbner-basis for ikke-kommutative ringer og bruk av denne for veialgebraer over en kropp. Videre spesialisering kan være beregninger av forskjellige invarianter av moduler over veialgebraer. Som en del av prosjektet kan programmeringsoppgaver inngå (programpakken som brukes er QPA = Quivers and Path Algebras, utvikles i Trondheim og USA, se hjemmeside til QPA for mer informasjon). Prosjektet forutsetter kurset MA3201 Ringer og Moduler, og det kan være en fordel å ha MA3203 Ringteori eller lese deler av dette som en del av prosjektet.

Flere studenter kan godt jobbe sammen på et prosjekt.

Triangulated categories are a way to reduce to the essence the homological algebra. They were first applied in algebraic geometry and algebraic topology, but have now become an indispensable tool also in studying homological aspects of representation theory.

The aim of a project could be to understand the axioms defining a triangulated category, and to verify and apply them on a class of examples.

Having participated in the course MA3204 Homological algebra would be an advantage.

The aim of this project is to understand representation of quivers, not by focusing on indecomposables directly, but rather by asking what can be said "generically" about representations of a given dimension vector. In particular it will be possible to ask about a "generic" decomposition of representations into indecomposables.

The tasks involved in this project would be to understand, for instance with the help of Schofield, General representations of quivers (Proc. London Math. Soc. (3), no. 65, 1992) what "generic" means precisely, and why it is possible to make statements about generic representations. Afterwords this would be applied to examples.

Having seen quiver representations would be an advantage for this project.

Understanding all (indecomposable) representations of a given quiver is a hopeless task if the quiver is not very small (this phenomenon is called wildness). To still get some impression it is natural to restrict ones focus to a more restrictive class of indecomposable representations.

One possible approach is to study so-called tree modules, which are representations with a particularly nice combinatorial description. They have been studied by Ringel, in "Indecomposable representations of the Kronecker quivers" for generalized Kronecker quivers.

The aim of this project is to understand the concept of tree modules, and Ringel's result for the case of generalized Kronecker quivers. Then it would be interesting to see if similar results hold for other wild quivers.

Having seen quiver representations would be an advantage for this project.

Exceptional sequences are certain sequences of representations (modules) that have many interesting combinatorial properties and applications. The theory originated from algebraic geometry. A project in this direction would deal either with categories of modules or with triangulated categories, and could focus either on combinatorial properties of such sequences or more on homological aspects of the theory.

A project could be offered both on master and on bachelor level. For a project on master level, the courses MA3203 and MA3204 are recommended as background.

Gentle algebras have module categories that are well understood, and the modules have a particularly nice combinatorial description. The also have good homological properties, in particular they are so-called Gorenstein algebras. A project could deal with combinatorial descriptions of the module category or of the derived category, but also with more homological aspects.

A project about gentle algebras could be offered both on master and on bachelor level. For a project on master level, the course MA3203 is essential, and in addition MA3204 is recommended as background.

Exact categories in the sense of Quillen are additive categories equipped with a class of kernel-cokernel pairs with nice properties. They occur in many places in mathematics, from functional analysis to Lie theory to representation theory of finite-dimensional algebras. It turns out that most results in homological algebra can be extended from abelian to exact categories.

This project would involve learning the definition of exact categories, to show homological and representation-theoretic properties about them, and to study certain classes of examples in detail. Furthermore, it could also involve studying the lattice of all exact structures on an additive category, a topic which has recently attracted a lot of research.

For a project on master level, it is recommended to have taken the courses MA3203 and MA3204.

The aim of this project is to study results from group theory that are not included in TMA4150 Algebra, but should be within reach after taking this course. There are many candidate problems for such a project, for instance Burnside's so-called pq theorem or the description of the finite subgroups of the (special) orthogonal group in terms of Platonic solids.

If you are interested in a thesis in cryptography, it is advised to take the TMA4160 Cryptography before starting the bachelor or master thesis. For master theses, it is beneficial if you have taken the Advanced Cryptography seminar. You may enjoy your journey of working on a thesis more if you have a general interest in theoretical and practical issues related to cryptography, IT security, and computer science.

A thesis topic is often built on a scientific paper (in English) at leading conferences, such as Crypto, Eurocrypt, Asiacrypt, etc.. The minimum goal of a thesis is to understand the paper down to the smallest detail and express it in your own words. In many cases, smaller or larger problems arrive and then it will continue to solve these problems.

Theses in more general applied algebra topics are also possible.

The following are some suggested thesis topics, but there are many other possibilities.

So-called provable security aims to show a relation between the security of a cryptosystem and one or more computational problems, by turning attackers against the cryptosystem into solvers of problems. The difference in efficiency between the attackers and the solvers is called the tightness gap. A large tightness gap results in inefficient cryptosystems. This thesis topic is about the study of techniques for building cryptosystems (e.g. signature schemes, public key cryptosystems and key exchange schemes) with tighter security proofs and greater overall efficiency, or studying obstacles to tight cryptography.

Quantum computers - if they ever become sufficiently large and reliable - can factor integers and compute discrete logarithms quickly. This breaks most cryptography in practical use today. This means that we are interested in computational problems that are hard for quantum computers to solve, and are usable for cryptography. The currently best method to decide if a problem is hard is to try to find efficient algorithms for solving the problem. This thesis topic is about algorithms for solving the problems underlying post-quantum cryptography, such as problems related to lattices and algebraic number theory, multivariate quadratic equations and Gröbner basis, coding theory, and isogenies and algebraic geometry.

Key exchange is one of the fundamental tasks in cryptography. The study of key exchange protocols is one of the great topics in cryptography, and has given us many break-throughs. This thesis topic is about modern key exchange protocols, either quantum-safe key exchange, password-based key exchange, key exchange under various novel forms of trust, or key exchange over various forms of unreliable networks. Or various combinations.

Shor’s algorithm is an effective method for factoring integers, given a sufficiently large and reliable quantum computer. There are many other quantum algorithms that are relevant for cryptography. This thesis topic is about quantum computation in general, and quantum algorithms related to cryptography in particular.

Cryptographic voting systems either promise greater assurance for elections (such as universal verifiability, the ability of anyone to verify that their vote was counted correctly), or new functionality (the ability to vote from home via the internet). The study of cryptographic voting systems can be considered a subtopic of cryptographic protocol theory, and includes topics such as verifiability of mathematical proofs, zero knowledge proofs and cryptographic protocols involving humans. This thesis topic is about the study of various aspects of cryptographic voting systems.

It is very hard to verify that a large and complicated mathematical argument is actually correct. But mathematical arguments can themselves be considered as mathematical objects, the study of which is called mathematical logic. Arguments as mathematical objects can be written out in a formal language, and such arguments are trivial to verify, though very labour-intensive. This is a perfect job for computers. In recent years this has been an interesting and fruitful branch of mathematics.

In cryptography we use mathematical arguments to demonstrate that our cryptosystems are secure (under plausible conjectures). The correctness of these mathematical arguments is critical, because any flaw in an argument may hide a possible attack on the cryptosystem. This thesis topic is about formalising mathematical arguments used in cryptography so that they can be verified by software such as Easycrypt.

Første del (høstprosjektet) vil overlappe med Grøbner-basis prosjektet til Solberg. Andre del vil gå ut på å sette seg inn i hvordan Grøbner basis er forsøkt utnyttet til kryptoanalyse.

Referanse: Som for Grøbner-basis prosjektet, samt Neil Koblitz: Algebraic aspects of cryptography, Springer ISBN: 3-540-63446-0

Forutsetninger: MA3201 Ringer og Moduler, MA3202 Galoisteori, TMA4160 Kryptografi. Kurset MA8202 Kommutativ algebra bør tas samtidlig som høstprosjektet.

Reed-Solomon-koden lager kodeord ved å evaluere polynomer av grad høyst k-1 i n>k punkter. Disse kan generaliseres blant annet til algebraiske kurver, der man evaluerer funksjoner på en kurve i et antall punkter på kurven. Oppgaven består i å studere hvordan koding og dekoding gjøres for disse generaliserte kodene.

Det er nødvendig å ta kurset TMA4185 Kodeteori, og det er en fordel å ta fagene MA3201 Ringer og moduler og MA3202 Galoisteori.

Overføring av data og annen digital kommunikasjon bygger ofte på feilkorrigerende koder. Et eksempel er en CD-spiller. Dette prosjektet vil i første omgang ta for seg klassen grupperinger, og se hvordan denne er brukt i forbindelse med feilkorrigerende koder.

Gitt en endelig gruppe G og en kropp k kan vi danne oss grupperingen kG, som er vektorrommet over kroppen k med alle gruppeelementene i G som basis. Multiplikasjonen i kG er gitt ved gruppeoperasjonen i G. Dette prosjektet har som mål å sette seg inn i noe av teorien for grupperinger over en kropp, og forstå hvordan idealer i disse ringene brukes for å realisere kjente koder. Også andre ringer enn grupperinger er blitt brukt for å lage koder. Disse kan utgjøre videre tema for prosjekter/oppgaver.

Referanser:

• Bernhardt, Frank; Landrock, Peter; Manz, Olaf: The extended Golay codes considered as ideals, J. Combin. Theory Ser. A 55 (1990), no. 2, 235–246.
• Landrock, Peter; Manz, Olaf, Classical codes as ideals in group algebras, Des. Codes Cryptogr. 2 (1992), no. 3, 273-285.

Prosjektet forutsetter kursene MA3201 Ringer og Moduler og TMA4185 Kodeteori. Flere studenter kan godt jobbe sammen på et prosjekt.

Polar codes are the first forward error correcting code family that is provably capacity achieving, and has provable encoding and decoding complexity. Lately, they have also been included in the 5G new radio (NR) air interface standard [1]. While the early concepts of polar codes mainly worked well in large block lengths, the NR design includes the possibility to use polar codes down to block lengths of 12 information bits. This makes the code a good candidate for IoT applications, where short block lengths are desirable for energy savings, offering potentially better performance than convolutional codes. The 5G NR polar code design [1] offers large flexibility in choice of code rate and block size.

The work includes:

• Literature search of polar codes and decoding techniques
• Determine appropriate code & suitable decoding technique (e.g. successive cancellation and list decode)
• Implement in software and compare to convolutional codes

[1] https://arxiv.org/abs/1804.04389