<p>When permutation polynomials over finite fields are used as core components of cryptographic algorithms, one step in reducing the hardware area of their secure implementation is to represent them as a composition of permutation polynomials of lower algebraic degree. In this work, we present a criterion for the existence of a class of decompositions of the inverse power function. We use this criterion to show the existence of such decompositions in the finite fields with <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_820_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{2}^{\varvec{n}}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mn mathvariant="bold">2</mn> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> </msup> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_820_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="28" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{2}^{\varvec{2n}}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mn mathvariant="bold">2</mn> </mrow> <mrow> <mn mathvariant="bold">2</mn> <mi mathvariant="bold-italic">n</mi> </mrow> </msup> </math></EquationSource> </InlineEquation> elements when <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_820_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="46" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{2}^{\varvec{n}} \varvec{-1}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mrow> <mn mathvariant="bold">2</mn> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> </msup> <mrow> <mo mathvariant="bold">-</mo> <mn mathvariant="bold">1</mn> </mrow> </mrow> </math></EquationSource> </InlineEquation> is prime. We further present a search algorithm based on the criterion that can produce novel decompositions for some <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_820_Article_IEq4.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="16" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{n}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> </math></EquationSource> </InlineEquation> between <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_820_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{32}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn mathvariant="bold">32</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_820_Article_IEq6.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="31" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{500}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn mathvariant="bold">500</mn> </mrow> </math></EquationSource> </InlineEquation> and improve the length of some known decompositions. Finally, we discuss how to further reduce the number of power functions in the decomposition.</p>

Further existence results of decompositions of permutation polynomials

期刊论文
出版模式：

开放获取
发表日期：

2025年8月23日

查看全文

Samuele Andreoli,
George Petrides

摘要

When permutation polynomials over finite fields are used as core components of cryptographic algorithms, one step in reducing the hardware area of their secure implementation is to represent them as a composition of permutation polynomials of lower algebraic degree. In this work, we present a criterion for the existence of a class of decompositions of the inverse power function. We use this criterion to show the existence of such decompositions in the finite fields with $\varvec{2}^{\varvec{n}}$ $2^{n}$ and $\varvec{2}^{\varvec{2n}}$ $2^{2 n}$ elements when $\varvec{2}^{\varvec{n}} \varvec{-1}$ $2^{n} - 1$ is prime. We further present a search algorithm based on the criterion that can produce novel decompositions for some $\varvec{n}$ $n$ between $\varvec{32}$ $32$ and $\varvec{500}$ $500$ and improve the length of some known decompositions. Finally, we discuss how to further reduce the number of power functions in the decomposition.