# Difference between revisions of "Commutative Presemifields and Semifields"

m |
|||

Line 22: | Line 22: | ||

==Equivalence Relations== | ==Equivalence Relations== | ||

Two functions <math>F</math> and <math>F'</math> from <math>\mathbb{F}_{p^n}</math> to itself are called: | 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 | + | *<span class="definition">affine equivalent</span> if <math>F'=A_1\circ F\circ A_2, 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">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>. | *<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>. |

## Revision as of 14:55, 17 September 2019

# Background

For a prime and a positive integer let be the finite field with elements. Let be a map from the finite field to itself. Such function admits a unique representation as a polynomial of degree at most , i.e.

.

The function is

- linear if ,
- affine if it is the sum of a linear function and a constant,
- DO (Dembowski-Ostrim) polynomial if ,
- quadratic if it is the sum of a DO polynomial and an affine function.

For a positive integer, the function is called differentially -uniform if for any pairs , with , the equation **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F(x+a)-F(x)=b}**
admits at most solutions.

A function is called planar or perfect nonlinear (PN) if . Obviously such functions exist only for an odd prime. In the even case the smallest possible case for is two (APN function).

For planar function we have that the all the nonzero derivatives, , are permutations.

## Equivalence Relations

Two functions and from to itself are called:

- affine equivalent if are affine permutations;
- EA-equivalent (extended-affine) if , where is affine and is afffine equivalent to ;
- CCZ-equivalent if there exists an affine permutation
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal{L}}**of**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{p^n}\times\mathbb{F}_{p^n}}**such that , where .

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 (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb{S}=(\mathbb{F}_{p^n},+,\star)}**
,
for **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p}**
a prime, **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n}**
a positive integer, **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb{S}=(\mathbb{F}_{p^n},+)}**
additive group and **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x\star y}**
multiplication linear in each variable.
Every commutative presemifield can be transformed into a commutative semifield.

Two presemifields **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb{S}_1=(\mathbb{F}_{p^n},+,\star)}**
and **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.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 (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T,M,N}**
of **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{p^n}}**
such that
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T(x\star y)=M(x)\circ N(y)}**
,
for any **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x,y\in\mathbb{F}_{p^n}}**
. If **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.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 (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb{S}=(\mathbb{F}_{p^n},+,\star)}**let**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F_\mathbb{S}(x)=\frac{1}{2}(x\star x)}**; - given
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F}**let**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb{S}_F=(\mathbb{F}_{p^n},+,\star)}**defined by .

Given a finite semifield, the subsets

for all

for all

for all

are called left, middle and right nucleus of .

The set is called the nucleus. All these sets are finite field and, when is commutative, . The order of the different nuclei are invariant under isotopism.

## Properties

Hence two quadratic planar functions are isotopic equivalent if their corresponding presemifields are isotopic. Moreover, we have:

- are CCZ-equivalent if and only if are strongly isotopic;
- for odd, isotopic coincides with strongly isotopic;
- if are isotopic equivalent, then there exists a linear map such that is EA-equivalent to ;
- any commutative presemifield of odd order can generate at most two CCZ-equivalence classes of planar DO polynomials;
- if and are isotopic commutative semifields of characteristic with order of middle nuclei and nuclei and respectively, then either one of the following is satisfied:
- is odd and the semifields are strongly isotopic,
- is even and the semifields are strongly isotopic or the only isotopisms are of the form with non-square.