 SharedSage genom exempel / Primitiva_rötter_och_diskreta_logaritmer.sagewsOpen in CoCalc
Author: Robert Nyqvist

# Primitiva rötter och diskreta logaritmer

Låt $a$ och $n$ vara positiva heltal, där $\gcd(a, n) = 1$. Det minsta positiva heltal $k$ sådant att $a^k \equiv 1 \pmod{n}$ kallas för ordningen av $a$ modulo $n$.
n = 57
a = Mod(14, n)
k = multiplicative_order(a)
k

18
Alltså är 14 ordningen för 14 modulo 57.
Om ordningen av $a$ modulo $n$ är lika med $\phi(n)$, så säges $a$ vara en primitiv rot modulo $n$. En primitiv rot modulo $n$ fås med primitive_root under förutsättning att en sådan existerar.
n = 311
g = primitive_root(n)
g

17
primitive_root(12)

Error in lines 1-1 Traceback (most recent call last): File "/projects/sage/sage-7.6/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 995, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "/projects/sage/sage-7.6/local/lib/python2.7/site-packages/sage/arith/misc.py", line 3728, in primitive_root raise ValueError("no primitive root") ValueError: no primitive root
I fortsättningen betraktar vi $g$ som ett element i $\mathbb{Z}_{311}$.
Z311 = Zmod(n)
g = Z311(g)

Den diskreta logaritmen $k = L_g(x)$ modulo $n$ är det minsta icke-negativa heltal $k$ sådant att $g^k = x$ i $\mathbb{Z}_n$, där $g$ är en primitiv rot modulo $n$. Vad ska $g = 17$ upphöjas med för att vi ska få $5$ modulo $311$?
discrete_log(5, g)

196
Alltså är $L_{17}(5) = 196$, d.v.s. $17^{196} \equiv 5 \pmod{311}$.