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.

9
votes
0answers
284 views

Number of primitive roots mod $p$ that are not primitive roots mod $p^2$

Consider the primitive roots of a prime $p$ in the range $1...p$ which are not primitive roots mod $p^2$. Let $n(p)$ be this number. While looking for an answer to this question, it seems that the ...
5
votes
0answers
189 views

Spliting subspaces and finite fields

I'm sure that the following is true, but I can't prove it. Let $R<S<K, R=\mathrm{GF}(q),\ S= \mathrm{GF}(q^n), \ K= \mathrm{GF}(q^{mn})$ be a tower of finite fields and $A = \{\theta\in K: \...
4
votes
0answers
206 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, ...
4
votes
0answers
90 views

About primitive roots and primes.

For any odd prime $p$ there exists at least one prime $q < p$ such that $q$ is a primitive root $\text{mod } p$ ; is this true?
3
votes
0answers
47 views

solutions of gold APN functions using trace function

The Gold APN is defined as $F(x)=x^{2^{k}+1}$ in $GF(2^n)$, where $\gcd(k,n)=1$. The differential uniformity computed using $F(x)=F(x+a)=b$ as following: $x^{2^{k}+1} + (x+a)^{2^{k}+1}=b$ $x^{2^{k}+...
3
votes
0answers
44 views

Some questions concerning the generators of cyclic groups

Let $g(p)$ be the least positive primitive root of the prime $p$, the primitive roots being the generators of the cyclic group $\mathbb{Z}_{p-1}$. These are the values for the first prime numbers: $$...
2
votes
0answers
195 views

Primitive $p$-th root of unity with characteristic $p$

I struggle on this since two days, and still found no answer. My course states the following: If the characteristic of $K \neq p$, then they are exactly $p-1$ different $p$-th roots of unity in the ...
2
votes
0answers
105 views

Theorems on Primitive Roots

Let g be a primitive root modulo $p$($p$ is an odd prime) with $g^{p-1}\ncong{1}\ (mod\ p^{2})$. I am interested in proving that $$g^{(p-1)p^{m-2}}\ncong{1}\ (mod\ p^{m})$$ for every $m\geq{2}$ So ...
2
votes
0answers
67 views

How to prove that all the eigenvalues of this matrix have modulus $\sqrt{n}$?

Let $\zeta$ be a primitive $n$-th root of unity. Prove that all eigenvalues of the matrix $\left(\begin{matrix} 1 & 1 & 1 & \cdots & 1\\ 1 & \zeta & \zeta^2 & \cdots & ...
2
votes
0answers
235 views

Subgroups and corresponding fixed fields of Galois group of primitive 24th root of unity.

I have been asked to determine the lattice of subgroups of $G=\Gamma(\mathbb{Q}(\zeta):\mathbb{Q})$ where $\zeta$ is a primitive $24^{th}$ root of unity. I am then asked to determine their ...
2
votes
0answers
234 views

Primitive elements of finite fields

Let $p$ be a prime number and $q=p^n$ for some positive integer $n$. $F_q[x]$ is the polynomial ring with coefficients in $F_q$. For any $M(x)\in F_q[x]$, define $\mathcal{R}(M(x))\subset F_q[x]$ to ...
2
votes
0answers
39 views

Generators in arithmetic progression.

Suppose $p+1$ is a prime fix $a,b\in\Bbb Z_p^\times$ how many generators of $\Bbb Z_p^\times$ lie on the line $ax+b$ considered over $\Bbb Z$ and what is the size of a typical minimal generator with ...
2
votes
0answers
350 views

When is 2 a primitive root for a Sophie Germain prime $p$ or its associate $2p + 1$?

A prime $p$ is a Sophie Germain prime if its associate $2p + 1$ is also prime. When is $2$ a primitive root for a Sophie Germain prime $p$ or its associate $2p + 1$? A previous question found that a ...
2
votes
0answers
81 views

Lower bound for the values of cyclotomic polynomials evualuated at integers

Let $b,n \geq 2$ be integers and let $\Phi_n(b)$ be the value of the $n$-th cyclotomic polynomial evaluated at $b$. I've recently noticed by computer experiments that whenever $n$ is odd, we seem to ...
2
votes
0answers
91 views

Distribution of Primitive Elements Finite Fields Prime Order

It is well known that the integers modulo a prime $p$ form a finite field and that the multiplicative group of this finite field is cyclic, with $\phi(p-1)$ different possible choices of primitive ...
2
votes
0answers
64 views

A multivalued function $ f(x) = 0 $ with integer solutions $ x_1=p(n) $ and $x_2=q(n) $

Please help me to define a multivalued function $ f(x) = 0 $ with integer solutions : $ x_1 = p(n)$ and $ x_2 = q(n) $ such that $\dfrac{ p(n) + q(n) } { 2 } = 2 n + 1 $ and $ \...
2
votes
0answers
45 views

About primitive roots and ways of expressing them.

If $q$ is a primitive root mod $p$ and $q = (2^a)(3^b)(5^c)\pmod p$ for some $a,b,c$ all elements of integers then say that this $q$ has the 'form' $\{2,3,5\}(p)$. Then is it true all the residues $\...
1
vote
0answers
24 views

upper bound on, or fast algorithm to find, an order $2^n$ element in the multiplicative group modulo prime $q(2^n)+1$

I have a program which (in its current implementation) requires, for a given $N=2^n$, some $\omega$ in some field such that $\omega^N=1$ and $\omega^i\ne1$ for each $0<i<N$. Complex roots of ...
1
vote
0answers
25 views

Primitive roots in arithmetic progression

Let $a$ be a primitive root modulo odd prime. Show that in an arithmetic progression $a+kp$, where $k = 0,1,\dots,p-1$ there is exactly one number that is NOT a primitive root modulo $p^2$. It is ...
1
vote
0answers
35 views

What is the best upper bound for “how often” a number n is a primitive root modulo a prime p?

Let $n$ be a non-square positive number. The Artin Conjecture states that there are infinitely primes $p$ for which $n$ is a primitive root. Question: Given a number $n$, what is the best upper bound ...
1
vote
0answers
38 views

Certain conditions for primitive roots of $n$.

Let $a$ be a primitive root for modulo $n$. Then, $a^{\frac{\phi(n)}{2}}\equiv-1\pmod{n}$. I have a question for its converse. In general, its converse is false. Is it possible to make(it means '...
1
vote
0answers
65 views

Is this a valid proof of Euler's product formula for the totient function?

I will attempt the proof using induction. But first, a lemma: Lemma 1: If $ n = p^{\alpha} $, where $ p $ is prime and $ \alpha\in\mathbb{N} $, then $ \phi(n) = n(1-\frac{1}{p}) $. $ \underline{...
1
vote
0answers
37 views

n is primitive root for odd prime p. If -n is primitive root iff p = 4k+1 for some integer k

if $n$ is primitive root for odd prime $p$, then $-n$ is also a primitive root for $p$ $\iff p = 1 \text{ mod } 4$ I am having trouble solving this question, can someone show to me how to solve it? ...
1
vote
0answers
146 views

Primitive nth roots of unity related to the complex nth roots of 1.

I just cannot seem to wrap my head around this problem and would really appreciate some guidance. So I know that a primitive $n^{th}$ root of unity is a complex number $z$ such that $z^n = 1$ but $z^m ...
1
vote
0answers
338 views

Let $p$ be an odd prime. Suppose $a$ and $b$ are both primitive roots mod $p$. Show that $ab$ is not a primitive root mod $p$

Let $p$ be an odd prime. Suppose $a$ and $b$ are both primitive roots mod $p$. Show that $ab$ is not a primitive root mod $p$. Would appreciate some proof-checking here. First, we show that a ...
1
vote
0answers
80 views

When does a prime divide the sum of its primitive roots?

Here : Prime numbers primitive roots and $\Phi$? the ratio between the primes dividing the sum of its primitive roots and the primes upto a given limit is asked. Is there a nice criterion ...
1
vote
0answers
44 views

How to calculate the cardinality of following set

If $$A = \bigg\{\sum_{i=0}^4a_i x^{i}+b_i x^{i}y \ \big| \bigg(\sum_{i=0}^4a_iw^i\bigg)\bigg(\sum_{i=0}^4a_iw^{4i}\bigg) = 0: a_i, b_i \in \mathbb{F}_{2^k}\bigg\}$$ where $\mathbb{F}_{2^k}$ is a field ...
1
vote
0answers
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 ...
1
vote
0answers
177 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.
1
vote
0answers
906 views

confusion on how to find primitive roots (find primitive root mod 23, 46, 529, 12167)

We were asked to find primitive root mod $23$, $46$, $529$, $12167$. My lecturer gave us a hint in finding primitive root mod $23$, but I am confused about his reasoning. My lecturer said $a$ would ...
1
vote
0answers
103 views

Are non-squares primitive roots?

We know that even squares cannot be primitive roots modulo primes.Are all other natural numbers primitive roots mod some p? My heuristic argument goes as follows: the probability that a natural ...
1
vote
0answers
98 views

Finding primitive root mod n?

in wikipedia, https://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots, it says there is no formula to compute primitive root mod n. and in the footnote 8, it seems that there ...
1
vote
0answers
53 views

evaluate the integrals using Primitives

Evaluate the integrals $\int_\gamma z^ndz$ for all integers n. Here $\gamma$ is any circle not containing the origin. The answer to this problem is extremely difficult. $$ \int \limits_{\gamma }\...
1
vote
0answers
39 views

Is $\mathbb{Q}(z,\dots,z^{n-1})$ the splitting field of some polynomial $\mathbb{Q}[x]$, where $z$ is a primitive root of unity?

Is $\mathbb{Q}(z,...z^{n-1})$ the splitting field of some polynomial in $\mathbb{Q}[x]$, where $z$ is a primitive root of unity? I know that if $n\ge 1$ and $k$ is a field, and $f(x)=x^n-1\in k[x]$, ...
1
vote
0answers
22 views

Basis of the special form

Let $R = \mathrm{GF}(q)$, $S = \mathrm{GF}(q^n), \ n\geq 2$ be extension of $R$, $h$ be a primitive element of $S$. I want to count or estimate the number $N$ of basis of the following form. Let $$\...
1
vote
0answers
47 views

Primitive root of unity with certain conditions

Find a primitive $k$-th root of unity $w$ modulo some prime $p$, where $k\geq a$ and $p\geq b$ where $a,b$ are chosen constants. After looking online, I know I can find such values from tables, e.g. ...
1
vote
0answers
207 views

Number Theory: Find a primitive root of $13^{901}$ and find a complete set of primitive roots of $13$

I solved this problem: Find a complete set of mutually incongruent primitive roots of $13$. I know that there are $\phi(\phi(13))=4$ primitive roots of 13, which are $2,6,7,$ and $11$. However, I ...
1
vote
0answers
136 views

Number Theory: Prove $x^k\equiv a\pmod{p}$ is solvable for $r^d,r^{2d},\dots,r^{[(p-1)/d]d}$.

I think I have the proof to this problem, but I'm not sure if it's correct: Let $r$ be a primitive root of the odd prime $p$, and let $d=\gcd(k,p-1)$. Prove that the values of $a$ for which the ...
1
vote
0answers
289 views

Efficient way to find primitive root without prime factorization

I was wondering if there is a more efficient brute-forcing approach to find any primitive root of number $p$ without prime factorization. My approach is as follows: Get a random residue class $[x]$ ...
1
vote
0answers
65 views

Proof for primality based on exponents and primitive roots

I'm trying to prove the following statement: Suppose $n > 1$. The number $n$ is prime if and only if there exists a number $b$ such that gcd$(b, n) = 1$ and $b^{n−1} ≡ 1$ (mod $n$) and $b^{(n−1)/d}...
1
vote
0answers
81 views

Multiplicative order: an exercise

I've got this problem: Determine an integer with (exactly) multiplicative order $22$ mod $1331$ Is there a general way to procede in any case with this kind of exercises? Thank you!
1
vote
0answers
700 views

Extension field of F2 , expressing roots and primitive elements in that field

Let $\Phi$ be an extension field of $\Bbb{F}_2$ of extension degree s >1. Let $a(x)$ be a non-zero polynomial with the coefficients in $\Bbb{F}_2$. (a) Show that if $\beta$ is a root of the ...
0
votes
0answers
31 views

Let $w\in G_{18}$ be a primitive root of unity. Prove that $w^{16} \sum_{j=1}^{17}(w^3 \overline{w})^{3j+1}$ is imaginary pure.

This is what I've got: $$w^3\overline{w}=w^3w^{-1}=w^2 \iff \\ w^{16} \sum_{j=1}^{17}(w^3 \overline{w})^{3j+1} = w^{16}w^2\sum_{j=1}^{17}w^{6j} = \bigg( \sum_{j=0}^{17}w^{6j} \bigg) - 1$$ Given that ...
0
votes
0answers
22 views

Isn't primitive root co-prime with corresponding modulo value?

Suppose, g is a primitive root modulo n. Therefore, $g^{\phi(n)} \equiv 1 \pmod n$ then g is always co-prime to n? Isn't it?
0
votes
0answers
21 views

Sign of these complex embeddings

Let $\alpha$ be a root of $f = x^4 - 7$, hence $\alpha$ is a fourth root of $7$. Consider the number field $F = \mathbb{Q}(\sqrt[4]{7})$, which is of degree $4$. Since it is of degree $4$, there ...
0
votes
0answers
31 views

In general, do primes of the form $a×2^{n}+1$always have primitive $2^n $th roots of unity (modulo that prime)?

EDIT: Title had an extra +1 in the 2's exponent For context, in competitive programming, problems which require a number theoretic transform usually ask for the answer modulo $998244353=7\times17\...
0
votes
0answers
29 views

Any finite field of $q$ elements has exactly $\Phi(q-1)$ primitive roots

Is the following prove of the above statement correct? $\bullet\ $Any finite field of $q$ elements is isomorphic to $\mathbb{F}_q$ and we know that $\mathbb{F}_q^*$ is a cyclic group of $q-1$ ...
0
votes
0answers
59 views

Determine a Normal Basis for Galois Extension of $\mathbb{Q}$ with primitive pth root of unit (p prime)

Let p be a prime, $\xi_p \in \mathbb{C}$ a primitive p-th unit root and $K = \mathbb{Q}(\xi_p)$. Give a normal basis for $K/\mathbb{Q}$. I know, that a basis of $L/K$ (finite and galois) is ...
0
votes
0answers
43 views

Given 2 is primitive root (mod p), showing that every non-zero element of Z(p) is expressable as power of [2] (mod p)

I'm trying to find out how I would go about showing this: Given a prime number p >= 2, suppose 2 is a primitive root modulo p. Show that every non-zero element of Z(p) can be written as a power of [2]...
0
votes
0answers
60 views

Relation between residues and primitive roots modulo $p$

I got a very satisfiying answer to my question on the relation between primeness and co-primeness of numbers which can be defined in a somehow symmetric way: $n$ is prime iff $$(\forall xy)\ ...