How can I find large irreducible polynomials over $mathbf{Z}_2$ [closed]
$begingroup$
I'm working on a cryptography algorithm. We need $GF(2^n)$ for large n. Therefore we are looking for large irreducible polynomials over $mathbf{Z}_2$. Especially we want trinomial and n~65536. I tried to use mathematica but it's too slow.
abstract-algebra
asked Jan 6 at 10:22
Kaiyi ZhangKaiyi Zhang
82
$endgroup$
closed as off-topic by José Carlos Santos, Cesareo, Adrian Keister, Namaste, jgon Jan 9 at 17:57
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 provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – José Carlos Santos, Cesareo, Adrian Keister, Namaste, jgon
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
I'm working on a cryptography algorithm. We need $GF(2^n)$ for large n. Therefore we are looking for large irreducible polynomials over $mathbf{Z}_2$. Especially we want trinomial and n~65536. I tried to use mathematica but it's too slow.
abstract-algebra
asked Jan 6 at 10:22
Kaiyi ZhangKaiyi Zhang
82
$endgroup$
closed as off-topic by José Carlos Santos, Cesareo, Adrian Keister, Namaste, jgon Jan 9 at 17:57
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 provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – José Carlos Santos, Cesareo, Adrian Keister, Namaste, jgon
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
Good question. Some large irreducibles might be tabulated somewhere.
$endgroup$
– Wuestenfux
Jan 6 at 10:26
$begingroup$
Do you need many such polynomials, or just a few?
$endgroup$
– MJD
Jan 6 at 10:52
add a comment |
$begingroup$
I'm working on a cryptography algorithm. We need $GF(2^n)$ for large n. Therefore we are looking for large irreducible polynomials over $mathbf{Z}_2$. Especially we want trinomial and n~65536. I tried to use mathematica but it's too slow.
abstract-algebra
asked Jan 6 at 10:22
Kaiyi ZhangKaiyi Zhang
82
$endgroup$
I'm working on a cryptography algorithm. We need $GF(2^n)$ for large n. Therefore we are looking for large irreducible polynomials over $mathbf{Z}_2$. Especially we want trinomial and n~65536. I tried to use mathematica but it's too slow.
abstract-algebra
abstract-algebra
asked Jan 6 at 10:22
Kaiyi ZhangKaiyi Zhang
82
asked Jan 6 at 10:22
Kaiyi ZhangKaiyi Zhang
82
asked Jan 6 at 10:22
Kaiyi ZhangKaiyi Zhang
82
asked Jan 6 at 10:22
Kaiyi ZhangKaiyi Zhang
82
asked Jan 6 at 10:22
Kaiyi ZhangKaiyi Zhang
82
82
closed as off-topic by José Carlos Santos, Cesareo, Adrian Keister, Namaste, jgon Jan 9 at 17:57
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 provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – José Carlos Santos, Cesareo, Adrian Keister, Namaste, jgon
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by José Carlos Santos, Cesareo, Adrian Keister, Namaste, jgon Jan 9 at 17:57
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 provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – José Carlos Santos, Cesareo, Adrian Keister, Namaste, jgon
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
Good question. Some large irreducibles might be tabulated somewhere.
$endgroup$
– Wuestenfux
Jan 6 at 10:26
$begingroup$
Do you need many such polynomials, or just a few?
$endgroup$
– MJD
Jan 6 at 10:52
add a comment |
$begingroup$
Good question. Some large irreducibles might be tabulated somewhere.
$endgroup$
– Wuestenfux
Jan 6 at 10:26
$begingroup$
Do you need many such polynomials, or just a few?
$endgroup$
– MJD
Jan 6 at 10:52
$begingroup$
Good question. Some large irreducibles might be tabulated somewhere.
$endgroup$
– Wuestenfux
Jan 6 at 10:26
$begingroup$
Good question. Some large irreducibles might be tabulated somewhere.
$endgroup$
– Wuestenfux
Jan 6 at 10:26
$begingroup$
Do you need many such polynomials, or just a few?
$endgroup$
– MJD
Jan 6 at 10:52
$begingroup$
Do you need many such polynomials, or just a few?
$endgroup$
– MJD
Jan 6 at 10:52
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Lidl and Niederreiter give an explicit infinite family of irreducible polynomials in $Bbb F_2[x]$ of arbitrary high degree. For any $kge 1$ the polynomial
$$
p_k(X)=X^{2cdot3^k}+X^{3^k}+1in Bbb F_2[X]
$$
is irreducible (these are trinomials, as you wanted).
answered Jan 6 at 11:06
Dietrich BurdeDietrich Burde
81.9k649107
$endgroup$
$begingroup$
Thanks! but the nearest $2times 3^k$ is 39366, which is not so close
$endgroup$
– Kaiyi Zhang
Jan 6 at 12:32
$begingroup$
I thought, you wanted (see title) to know "how can I find large irreducible polynomials over $mathbf{Z}_2$?", and $2cdot 3^{10}=118098$ is even larger than $65536$. But you can also find a irreducible polynomial $X^{65536}+cdots $, see here.
$endgroup$
– Dietrich Burde
Jan 6 at 12:36
$begingroup$
Thanks, that's helpful.
$endgroup$
– Kaiyi Zhang
Jan 6 at 13:22
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Lidl and Niederreiter give an explicit infinite family of irreducible polynomials in $Bbb F_2[x]$ of arbitrary high degree. For any $kge 1$ the polynomial
$$
p_k(X)=X^{2cdot3^k}+X^{3^k}+1in Bbb F_2[X]
$$
is irreducible (these are trinomials, as you wanted).
answered Jan 6 at 11:06
Dietrich BurdeDietrich Burde
81.9k649107
$endgroup$
$begingroup$
Thanks! but the nearest $2times 3^k$ is 39366, which is not so close
$endgroup$
– Kaiyi Zhang
Jan 6 at 12:32
$begingroup$
I thought, you wanted (see title) to know "how can I find large irreducible polynomials over $mathbf{Z}_2$?", and $2cdot 3^{10}=118098$ is even larger than $65536$. But you can also find a irreducible polynomial $X^{65536}+cdots $, see here.
$endgroup$
– Dietrich Burde
Jan 6 at 12:36
$begingroup$
Thanks, that's helpful.
$endgroup$
– Kaiyi Zhang
Jan 6 at 13:22
add a comment |
$begingroup$
Lidl and Niederreiter give an explicit infinite family of irreducible polynomials in $Bbb F_2[x]$ of arbitrary high degree. For any $kge 1$ the polynomial
$$
p_k(X)=X^{2cdot3^k}+X^{3^k}+1in Bbb F_2[X]
$$
is irreducible (these are trinomials, as you wanted).
answered Jan 6 at 11:06
Dietrich BurdeDietrich Burde
81.9k649107
$endgroup$
$begingroup$
Thanks! but the nearest $2times 3^k$ is 39366, which is not so close
$endgroup$
– Kaiyi Zhang
Jan 6 at 12:32
$begingroup$
I thought, you wanted (see title) to know "how can I find large irreducible polynomials over $mathbf{Z}_2$?", and $2cdot 3^{10}=118098$ is even larger than $65536$. But you can also find a irreducible polynomial $X^{65536}+cdots $, see here.
$endgroup$
– Dietrich Burde
Jan 6 at 12:36
$begingroup$
Thanks, that's helpful.
$endgroup$
– Kaiyi Zhang
Jan 6 at 13:22
add a comment |
$begingroup$
Lidl and Niederreiter give an explicit infinite family of irreducible polynomials in $Bbb F_2[x]$ of arbitrary high degree. For any $kge 1$ the polynomial
$$
p_k(X)=X^{2cdot3^k}+X^{3^k}+1in Bbb F_2[X]
$$
is irreducible (these are trinomials, as you wanted).
answered Jan 6 at 11:06
Dietrich BurdeDietrich Burde
81.9k649107
$endgroup$
Lidl and Niederreiter give an explicit infinite family of irreducible polynomials in $Bbb F_2[x]$ of arbitrary high degree. For any $kge 1$ the polynomial
$$
p_k(X)=X^{2cdot3^k}+X^{3^k}+1in Bbb F_2[X]
$$
is irreducible (these are trinomials, as you wanted).
answered Jan 6 at 11:06
Dietrich BurdeDietrich Burde
81.9k649107
edited Jan 6 at 11:11
answered Jan 6 at 11:06
Dietrich BurdeDietrich Burde
81.9k649107
answered Jan 6 at 11:06
Dietrich BurdeDietrich Burde
81.9k649107
answered Jan 6 at 11:06
Dietrich BurdeDietrich Burde
81.9k649107
81.9k649107
$begingroup$
Thanks! but the nearest $2times 3^k$ is 39366, which is not so close
$endgroup$
– Kaiyi Zhang
Jan 6 at 12:32
$begingroup$
I thought, you wanted (see title) to know "how can I find large irreducible polynomials over $mathbf{Z}_2$?", and $2cdot 3^{10}=118098$ is even larger than $65536$. But you can also find a irreducible polynomial $X^{65536}+cdots $, see here.
$endgroup$
– Dietrich Burde
Jan 6 at 12:36
$begingroup$
Thanks, that's helpful.
$endgroup$
– Kaiyi Zhang
Jan 6 at 13:22
add a comment |
$begingroup$
Thanks! but the nearest $2times 3^k$ is 39366, which is not so close
$endgroup$
– Kaiyi Zhang
Jan 6 at 12:32
$begingroup$
I thought, you wanted (see title) to know "how can I find large irreducible polynomials over $mathbf{Z}_2$?", and $2cdot 3^{10}=118098$ is even larger than $65536$. But you can also find a irreducible polynomial $X^{65536}+cdots $, see here.
$endgroup$
– Dietrich Burde
Jan 6 at 12:36
$begingroup$
Thanks, that's helpful.
$endgroup$
– Kaiyi Zhang
Jan 6 at 13:22
$begingroup$
Thanks! but the nearest $2times 3^k$ is 39366, which is not so close
$endgroup$
– Kaiyi Zhang
Jan 6 at 12:32
$begingroup$
Thanks! but the nearest $2times 3^k$ is 39366, which is not so close
$endgroup$
– Kaiyi Zhang
Jan 6 at 12:32
$begingroup$
I thought, you wanted (see title) to know "how can I find large irreducible polynomials over $mathbf{Z}_2$?", and $2cdot 3^{10}=118098$ is even larger than $65536$. But you can also find a irreducible polynomial $X^{65536}+cdots $, see here.
$endgroup$
– Dietrich Burde
Jan 6 at 12:36
$begingroup$
I thought, you wanted (see title) to know "how can I find large irreducible polynomials over $mathbf{Z}_2$?", and $2cdot 3^{10}=118098$ is even larger than $65536$. But you can also find a irreducible polynomial $X^{65536}+cdots $, see here.
$endgroup$
– Dietrich Burde
Jan 6 at 12:36
$begingroup$
Thanks, that's helpful.
$endgroup$
– Kaiyi Zhang
Jan 6 at 13:22
$begingroup$
Thanks, that's helpful.
$endgroup$
– Kaiyi Zhang
Jan 6 at 13:22
add a comment |
$begingroup$
Good question. Some large irreducibles might be tabulated somewhere.
$endgroup$
– Wuestenfux
Jan 6 at 10:26
$begingroup$
Do you need many such polynomials, or just a few?
$endgroup$
– MJD
Jan 6 at 10:52