Commutative Presemifields and Semifields: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
=Background= | |||
For a prime <math>p</math> and a positive integer <math>n</math> let <math>\mathbb{F}_{p^n}</math> be the finite field with <math>p^n</math> elements. | |||
Let <math>F</math> be a map from the finite field to itself. | |||
Such function admits a unique representation as a polynomial of degree at most <math>p^n-1</math>, i.e. | |||
<math>F(x)=\sum_{j=0}^{p^n-1}a_jx^j, a_j\in\mathbb{F}_{p^n}</math>. | |||
The function <math>F</math> is | |||
* <span class="definition">linear</span> if <math>F(x)=\sum_{j=0}^{n-1}a_jx^{p^j} </math>, | |||
* <span class="definition">affine</span> if it is the sum of a linear function and a constant, | |||
* <span class="definition">DO</span> (Dembowski-Ostrim) polynomial if <math>F(x)=\sum_{0\le i\le j<n}a_{ij}x^{p^i+p^j} </math>, | |||
* <span class="definition">quadratic</span> if it is the sum of a DO polynomial and an affine function. | |||
For <math>\delta</math> a positive integer, the function <math>F</math> is called <span class="definition">differentially <math>\delta</math>-uniform</span> if for any pairs <math>a,b\in\mathbb{F}_{p^n}</math>, with <math>a\ne0</math>, the equation <math>F(x+a)-F(x)=b</math> admits at most <math>\delta</math> solutions. | |||
A function <math>F</math> is called planar or perfect nonlinear (PN) if <math>\delta_F=1</math>. | |||
Obviously such functions exist only for <math>p</math> an odd prime. | |||
In the even case the smallest possible case for <math>\delta</math> is two ([[differential uniformity|APN]] function). | |||
For planar function we have that the all the nonzero derivatives, <math>D_aF(x)=F(x+a)-F(x)</math>, are permutations. | |||
==Equivalence Relations== | |||
Two functions <math>F</math> and <math>F'</math> from <math>\mathbb{F}_{p^n}</math> to itself are called: | |||
*<span class="definition">affine equivalent</span> if <math>F'=A_1\circ F\circ A_2</math>, where <math>A_1,A_2</math> are affine permutations; | |||
*<span class="definition">EA-equivalent</span> (extended-affine) if <math>F'=F''+A</math>, where <math>A</math> is affine and <math>F''</math> is afffine equivalent to <math>F</math>; | |||
*<span class="definition">CCZ-equivalent</span> if there exists an affine permutation <math>\mathcal{L}</math> of <math>\mathbb{F}_{p^n}\times\mathbb{F}_{p^n}</math> such that <math>\mathcal{L}(G_F)=G_{F'}</math>, where <math>G_F=\lbrace (x,F(x)) : x\in\mathbb{F}_{p^n}\rbrace</math>. | |||
CCZ-equivalence is the most general known equivalence relation for functions which preserves differential uniformity. Affine and EA-equivalence are its particular cases. | |||
For the case of quadratic planar functions the <span class="definition">isotopic equivalence</span> is more general than CCZ-equivalence, where two maps are isotopic equivalent if the corresponding presemifields are isotopic. | |||
=On Presemifields and Semifields= | |||
A <span class="definition">presemifield</span> is a ring with left and right distributivity and with no zero divisor. | A <span class="definition">presemifield</span> is a ring with left and right distributivity and with no zero divisor. | ||
A presemifield with a multiplicative identity is called a <span class="definition">semifield</span>. | A presemifield with a multiplicative identity is called a <span class="definition">semifield</span>. | ||
| Line 8: | Line 37: | ||
<math>T(x\star y)=M(x)\circ N(y)</math>, | <math>T(x\star y)=M(x)\circ N(y)</math>, | ||
for any <math>x,y\in\mathbb{F}_{p^n}</math>. If <math>M=N</math> then they are called <span class="definition">strongly isotopic</span>. | for any <math>x,y\in\mathbb{F}_{p^n}</math>. If <math>M=N</math> then they are called <span class="definition">strongly isotopic</span>. | ||
Each commutative presemifields of odd order defines a | Each commutative presemifields of odd order defines a planar DO polynomial and viceversa: | ||
* given <math>\mathbb{S}=(\mathbb{F}_{p^n},+,\star)</math> let <math>F_\mathbb{S}(x)=\frac{1}{2}(x\star x)</math>; | * given <math>\mathbb{S}=(\mathbb{F}_{p^n},+,\star)</math> let <math>F_\mathbb{S}(x)=\frac{1}{2}(x\star x)</math>; | ||
* given <math>F</math> let <math>\mathbb{S}_F=(\mathbb{F}_{p^n},+,\star)</math> defined by <math>x\star y=F(x+y)-F(x)-F(y)</math>. | * given <math>F</math> let <math>\mathbb{S}_F=(\mathbb{F}_{p^n},+,\star)</math> defined by <math>x\star y=F(x+y)-F(x)-F(y)</math>. | ||
Revision as of 14:08, 29 August 2019
Background
For a prime Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} and a positive integer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{p^n}} be the finite field with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p^n} elements. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} be a map from the finite field to itself. Such function admits a unique representation as a polynomial of degree at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p^n-1} , i.e.
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(x)=\sum_{j=0}^{p^n-1}a_jx^j, a_j\in\mathbb{F}_{p^n}} .
The function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is
- linear if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(x)=\sum_{j=0}^{n-1}a_jx^{p^j} } ,
- affine if it is the sum of a linear function and a constant,
- DO (Dembowski-Ostrim) polynomial if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(x)=\sum_{0\le i\le j<n}a_{ij}x^{p^i+p^j} } ,
- quadratic if it is the sum of a DO polynomial and an affine function.
For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta} a positive integer, the function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is called differentially Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta} -uniform if for any pairs Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a,b\in\mathbb{F}_{p^n}} , with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\ne0} , the equation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(x+a)-F(x)=b} admits at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta} solutions.
A function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is called planar or perfect nonlinear (PN) if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta_F=1} . Obviously such functions exist only for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} an odd prime. In the even case the smallest possible case for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta} is two (APN function).
For planar function we have that the all the nonzero derivatives, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_aF(x)=F(x+a)-F(x)} , are permutations.
Equivalence Relations
Two functions Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F'} from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{p^n}} to itself are called:
- affine equivalent if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F'=A_1\circ F\circ A_2} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1,A_2} are affine permutations;
- EA-equivalent (extended-affine) if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F'=F''+A} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} is affine and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F''} is afffine equivalent to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} ;
- CCZ-equivalent if there exists an affine permutation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{L}} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{p^n}\times\mathbb{F}_{p^n}} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{L}(G_F)=G_{F'}} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_F=\lbrace (x,F(x)) : x\in\mathbb{F}_{p^n}\rbrace} .
CCZ-equivalence is the most general known equivalence relation for functions which preserves differential uniformity. Affine and EA-equivalence are its particular cases. For the case of quadratic planar functions the isotopic equivalence is more general than CCZ-equivalence, where two maps are isotopic equivalent if the corresponding presemifields are isotopic.
On Presemifields and Semifields
A presemifield is a ring with left and right distributivity and with no zero divisor. A presemifield with a multiplicative identity is called a semifield. Any finite presemifield can be represented by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{S}=(\mathbb{F}_{p^n},+,\star)} , for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} a prime, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} a positive integer, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{S}=(\mathbb{F}_{p^n},+)} additive group and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\star y} multiplication linear in each variable.
Two presemifields Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{S}_1=(\mathbb{F}_{p^n},+,\star)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{S}_2=(\mathbb{F}_{p^n},+,\circ)} are called isotopic if there exist three linear permutations Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T,M,N} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{p^n}} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(x\star y)=M(x)\circ N(y)} , for any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x,y\in\mathbb{F}_{p^n}} . If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M=N} then they are called strongly isotopic. Each commutative presemifields of odd order defines a planar DO polynomial and viceversa:
- given Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{S}=(\mathbb{F}_{p^n},+,\star)} let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_\mathbb{S}(x)=\frac{1}{2}(x\star x)} ;
- given Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{S}_F=(\mathbb{F}_{p^n},+,\star)} defined by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\star y=F(x+y)-F(x)-F(y)} .
Hence two quadratic planar functions Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F,F'} are isotopic equivalent if their corresponding presemifields are isotopic. Moreover, we have:
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F,F'} are CCZ-equivalent if and only if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{S}_F,\mathbb{S}_{F'}} are strongly isotopic;
- for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} odd, isotopic coincides with strongly isotopic;
- if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F,F'} are isotopic equivalent, then there exists a linear map Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F'} is EA-equivalent to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(x+L(x))-F(x)-F(L(x))} .
