In classic McEliece cryptosystems, separable quasi-cyclic binary Goppa codes play an important role in reducing the public key size. In this paper, we always assume that <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathbb F_{q^2}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="double-struck">F</mi> <msup> <mi>q</mi> <mn>2</mn> </msup> </msub> </math></EquationSource> </InlineEquation> is a finite field with <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$q=2^{s}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>q</mi> <mo>=</mo> <msup> <mn>2</mn> <mi>s</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$G(x)=x^{q+1}+g x^{q}+g^q x +h\in \mathbb F_{q^{2 }}[x]$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mrow> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msup> <mi>x</mi> <mrow> <mi>q</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> <mo>+</mo> <mi>g</mi> <msup> <mi>x</mi> <mi>q</mi> </msup> <mo>+</mo> <msup> <mi>g</mi> <mi>q</mi> </msup> <mi>x</mi> <mo>+</mo> <mi>h</mi> <mo>∈</mo> <msub> <mi mathvariant="double-struck">F</mi> <msup> <mi>q</mi> <mn>2</mn> </msup> </msub> <mrow> <mo stretchy="false">[</mo> <mi>x</mi> <mo stretchy="false">]</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is a Goppa polynomial. We explicitly describe the complete irreducible factorizations of the polynomial G(x) over <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\mathbb F_{q^2}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="double-struck">F</mi> <msup> <mi>q</mi> <mn>2</mn> </msup> </msub> </math></EquationSource> </InlineEquation>. Let <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$L=\{\alpha \in \mathbb F_{q^2}: G(\alpha )\ne 0\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>L</mi> <mo>=</mo> <mo stretchy="false">{</mo> <mi>α</mi> <mo>∈</mo> <msub> <mi mathvariant="double-struck">F</mi> <msup> <mi>q</mi> <mn>2</mn> </msup> </msub> <mo>:</mo> <mi>G</mi> <mrow> <mo stretchy="false">(</mo> <mi>α</mi> <mo stretchy="false">)</mo> </mrow> <mo>≠</mo> <mn>0</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> be a support set, for <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$h\in \mathbb F_q^*$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>h</mi> <mo>∈</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>q</mi> <mo>∗</mo> </msubsup> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$ h\ne g^{q+1}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>h</mi> <mo>≠</mo> <msup> <mi>g</mi> <mrow> <mi>q</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>, we construct the quasi-dyadic binary extended Goppa code <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\overline{\Gamma }( L, G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover> <mi mathvariant="normal">Γ</mi> <mo>¯</mo> </mover> <mrow> <mo stretchy="false">(</mo> <mi>L</mi> <mo>,</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>; for <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$h\in \mathbb F_{q^2}\backslash \mathbb F_q$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>h</mi> <mo>∈</mo> <msub> <mi mathvariant="double-struck">F</mi> <msup> <mi>q</mi> <mn>2</mn> </msup> </msub> <mrow> <mo stretchy="true">\</mo> </mrow> <msub> <mi mathvariant="double-struck">F</mi> <mi>q</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, we construct the quasi-cyclic binary expurgated Goppa code <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\widetilde{\Gamma }(L, G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mi mathvariant="normal">Γ</mi> <mo stretchy="true">~</mo> </mover> <mrow> <mo stretchy="false">(</mo> <mi>L</mi> <mo>,</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>.

Quasi-cyclic binary extended and expurgated Goppa codes and their parameters

期刊论文
发表日期：

2026年4月9日

查看全文

Fengwei Li,
Xue Jia,
Huan Sun,
Qin Yue

摘要

In classic McEliece cryptosystems, separable quasi-cyclic binary Goppa codes play an important role in reducing the public key size. In this paper, we always assume that $\mathbb F_{q^2}$ $F_{q^{2}}$ is a finite field with $q=2^{s}$ $q = 2^{s}$ and $G(x)=x^{q+1}+g x^{q}+g^q x +h\in \mathbb F_{q^{2 }}[x]$ $G (x) = x^{q + 1} + g x^{q} + g^{q} x + h \in F_{q^{2}} [x]$ is a Goppa polynomial. We explicitly describe the complete irreducible factorizations of the polynomial G(x) over $\mathbb F_{q^2}$ $F_{q^{2}}$ . Let $L=\{\alpha \in \mathbb F_{q^2}: G(\alpha )\ne 0\}$ $L = {α \in F_{q^{2}} : G (α) \neq 0}$ be a support set, for $h\in \mathbb F_q^*$ $h \in F_{q}^{*}$ and $ h\ne g^{q+1}$ $h \neq g^{q + 1}$ , we construct the quasi-dyadic binary extended Goppa code $\overline{\Gamma }( L, G)$ $\bar{Γ} (L, G)$ ; for $h\in \mathbb F_{q^2}\backslash \mathbb F_q$ $h \in F_{q^{2}} \ F_{q}$ , we construct the quasi-cyclic binary expurgated Goppa code $\widetilde{\Gamma }(L, G)$ $\tilde{Γ} (L, G)$ .