Open in CoCalc

Primitiva rötter och diskreta logaritmer

Låt aa och nn vara positiva heltal, där gcd(a,n)=1\gcd(a, n) = 1. Det minsta positiva heltal kk sådant att ak1(modn)a^k \equiv 1 \pmod{n} kallas för ordningen av aa modulo nn.
n = 57 a = Mod(14, n) k = multiplicative_order(a) k
18
Alltså är 14 ordningen för 14 modulo 57.
Om ordningen av aa modulo nn är lika med ϕ(n)\phi(n), så säges aa vara en primitiv rot modulo nn. En primitiv rot modulo nn 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 gg som ett element i Z311\mathbb{Z}_{311}.
Z311 = Zmod(n) g = Z311(g)
Den diskreta logaritmen k=Lg(x)k = L_g(x) modulo nn är det minsta icke-negativa heltal kk sådant att gk=xg^k = x i Zn\mathbb{Z}_n, där gg är en primitiv rot modulo nn. Vad ska g=17g = 17 upphöjas med för att vi ska få 55 modulo 311311?
discrete_log(5, g)
196
Alltså är L17(5)=196L_{17}(5) = 196, d.v.s. 171965(mod311)17^{196} \equiv 5 \pmod{311}.