Primitiva_rötter_och_diskreta_logaritmer.sagews

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}$.