How can I find large irreducible polynomials over $mathbf{Z}_2$ [on hold]
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
New contributor
Kaiyi Zhang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
put on hold as off-topic by José Carlos Santos, Cesareo, Adrian Keister, amWhy, jgon 8 hours ago
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, amWhy, jgon
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
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
New contributor
Kaiyi Zhang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
put on hold as off-topic by José Carlos Santos, Cesareo, Adrian Keister, amWhy, jgon 8 hours ago
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, amWhy, jgon
If this question can be reworded to fit the rules in the help center, please edit the question.
Good question. Some large irreducibles might be tabulated somewhere.
– Wuestenfux
Jan 6 at 10:26
Do you need many such polynomials, or just a few?
– MJD
Jan 6 at 10:52
add a comment |
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
New contributor
Kaiyi Zhang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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
New contributor
Kaiyi Zhang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jan 6 at 10:22
Kaiyi ZhangKaiyi Zhang
82
New contributor
Kaiyi Zhang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jan 6 at 10:22
Kaiyi ZhangKaiyi Zhang
82
New contributor
Kaiyi Zhang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jan 6 at 10:22
Kaiyi ZhangKaiyi Zhang
82
asked Jan 6 at 10:22
Kaiyi ZhangKaiyi Zhang
82
82
New contributor
Kaiyi Zhang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Kaiyi Zhang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Kaiyi Zhang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
put on hold as off-topic by José Carlos Santos, Cesareo, Adrian Keister, amWhy, jgon 8 hours ago
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, amWhy, jgon
If this question can be reworded to fit the rules in the help center, please edit the question.
put on hold as off-topic by José Carlos Santos, Cesareo, Adrian Keister, amWhy, jgon 8 hours ago
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, amWhy, jgon
If this question can be reworded to fit the rules in the help center, please edit the question.
Good question. Some large irreducibles might be tabulated somewhere.
– Wuestenfux
Jan 6 at 10:26
Do you need many such polynomials, or just a few?
– MJD
Jan 6 at 10:52
add a comment |
Good question. Some large irreducibles might be tabulated somewhere.
– Wuestenfux
Jan 6 at 10:26
Do you need many such polynomials, or just a few?
– MJD
Jan 6 at 10:52
Good question. Some large irreducibles might be tabulated somewhere.
– Wuestenfux
Jan 6 at 10:26
Good question. Some large irreducibles might be tabulated somewhere.
– Wuestenfux
Jan 6 at 10:26
Do you need many such polynomials, or just a few?
– MJD
Jan 6 at 10:52
Do you need many such polynomials, or just a few?
– MJD
Jan 6 at 10:52
add a comment |
1 Answer
1
active
oldest
votes
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
78.1k64386
Thanks! but the nearest $2times 3^k$ is 39366, which is not so close
– Kaiyi Zhang
Jan 6 at 12:32
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.
– Dietrich Burde
Jan 6 at 12:36
Thanks, that's helpful.
– 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
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
78.1k64386
Thanks! but the nearest $2times 3^k$ is 39366, which is not so close
– Kaiyi Zhang
Jan 6 at 12:32
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.
– Dietrich Burde
Jan 6 at 12:36
Thanks, that's helpful.
– Kaiyi Zhang
Jan 6 at 13:22
add a comment |
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
78.1k64386
Thanks! but the nearest $2times 3^k$ is 39366, which is not so close
– Kaiyi Zhang
Jan 6 at 12:32
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.
– Dietrich Burde
Jan 6 at 12:36
Thanks, that's helpful.
– Kaiyi Zhang
Jan 6 at 13:22
add a comment |
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
78.1k64386
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
78.1k64386
edited Jan 6 at 11:11
answered Jan 6 at 11:06
Dietrich BurdeDietrich Burde
78.1k64386
answered Jan 6 at 11:06
Dietrich BurdeDietrich Burde
78.1k64386
answered Jan 6 at 11:06
Dietrich BurdeDietrich Burde
78.1k64386
78.1k64386
Thanks! but the nearest $2times 3^k$ is 39366, which is not so close
– Kaiyi Zhang
Jan 6 at 12:32
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.
– Dietrich Burde
Jan 6 at 12:36
Thanks, that's helpful.
– Kaiyi Zhang
Jan 6 at 13:22
add a comment |
Thanks! but the nearest $2times 3^k$ is 39366, which is not so close
– Kaiyi Zhang
Jan 6 at 12:32
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.
– Dietrich Burde
Jan 6 at 12:36
Thanks, that's helpful.
– Kaiyi Zhang
Jan 6 at 13:22
Thanks! but the nearest $2times 3^k$ is 39366, which is not so close
– Kaiyi Zhang
Jan 6 at 12:32
Thanks! but the nearest $2times 3^k$ is 39366, which is not so close
– Kaiyi Zhang
Jan 6 at 12:32
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.
– Dietrich Burde
Jan 6 at 12:36
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.
– Dietrich Burde
Jan 6 at 12:36
Thanks, that's helpful.
– Kaiyi Zhang
Jan 6 at 13:22
Thanks, that's helpful.
– Kaiyi Zhang
Jan 6 at 13:22
add a comment |
Good question. Some large irreducibles might be tabulated somewhere.
– Wuestenfux
Jan 6 at 10:26
Do you need many such polynomials, or just a few?
– MJD
Jan 6 at 10:52