<p>We study the nonlinearities of de Bruijn feedback functions and present two results regarding their possible values. First, we show that the maximal nonlinearity of de Bruijn feedback functions is nearly as large as that of bent functions. Specifically, for de Bruijn feedback functions of order <i>n</i>, their maximal nonlinearity is shown to be at least <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$2^{n-1}-2^{\frac{n+1}{2}}\sqrt{n}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mn>2</mn> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msup> <mo>-</mo> <msup> <mn>2</mn> <mfrac> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> <mn>2</mn> </mfrac> </msup> <msqrt> <mi>n</mi> </msqrt> </mrow> </math></EquationSource> </InlineEquation>, compared to <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$2^{n-1}-2^{\frac{n}{2}-1}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mn>2</mn> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msup> <mo>-</mo> <msup> <mn>2</mn> <mrow> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> <mo>-</mo> <mn>1</mn> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> for bent functions. Second, we show that the nonlinearities cover all numbers of the form <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$4r+2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>4</mn> <mi>r</mi> <mo>+</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> between 2 and the maximum value.</p>

Possible values for the nonlinearity of de bruijn feedback functions

期刊论文
发表日期：

2026年3月9日

查看全文

Ming Li,
Yufan Liu,
Yupeng Jiang,
Xiaofang Xu

摘要

We study the nonlinearities of de Bruijn feedback functions and present two results regarding their possible values. First, we show that the maximal nonlinearity of de Bruijn feedback functions is nearly as large as that of bent functions. Specifically, for de Bruijn feedback functions of order n, their maximal nonlinearity is shown to be at least $2^{n-1}-2^{\frac{n+1}{2}}\sqrt{n}$ $2^{n - 1} - 2^{\frac{n + 1}{2}} \sqrt{n}$ , compared to $2^{n-1}-2^{\frac{n}{2}-1}$ $2^{n - 1} - 2^{\frac{n}{2} - 1}$ for bent functions. Second, we show that the nonlinearities cover all numbers of the form $4r+2$ $4 r + 2$ between 2 and the maximum value.