Komplette snitt (Bergh)

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.

4-underromsproblemet (Smalø)

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'',

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.

Forutsetninger: Det er en fordel å ha tatt TMA 4150 eller MA 2201 og MA 3201 eller tilsvarende.

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

Grøbnerbasis (Solberg)

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 polynom-ringer 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 i 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å. 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.

Forskjellige temaer i algebra (Bergh/Smalø/Solberg)

En rekke andre oppgaver i algebra er mulig. Disse vil normalt bygge på et eller flere av kursene Ringer og Moduler, Galoisteori og Ringteori. Ta kontakt med en av de fast ansatte i algebragruppen for nærmere avtale.

Anvendt algebra-oppgaver

Koder basert på algebraisk geometri (Gjøsteen)

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.

Anonymitet i kryptografiske protokoller (Gjøsteen)

Mesteparten av dagens digitale infrastruktur, f.eks. for telekommunikasjon og betaling, er konstruert på en slik måte at eieren av infrastrukturen samler opp svært mye informasjon om brukerne av infrastrukturen. Det er mange eksempler på at slik informasjon kommer på avveie eller blir misbrukt, enten av betrodde ansatte eller av eieren av infrastrukturen.

Oppgaven vil dreie seg om å studere hvordan man kan lage kryptografiske protokoller som beskytter brukerne og bedrer personvernet.

Det er nødvendig å ha tatt kurset TMA4160 Kryptografi.

Tallkroppsålden (Gjøsteen)

Tallkroppsålden (number field sieve) er den raskeste metoden vi kjenner i dag for å faktorisere store heltall. Tilsvarende metoder kan brukes for å finne diskrete logaritmer i endelige kropper.

I visse kryptografiske angrep kan man få ekstra informasjon som kanskje kan gjøre tallkroppsolden raskere. Oppgaven vil bestå i å sette seg inn i tallkroppsålden og hvordan denne kan gjøres raskere ved hjelp av ekstra informasjon, samt forsøke å tilpasse dette til nye kryptografiske angrep.

Det er nødvendig å ta kursene MA3201 Ringer og moduler og MA3202 Galoisteori. Det er nyttig å ta kurset TMA4160 Kryptografi.

Elliptiske kurver (Gjøsteen)

Når man skal bruke elliptiske kurver i kryptografi må man velge en endelig kropp og en kurve definert over denne kroppen. Oppgaven vil se på hvordan man velger kropper og kurver som er egnet for kryptografi, både med tanke på sikkerhet og effektiv implementasjon.

Turbo-koder (Gjøsteen)

Når man kobler sammen to koder får man ikke nødvendigvis samme effekt som én enkelt kode med dobbel lengde. Hvis den innerste koden gjør en dekodingsfeil kan dette introdusere nye feil som får den ytre koden til også å gjøre en dekodingsfeil. En måte å begrense dette problemet på er å stokke om på symbolene mellom indre og ytre kode. Dette kan spre feilene som den første dekodingen introduserer og dermed gjøre det mulig for den ytre koden å rette alle sammen. En måte å forbedre ytterligere er det såkalte "turbo-prinsippet", der man gjør flere runder med dekoding for utnytte indre og ytre kode maksimalt.

Oppgaven vil bestå i å studere hvordan turbo-koder bygges opp og hvordan dekoding gjøres.

Det er nødvendig å ta kurset TMA4185 Kodeteori.

Kodeteori-prosjekt (Smalø)

For informasjon om dette prosjektet ta kontakt med Sverre, sverresm (at) math ntnu no.

Koder som idealer i grupperinger og andre ringer (Solberg)

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 gruppe-elementene i G som basis. Multiplikasjonen i kG er gitt ved gruppe-operasjonen 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.

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

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.

Grøbner-basis og krypto-analyse (Gjøsteen/Solberg)

Første del (høst-prosjektet) 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 Krypto-analyse.

Forutsetninger: Ringer og Moduler, Galois-teori, Kryptografi. Kurset Kommutativ algebra bør taes samtidlig som høst-prosjektet.

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

Oppgaver i samarbeid med Inst. for telematikk (Gjøsteen)

Om noen er interessert i prosjekt/diplom i samarbeid med telematikk, ta gjerne kontakt med Kristian.

Forutsetningene for en slik oppgave vil vanligvis være kursene Algebra og Tallteori, Kryptografi og Informasjons-sikkerhet (ved ITEM).

Andre oppgaver i kryptografi (Gjøsteen)

Det er mange mulige temaer innen matematisk kryptografi, slik som latticealgorimer, anonymitet i kryptografiske protokoller, osv. Ta kontakt for nærmere informasjon.

Det vil stort sett være en forutsetning med kurset TMA4160 Kryptografi, og informasjonssikkerhetskurset til ITEM kan også være nyttig.