Primitivni korijeni

diplomski rad

• Naslov (engleski): Primitive roots
• Autor: Marija Milković
• Mentor: Zrinka Franušić (mentor)
• Član povjerenstva: Zrinka Franušić (predsjednik povjerenstva)
• Član povjerenstva: Aleksandra Čižmešija (član povjerenstva)
• Član povjerenstva: Matija Bašić (član povjerenstva)
• Član povjerenstva: Pavle Pandžić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2022-03-03, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Prema Eulerovom teoremu za relativno proste brojeve \(a\in \mathbb{Z}\)i \(n\in \mathbb{N}\) vrijedi \(a^{\varphi(n)}\equiv 1 \pmod n\). Najmanji prirodni broj \(d\) sa svojstvom da je \(a^d\equiv1 \pmod n\) zove se \(red\) od \(a\) modulo \(n\). Ako je \(d=\varphi(n) \), \(a\) se naziva primitivni korijen modulo \(n\), a skup \(\{a^1, a^2, \ldots, a^{\varphi(n)}\} \) čini reducirani sustav ostataka modulo \(n\). To povlači da je \(\mathbb{Z}_n^*\) ciklička grupa, pri čemu je \(a\) generator te grupe. Ne postoji primitivni korijen modulo \(n\) za svaki prirodan broj \(n\). Pokazuje se da primitivni korijen modulo \(n\) postoji ako i samo ako je \(n=2, 4, p^k\) ili \(n=2p^k\), pri čemu je \( p\) prost broj i \(k\in \mathbb{N}\). S obzirom da \(\{a^0, a^1, \ldots, a^{\varphi(n)-2}\}\) čini reducirani sustav ostataka modulo \(n\), to nam omogućava definiciju indeksa (diskretnog logaritma) od a u odnosu na primitivni korijen modulo \(n\). Ako je \(y\in\mathbb{Z}\) relativno prost s \(n\), tada je index od \(y\) s obzirom na a modulo \(n\) jednak \(x\in \{0, 1, \ldots, \varphi(n)-1\}\) za koji je \(y\equiv a^x\pmod n\). Indeksi imaju svojstva koja su slična onima za logaritme pri čemu se jednakosti zamjenjuju kongruencijama modulo \(\varphi(n) \). U radu su opisane i neke primjene primitivnih korijena i diskretnog logaritma kao što su rješavanje polinomijalnih i eksponencijalnih kongruencija, testovi prostosti i protokol za razmjenu ključeva koji se koristi u kriptografiji..

Sažetak (engleski)

According to Euler’s theorem, for relatively prime numbers \(a\in \mathbb{Z}\) and \(n\in \mathbb{N}\), it holds that \(a^{\varphi(n)}\equiv 1 \pmod n\). The smallest natural number \(d\) with the property \(a^d\equiv1 \pmod n\) is called the order of \(a\) modulo \(n\). If \(d=\varphi(n) \), then \(a\) is called a primitive root modulo \(n\) and the set \(\{a^1, a^2, \ldots, a^{\varphi(n)}\} \) forms a reduced system of residues modulo \(n\). This implies that \(\mathbb{Z}_n^*\) is a cyclic multiplicative group, where the primitive root \(a\) is its generator. A primitive root modulo \(n\) does not exist for every natural number \(n\). It is shown that a primitive root modulo \(n\) exists if and only if \(n=2, 4, p^k\) or \(n=2p^k\), where \( p\) is a prime number and \(k\in \mathbb{N}\). Considering that \(\{a^0, a^1, \ldots, a^{\varphi(n)-2}\}\) is a reduced system of residues modulo \(n\), it leads to a definition of the index (discrete logarithm). If \(y\in\mathbb{Z}\) is relatively prime to \(n\), then the index of \(y\) to the base a modulo \(n\) equals \(x\in \{0, 1, \ldots, \varphi(n)-1\}\) such that \(y\equiv a^x\pmod n\). Indices have many properties similar those of logarithms where equalities are replaced with congruences modulo \(\varphi(n) \). In this graduate thesis, some applications of primitive roots and discrete logarithms are described, such as solving polynomial and exponential congruences, primality testing, and the key exchange protocol which is used in cryptography.

• Ključne riječi: Eulerov teorem; red od a modulo n; ciklička grupa; diskretni logaritam; polinomijalne kongruencije; eksponencijalne kongruencije; kriptografija
• Ključne riječi (engleski): Euler's theorem; order of a modulo n; cyclic multiplicative group; discrete logarithm; polynomial congruences; exponential congruences; cryptography
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:024300
• Studijski program: Naziv: Matematika; smjerovi: nastavnički; Smjer: nastavnički; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra edukacije matematike (mag. educ. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2022-03-29 12:04:28