Mixing
Finding the n-th root of unity in a finite field
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
I'm trying to find the n-th root of unity in a finite field that is given to me. n is a power of 2. The finite field has prime order. I know that if this were just normal numbers, I could find it using $e^(2pi ik/n)$. I have no idea how to translate that into finite fields.
finite-field
asked 4 hours ago
Kek
653
add a comment |Â
up vote
3
down vote
favorite
I'm trying to find the n-th root of unity in a finite field that is given to me. n is a power of 2. The finite field has prime order. I know that if this were just normal numbers, I could find it using $e^(2pi ik/n)$. I have no idea how to translate that into finite fields.
finite-field
asked 4 hours ago
Kek
653
1
But you are working in the multiplicative group, which has not prime order. See also this answer
– Ruggero
4 hours ago
@Ruggero: actually, there do exist finite fields with prime-sized multiplicative groups; for example, $GF(2^127)$.
– poncho
3 hours ago
@Ruggero The group I'm working with is certainly prime order.
– Kek
3 hours ago
If the multiplicative group you're working in has prime order andnis a power of 2, then the answer is easy; either you're working in $GF(3)$ (and so the answer is 1 and 2), or you're working in a larger group, in which case the onlyn-th root of 1 is 1, that is $x^n = 1$ only if $x=1$
– poncho
1 hour ago
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I'm trying to find the n-th root of unity in a finite field that is given to me. n is a power of 2. The finite field has prime order. I know that if this were just normal numbers, I could find it using $e^(2pi ik/n)$. I have no idea how to translate that into finite fields.
finite-field
asked 4 hours ago
Kek
653
I'm trying to find the n-th root of unity in a finite field that is given to me. n is a power of 2. The finite field has prime order. I know that if this were just normal numbers, I could find it using $e^(2pi ik/n)$. I have no idea how to translate that into finite fields.
finite-field
finite-field
asked 4 hours ago
Kek
653
asked 4 hours ago
Kek
653
asked 4 hours ago
Kek
653
asked 4 hours ago
Kek
653
asked 4 hours ago
Kek
653
653
1
But you are working in the multiplicative group, which has not prime order. See also this answer
– Ruggero
4 hours ago
@Ruggero: actually, there do exist finite fields with prime-sized multiplicative groups; for example, $GF(2^127)$.
– poncho
3 hours ago
@Ruggero The group I'm working with is certainly prime order.
– Kek
3 hours ago
If the multiplicative group you're working in has prime order andnis a power of 2, then the answer is easy; either you're working in $GF(3)$ (and so the answer is 1 and 2), or you're working in a larger group, in which case the onlyn-th root of 1 is 1, that is $x^n = 1$ only if $x=1$
– poncho
1 hour ago
add a comment |Â
1
But you are working in the multiplicative group, which has not prime order. See also this answer
– Ruggero
4 hours ago
@Ruggero: actually, there do exist finite fields with prime-sized multiplicative groups; for example, $GF(2^127)$.
– poncho
3 hours ago
@Ruggero The group I'm working with is certainly prime order.
– Kek
3 hours ago
If the multiplicative group you're working in has prime order andnis a power of 2, then the answer is easy; either you're working in $GF(3)$ (and so the answer is 1 and 2), or you're working in a larger group, in which case the onlyn-th root of 1 is 1, that is $x^n = 1$ only if $x=1$
– poncho
1 hour ago
1
1
But you are working in the multiplicative group, which has not prime order. See also this answer
– Ruggero
4 hours ago
But you are working in the multiplicative group, which has not prime order. See also this answer
– Ruggero
4 hours ago
@Ruggero: actually, there do exist finite fields with prime-sized multiplicative groups; for example, $GF(2^127)$.
– poncho
3 hours ago
@Ruggero: actually, there do exist finite fields with prime-sized multiplicative groups; for example, $GF(2^127)$.
– poncho
3 hours ago
@Ruggero The group I'm working with is certainly prime order.
– Kek
3 hours ago
@Ruggero The group I'm working with is certainly prime order.
– Kek
3 hours ago
If the multiplicative group you're working in has prime order and
n is a power of 2, then the answer is easy; either you're working in $GF(3)$ (and so the answer is 1 and 2), or you're working in a larger group, in which case the only n-th root of 1 is 1, that is $x^n = 1$ only if $x=1$– poncho
1 hour ago
If the multiplicative group you're working in has prime order and
n is a power of 2, then the answer is easy; either you're working in $GF(3)$ (and so the answer is 1 and 2), or you're working in a larger group, in which case the only n-th root of 1 is 1, that is $x^n = 1$ only if $x=1$– poncho
1 hour ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
In a finite field of size $q$, the multiplicative subgroup has order $q-1$ (i.e. all elements are invertible except $0$). If $n$ is relatively prime to $q-1$, then there is only one $n$-th root of unity, i.e. $1$ itself. If $n$ divides $q-1$, then there are $n$ roots of unity. In the remainder of this answer, I assume that you are in that case, i.e. $n$ divides $q-1$.
Everything I write below uses computations in the finite field (i.e. modulo $q$, if $q$ is prime).
To get an $n$-th root of unity, you generate a random non-zero $x$ in the field. Then:
$$ (x^(q-1)/n)^n = x^q-1 = 1 $$
Therefore, $x^(q-1)/n$ is an $n$-th root of unity. Note that you can end up with any of the $n$ $n$-th roots of unity (including $1$ itself), each with probability $1/n$.
Now you may want to have a primitive $n$-th root of unity, i.e. one value $g$ such that all $n$-th roots of unity can be obtained with values $g^j$ for integers $j$ ranging from $0$ to $n-1$. If $g$ is an $n$-th root of unity, then it is primitive if and only if $g^j neq 1$ for any $j > 0$ that divides $n$, except $n$ itself. In your case this is easy: since $n$ is a power of $2$, any $j$ that divides $n$ is also a power of $2$. In practice, this yields the following:
- Get a random $x neq 0$ in your finite field.
- Compute $g = x^(q-1)/n$.
- If $g^n/2 neq 1$, then $g$ is a primitive $n$-th root of unity. Otherwise, start again with another random $x$.
This will succeed with probability $1/2$ at each iteration, so you'll get your primitive root rather quickly. Also, you don't need a strongly secure randomness generator here (unless the choice of the primitive root is to be part of some secret).
Take care that there are several primitive $n$-th roots of unity; in your case, there are precisely $n/2$ of them. None of them is more primitive than the others; thus, there is no notion of "the primitive root". You find a primitive root.
answered 1 hour ago
Thomas Pornin
66.9k12174253
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
In a finite field of size $q$, the multiplicative subgroup has order $q-1$ (i.e. all elements are invertible except $0$). If $n$ is relatively prime to $q-1$, then there is only one $n$-th root of unity, i.e. $1$ itself. If $n$ divides $q-1$, then there are $n$ roots of unity. In the remainder of this answer, I assume that you are in that case, i.e. $n$ divides $q-1$.
Everything I write below uses computations in the finite field (i.e. modulo $q$, if $q$ is prime).
To get an $n$-th root of unity, you generate a random non-zero $x$ in the field. Then:
$$ (x^(q-1)/n)^n = x^q-1 = 1 $$
Therefore, $x^(q-1)/n$ is an $n$-th root of unity. Note that you can end up with any of the $n$ $n$-th roots of unity (including $1$ itself), each with probability $1/n$.
Now you may want to have a primitive $n$-th root of unity, i.e. one value $g$ such that all $n$-th roots of unity can be obtained with values $g^j$ for integers $j$ ranging from $0$ to $n-1$. If $g$ is an $n$-th root of unity, then it is primitive if and only if $g^j neq 1$ for any $j > 0$ that divides $n$, except $n$ itself. In your case this is easy: since $n$ is a power of $2$, any $j$ that divides $n$ is also a power of $2$. In practice, this yields the following:
- Get a random $x neq 0$ in your finite field.
- Compute $g = x^(q-1)/n$.
- If $g^n/2 neq 1$, then $g$ is a primitive $n$-th root of unity. Otherwise, start again with another random $x$.
This will succeed with probability $1/2$ at each iteration, so you'll get your primitive root rather quickly. Also, you don't need a strongly secure randomness generator here (unless the choice of the primitive root is to be part of some secret).
Take care that there are several primitive $n$-th roots of unity; in your case, there are precisely $n/2$ of them. None of them is more primitive than the others; thus, there is no notion of "the primitive root". You find a primitive root.
answered 1 hour ago
Thomas Pornin
66.9k12174253
add a comment |Â
up vote
3
down vote
In a finite field of size $q$, the multiplicative subgroup has order $q-1$ (i.e. all elements are invertible except $0$). If $n$ is relatively prime to $q-1$, then there is only one $n$-th root of unity, i.e. $1$ itself. If $n$ divides $q-1$, then there are $n$ roots of unity. In the remainder of this answer, I assume that you are in that case, i.e. $n$ divides $q-1$.
Everything I write below uses computations in the finite field (i.e. modulo $q$, if $q$ is prime).
To get an $n$-th root of unity, you generate a random non-zero $x$ in the field. Then:
$$ (x^(q-1)/n)^n = x^q-1 = 1 $$
Therefore, $x^(q-1)/n$ is an $n$-th root of unity. Note that you can end up with any of the $n$ $n$-th roots of unity (including $1$ itself), each with probability $1/n$.
Now you may want to have a primitive $n$-th root of unity, i.e. one value $g$ such that all $n$-th roots of unity can be obtained with values $g^j$ for integers $j$ ranging from $0$ to $n-1$. If $g$ is an $n$-th root of unity, then it is primitive if and only if $g^j neq 1$ for any $j > 0$ that divides $n$, except $n$ itself. In your case this is easy: since $n$ is a power of $2$, any $j$ that divides $n$ is also a power of $2$. In practice, this yields the following:
- Get a random $x neq 0$ in your finite field.
- Compute $g = x^(q-1)/n$.
- If $g^n/2 neq 1$, then $g$ is a primitive $n$-th root of unity. Otherwise, start again with another random $x$.
This will succeed with probability $1/2$ at each iteration, so you'll get your primitive root rather quickly. Also, you don't need a strongly secure randomness generator here (unless the choice of the primitive root is to be part of some secret).
Take care that there are several primitive $n$-th roots of unity; in your case, there are precisely $n/2$ of them. None of them is more primitive than the others; thus, there is no notion of "the primitive root". You find a primitive root.
answered 1 hour ago
Thomas Pornin
66.9k12174253
add a comment |Â
up vote
3
down vote
up vote
3
down vote
In a finite field of size $q$, the multiplicative subgroup has order $q-1$ (i.e. all elements are invertible except $0$). If $n$ is relatively prime to $q-1$, then there is only one $n$-th root of unity, i.e. $1$ itself. If $n$ divides $q-1$, then there are $n$ roots of unity. In the remainder of this answer, I assume that you are in that case, i.e. $n$ divides $q-1$.
Everything I write below uses computations in the finite field (i.e. modulo $q$, if $q$ is prime).
To get an $n$-th root of unity, you generate a random non-zero $x$ in the field. Then:
$$ (x^(q-1)/n)^n = x^q-1 = 1 $$
Therefore, $x^(q-1)/n$ is an $n$-th root of unity. Note that you can end up with any of the $n$ $n$-th roots of unity (including $1$ itself), each with probability $1/n$.
Now you may want to have a primitive $n$-th root of unity, i.e. one value $g$ such that all $n$-th roots of unity can be obtained with values $g^j$ for integers $j$ ranging from $0$ to $n-1$. If $g$ is an $n$-th root of unity, then it is primitive if and only if $g^j neq 1$ for any $j > 0$ that divides $n$, except $n$ itself. In your case this is easy: since $n$ is a power of $2$, any $j$ that divides $n$ is also a power of $2$. In practice, this yields the following:
- Get a random $x neq 0$ in your finite field.
- Compute $g = x^(q-1)/n$.
- If $g^n/2 neq 1$, then $g$ is a primitive $n$-th root of unity. Otherwise, start again with another random $x$.
This will succeed with probability $1/2$ at each iteration, so you'll get your primitive root rather quickly. Also, you don't need a strongly secure randomness generator here (unless the choice of the primitive root is to be part of some secret).
Take care that there are several primitive $n$-th roots of unity; in your case, there are precisely $n/2$ of them. None of them is more primitive than the others; thus, there is no notion of "the primitive root". You find a primitive root.
answered 1 hour ago
Thomas Pornin
66.9k12174253
In a finite field of size $q$, the multiplicative subgroup has order $q-1$ (i.e. all elements are invertible except $0$). If $n$ is relatively prime to $q-1$, then there is only one $n$-th root of unity, i.e. $1$ itself. If $n$ divides $q-1$, then there are $n$ roots of unity. In the remainder of this answer, I assume that you are in that case, i.e. $n$ divides $q-1$.
Everything I write below uses computations in the finite field (i.e. modulo $q$, if $q$ is prime).
To get an $n$-th root of unity, you generate a random non-zero $x$ in the field. Then:
$$ (x^(q-1)/n)^n = x^q-1 = 1 $$
Therefore, $x^(q-1)/n$ is an $n$-th root of unity. Note that you can end up with any of the $n$ $n$-th roots of unity (including $1$ itself), each with probability $1/n$.
Now you may want to have a primitive $n$-th root of unity, i.e. one value $g$ such that all $n$-th roots of unity can be obtained with values $g^j$ for integers $j$ ranging from $0$ to $n-1$. If $g$ is an $n$-th root of unity, then it is primitive if and only if $g^j neq 1$ for any $j > 0$ that divides $n$, except $n$ itself. In your case this is easy: since $n$ is a power of $2$, any $j$ that divides $n$ is also a power of $2$. In practice, this yields the following:
- Get a random $x neq 0$ in your finite field.
- Compute $g = x^(q-1)/n$.
- If $g^n/2 neq 1$, then $g$ is a primitive $n$-th root of unity. Otherwise, start again with another random $x$.
This will succeed with probability $1/2$ at each iteration, so you'll get your primitive root rather quickly. Also, you don't need a strongly secure randomness generator here (unless the choice of the primitive root is to be part of some secret).
Take care that there are several primitive $n$-th roots of unity; in your case, there are precisely $n/2$ of them. None of them is more primitive than the others; thus, there is no notion of "the primitive root". You find a primitive root.
answered 1 hour ago
Thomas Pornin
66.9k12174253
answered 1 hour ago
Thomas Pornin
66.9k12174253
answered 1 hour ago
Thomas Pornin
66.9k12174253
answered 1 hour ago
Thomas Pornin
66.9k12174253
66.9k12174253
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f63614%2ffinding-the-n-th-root-of-unity-in-a-finite-field%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
But you are working in the multiplicative group, which has not prime order. See also this answer
– Ruggero
4 hours ago
@Ruggero: actually, there do exist finite fields with prime-sized multiplicative groups; for example, $GF(2^127)$.
– poncho
3 hours ago
@Ruggero The group I'm working with is certainly prime order.
– Kek
3 hours ago
If the multiplicative group you're working in has prime order and
nis a power of 2, then the answer is easy; either you're working in $GF(3)$ (and so the answer is 1 and 2), or you're working in a larger group, in which case the onlyn-th root of 1 is 1, that is $x^n = 1$ only if $x=1$– poncho
1 hour ago