Questions tagged [primitive-roots]

For questions about primitive roots in modular arithmetic, index calculus, and applications in cryptography. For questions about primitive roots of unity, use the (roots-of-unity) tag instead.

394 questions
61 views

How to show the $p$ minus primitive root is also a primitive root for $p \equiv1 \pmod {4}$

Let $p$ be a prime such that $p \equiv1 \pmod {4},$ and let $r$ be a primitive root mod $p$. I wonder how to show that $p-r$ is a primitive root mod $p.$
44 views

Question related to N-th cyclotomic polynomial, principal N-th root of unity and residue class of X

I am struggling to understand a couple of statements in a cryptography-related paper. I think I lack some maths background. Can you help me understand it ? Here are the statements: We consider the ...
439 views

88 views

200 views

Primitive element and choice of irreducible polynomial

It is known that every finite field of the same order $p^k$ are isomorphic. So, $F_p[x]/\langle q(x)\rangle$ leads to the same field for any choice of irriducible k-degree $q(x)$ over $F_p[x]$. But, ...
175 views

Get primitive root of 1024 bit prime number in sage

How to find the primitive root of a 1024 bit prime number in sage? primitive_root(p) takes forever to calculate.
59 views

Primitive roots in integer rings of number fields with class number 1

In number fields that are PIDs, i.e., with class number 1, we have unique factorization of integral elements into primes, much like we do in $\Bbb Z$. Suppose $\pi$ is such a prime element in $R$, the ...
36 views

54 views

Prove that $\gamma^{\frac{q-1}{2}}=-1$ in $\mathbb{F}_q$ when $q$ is an odd prime power and $\mathbb{F}_q^*=<\gamma >$.

I have written a proof for this, however I think there may be a simpler way to go about it and am curious for any suggestions. Also I don't fully see where my proof would fail if $q$ was even (other ...
66 views

$f(X)=X^{16}-X \in \mathbb F_2 [X]$ ,order of primitive roots, polynomial of minimal degree

Given is the polynomial $f(X)=X^{16}-X \in \mathbb F_2 [X]$. It factorizes into $f(X)=X(X+1)q(X)$, where $q(X)=X^{14}+X^{13}+\dots +X+1$. Now, let $\alpha$ be a primitive root of $\mathbb F_{16}$ ...
70 views

Checking understanding of Order, Primitive Roots

I dont seem to understand how primitive roots work. I've outlined what I think, if anyone can tell me what I'm misunderstanding I'd really appreciate it! To calculate the order of 5 modulo 18, our ...
31 views

If g is a primitive root modulo $N$, then g is a primitive root modulo $D$, where $D|N$.
Let g be a primitive root modulo $N\ge2$ and $D\ge 2$ a divisor of $N$. Show that the reduction modulo D of g is a primitive root modulo D. I've tried using Gauss' Theorem, but I'm not quite sure how ...
If $n$ has no primitive roots and $a$ and $n$ are coprime, what can we say about the order of $a$? I've Googled this a bit and nothing directly comes up. Ex: if $n = 42$ then we know it has not ...