Primitive roots
| Autor: | Milković, Marija |
|---|---|
| Přispěvatelé: | Franušić, Zrinka |
| Jazyk: | chorvatština |
| Rok vydání: | 2022 |
| Předmět: |
red od a modulo n
cyclic multiplicative group cryptography discrete logarithm polinomijalne kongruencije order of a modulo n exponential congruences ciklička grupa Euler's theorem eksponencijalne kongruencije diskretni logaritam PRIRODNE ZNANOSTI. Matematika Eulerov teorem polynomial congruences NATURAL SCIENCES. Mathematics kriptografija |
| Popis: | 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.. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|