Assume that $g$ is a generator of $Bbb F_q$. Show that $g^i$ is a generator if and only if $i$ and $q−1$...
up vote
0
down vote
favorite
Assume that $g$ is a generator of $Bbb F_q$. Show that $g^i$ is a generator if and only if $i$ and $q−1$ are relatively prime.
I'm not exactly sure how to start this problem, so every help would be very useful.
finite-fields cryptography
edited Nov 19 at 2:58
Tianlalu
2,674632
asked Nov 19 at 0:39
George S
13010
closed as off-topic by user10354138, John B, Shailesh, Brahadeesh, Jyrki Lahtonen Nov 19 at 5:12
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user10354138, John B, Shailesh, Brahadeesh, Jyrki Lahtonen
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
up vote
0
down vote
favorite
Assume that $g$ is a generator of $Bbb F_q$. Show that $g^i$ is a generator if and only if $i$ and $q−1$ are relatively prime.
I'm not exactly sure how to start this problem, so every help would be very useful.
finite-fields cryptography
edited Nov 19 at 2:58
Tianlalu
2,674632
asked Nov 19 at 0:39
George S
13010
closed as off-topic by user10354138, John B, Shailesh, Brahadeesh, Jyrki Lahtonen Nov 19 at 5:12
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user10354138, John B, Shailesh, Brahadeesh, Jyrki Lahtonen
If this question can be reworded to fit the rules in the help center, please edit the question.
1
This is more a question about generators of cyclic groups (rather than about finite fields or cryptography). For a cyclic group of order $n$ with $g$ a generator, the other generators are precisely $g^i$ with gcd$(i,n)=1$.
– P Vanchinathan
Nov 19 at 3:07
1
The way to start is to remind yourself of the definition of "generator", and then see whether the definition works if $i$ and $q-1$ are relatively prime, and whether it works if they aren't.
– Gerry Myerson
Nov 19 at 3:24
Every element of $Bbb{F}_q$ is a power of $g^k$ if and only if every element of $Bbb{F}_q$ has a $k$th root, so this is also a duplicate of this in a sense.
– Jyrki Lahtonen
Nov 19 at 5:12
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Assume that $g$ is a generator of $Bbb F_q$. Show that $g^i$ is a generator if and only if $i$ and $q−1$ are relatively prime.
I'm not exactly sure how to start this problem, so every help would be very useful.
finite-fields cryptography
edited Nov 19 at 2:58
Tianlalu
2,674632
asked Nov 19 at 0:39
George S
13010
Assume that $g$ is a generator of $Bbb F_q$. Show that $g^i$ is a generator if and only if $i$ and $q−1$ are relatively prime.
I'm not exactly sure how to start this problem, so every help would be very useful.
finite-fields cryptography
finite-fields cryptography
edited Nov 19 at 2:58
Tianlalu
2,674632
asked Nov 19 at 0:39
George S
13010
edited Nov 19 at 2:58
Tianlalu
2,674632
asked Nov 19 at 0:39
George S
13010
edited Nov 19 at 2:58
Tianlalu
2,674632
edited Nov 19 at 2:58
Tianlalu
2,674632
edited Nov 19 at 2:58
Tianlalu
2,674632
2,674632
asked Nov 19 at 0:39
George S
13010
asked Nov 19 at 0:39
George S
13010
asked Nov 19 at 0:39
George S
13010
13010
closed as off-topic by user10354138, John B, Shailesh, Brahadeesh, Jyrki Lahtonen Nov 19 at 5:12
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user10354138, John B, Shailesh, Brahadeesh, Jyrki Lahtonen
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by user10354138, John B, Shailesh, Brahadeesh, Jyrki Lahtonen Nov 19 at 5:12
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user10354138, John B, Shailesh, Brahadeesh, Jyrki Lahtonen
If this question can be reworded to fit the rules in the help center, please edit the question.
1
This is more a question about generators of cyclic groups (rather than about finite fields or cryptography). For a cyclic group of order $n$ with $g$ a generator, the other generators are precisely $g^i$ with gcd$(i,n)=1$.
– P Vanchinathan
Nov 19 at 3:07
1
The way to start is to remind yourself of the definition of "generator", and then see whether the definition works if $i$ and $q-1$ are relatively prime, and whether it works if they aren't.
– Gerry Myerson
Nov 19 at 3:24
Every element of $Bbb{F}_q$ is a power of $g^k$ if and only if every element of $Bbb{F}_q$ has a $k$th root, so this is also a duplicate of this in a sense.
– Jyrki Lahtonen
Nov 19 at 5:12
add a comment |
1
This is more a question about generators of cyclic groups (rather than about finite fields or cryptography). For a cyclic group of order $n$ with $g$ a generator, the other generators are precisely $g^i$ with gcd$(i,n)=1$.
– P Vanchinathan
Nov 19 at 3:07
1
The way to start is to remind yourself of the definition of "generator", and then see whether the definition works if $i$ and $q-1$ are relatively prime, and whether it works if they aren't.
– Gerry Myerson
Nov 19 at 3:24
Every element of $Bbb{F}_q$ is a power of $g^k$ if and only if every element of $Bbb{F}_q$ has a $k$th root, so this is also a duplicate of this in a sense.
– Jyrki Lahtonen
Nov 19 at 5:12
1
1
This is more a question about generators of cyclic groups (rather than about finite fields or cryptography). For a cyclic group of order $n$ with $g$ a generator, the other generators are precisely $g^i$ with gcd$(i,n)=1$.
– P Vanchinathan
Nov 19 at 3:07
This is more a question about generators of cyclic groups (rather than about finite fields or cryptography). For a cyclic group of order $n$ with $g$ a generator, the other generators are precisely $g^i$ with gcd$(i,n)=1$.
– P Vanchinathan
Nov 19 at 3:07
1
1
The way to start is to remind yourself of the definition of "generator", and then see whether the definition works if $i$ and $q-1$ are relatively prime, and whether it works if they aren't.
– Gerry Myerson
Nov 19 at 3:24
The way to start is to remind yourself of the definition of "generator", and then see whether the definition works if $i$ and $q-1$ are relatively prime, and whether it works if they aren't.
– Gerry Myerson
Nov 19 at 3:24
Every element of $Bbb{F}_q$ is a power of $g^k$ if and only if every element of $Bbb{F}_q$ has a $k$th root, so this is also a duplicate of this in a sense.
– Jyrki Lahtonen
Nov 19 at 5:12
Every element of $Bbb{F}_q$ is a power of $g^k$ if and only if every element of $Bbb{F}_q$ has a $k$th root, so this is also a duplicate of this in a sense.
– Jyrki Lahtonen
Nov 19 at 5:12
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
1
This is more a question about generators of cyclic groups (rather than about finite fields or cryptography). For a cyclic group of order $n$ with $g$ a generator, the other generators are precisely $g^i$ with gcd$(i,n)=1$.
– P Vanchinathan
Nov 19 at 3:07
1
The way to start is to remind yourself of the definition of "generator", and then see whether the definition works if $i$ and $q-1$ are relatively prime, and whether it works if they aren't.
– Gerry Myerson
Nov 19 at 3:24
Every element of $Bbb{F}_q$ is a power of $g^k$ if and only if every element of $Bbb{F}_q$ has a $k$th root, so this is also a duplicate of this in a sense.
– Jyrki Lahtonen
Nov 19 at 5:12