3
$\begingroup$

I am looking for special class of involutive functions (f) with exactly one (zero) fixed point over finite field $F_q$ with properties:

1) $f(f(x))=x$ for any $x \in F_q$ , $f(x)=x$ iff $x=0$

2) For any fixed $a \in F_q$, $a \ne 0$ the following holds:

$f(x+a)-f(x)=g_a(x)$

where $g_a(x_1) \ne g_a(x_2) $ for any $x_1 \ne x_2$, $x_1 \ne -a$ and $x_1 \ne 0$, $x_2 \ne -a$ and $x_2 \ne 0$

and

for any $x \ne -a$ and $x \ne 0$

$g_a(x) \ne a$

EDIT(25 Aug 2019) I'd like to add 3'rd constraint:

3) For any fixed $a \in F_q$, $a \ne 0$ the following holds:

$f(x+a)-x=g_a(x)$

where $g_a(x_1) \ne g_a(x_2) $ for any $x_1 \ne x_2$, $x_1 \ne -a$ and $x_1 \ne 0$, $x_2 \ne -a$ and $x_2 \ne 0$

$\endgroup$
1
  • $\begingroup$ Actually 3'rd constraint directly follows from 1 and 2. $\endgroup$
    – user144684
    Sep 15, 2019 at 9:55

6 Answers 6

5
$\begingroup$

An involution with exactly one fixed point must be over an odd-sized set, so characteristic 2 is ruled out.

By my computation, there are only three such functions for odd prime powers between 3 and 29 inclusive:

  • $f_1: GF(3) \to GF(3)$ given in cycle form as $(0)(12)$
  • $f_2: GF(7) \to GF(7)$ is $(0)(13)(26)(45)$
  • $f_3: GF(7) \to GF(7)$ is $(0)(15)(23)(46)$ (so $f_3(x) = -f_2(-x)$ and there's fundamentally only one solution for $GF(7)$).

However, $GF(31)$ has three pairs:

0, 12, 24, 8, 17, 28, 16, 9, 3, 7, 25, 30, 1, 27, 18, 21, 6, 4, 14, 20, 19, 15, 29, 26, 2, 10, 23, 13, 5, 22, 11
0, 13, 26, 23, 21, 7, 15, 5, 11, 25, 14, 8, 30, 1, 10, 6, 22, 27, 19, 18, 28, 4, 16, 3, 29, 9, 2, 17, 20, 24, 12
0, 14, 28, 5, 25, 3, 10, 16, 19, 24, 6, 23, 20, 30, 1, 22, 7, 18, 17, 8, 12, 27, 15, 11, 9, 4, 29, 21, 2, 26, 13
0, 18, 5, 29, 10, 2, 27, 22, 20, 16, 4, 19, 23, 14, 13, 24, 9, 30, 1, 11, 8, 25, 7, 12, 15, 21, 28, 6, 26, 3, 17
0, 19, 7, 11, 14, 29, 22, 2, 28, 15, 27, 3, 13, 12, 4, 9, 25, 21, 30, 1, 23, 17, 6, 20, 26, 16, 24, 10, 8, 5, 18
0, 20, 9, 26, 18, 8, 21, 29, 5, 2, 16, 12, 11, 17, 27, 25, 10, 13, 4, 30, 1, 6, 24, 28, 22, 15, 3, 14, 23, 7, 19

My search strategy is to enumerate involutions by maintaining a set of unpaired elements, from which I take the smallest and one other, check for failure of injection in any $g_a$, and then recurse.


I note that nothing in the definition (functions which are involutions and perfect nonlinear) relies on the multiplicative structure of $GF(q)$, and the additive structure of $GF(p)$ (for $p$ prime) is just the additive structure of $\mathbb{Z} / p\mathbb{Z}$.

I note that the three fields for which I have found solutions have orders which are Mersenne primes. I therefore extended my search to $\mathbb{Z} / n\mathbb{Z}$ for the Mersenne number $n=15$, and found one pair of solutions:

0, 4, 8, 14, 1, 10, 13, 9, 2, 7, 5, 12, 11, 6, 3
0, 12, 9, 4, 3, 10, 8, 13, 6, 2, 5, 14, 1, 7, 11

I further observe that all of the functions I've found so far are exponential, in the sense that they satisfy $f(2x) = 2f(x)$. By restricting the search to involutions which satisfy this criterion, I am able to extend it to higher Mersenne numbers, finding for $n=63$ the functions

0, 6, 12, 32, 24, 62, 1, 26, 48, 45, 61, 25, 2, 35, 52, 23, 33, 47, 27, 56, 59, 42, 50, 15, 4, 11, 7, 18, 41, 60, 46, 34, 3, 16, 31, 13, 54, 44, 49, 43, 55, 28, 21, 39, 37, 9, 30, 17, 8, 38, 22, 53, 14, 51, 36, 40, 19, 58, 57, 20, 29, 10, 5
0, 8, 16, 53, 32, 38, 43, 62, 1, 45, 13, 51, 23, 10, 61, 44, 2, 41, 27, 34, 26, 42, 39, 12, 46, 30, 20, 18, 59, 48, 25, 35, 4, 58, 19, 31, 54, 57, 5, 22, 52, 17, 21, 6, 15, 9, 24, 49, 29, 47, 60, 11, 40, 3, 36, 56, 55, 37, 33, 28, 50, 14, 7
0, 25, 50, 55, 37, 40, 47, 53, 11, 27, 17, 8, 31, 15, 43, 13, 22, 10, 54, 51, 34, 42, 16, 28, 62, 1, 30, 9, 23, 49, 26, 12, 44, 59, 20, 58, 45, 4, 39, 38, 5, 57, 21, 14, 32, 36, 56, 6, 61, 29, 2, 19, 60, 7, 18, 3, 46, 41, 35, 33, 52, 48, 24
0, 39, 15, 11, 30, 28, 22, 17, 60, 45, 56, 3, 44, 61, 34, 2, 57, 7, 27, 31, 49, 42, 6, 58, 25, 24, 59, 18, 5, 43, 4, 19, 51, 37, 14, 40, 54, 33, 62, 1, 35, 47, 21, 29, 12, 9, 53, 41, 50, 20, 48, 32, 55, 46, 36, 52, 10, 16, 23, 26, 8, 13, 38
0, 56, 49, 13, 35, 30, 26, 8, 7, 27, 60, 23, 52, 3, 16, 34, 14, 39, 54, 48, 57, 42, 46, 11, 41, 58, 6, 9, 32, 44, 5, 59, 28, 38, 15, 4, 45, 43, 33, 17, 51, 24, 21, 37, 29, 36, 22, 61, 19, 2, 53, 40, 12, 50, 18, 62, 1, 20, 25, 31, 10, 47, 55
0, 58, 53, 34, 43, 6, 5, 44, 23, 27, 12, 49, 10, 41, 25, 55, 46, 33, 54, 26, 24, 42, 35, 8, 20, 14, 19, 9, 50, 32, 47, 60, 29, 17, 3, 22, 45, 56, 52, 59, 48, 13, 21, 4, 7, 36, 16, 30, 40, 11, 28, 61, 38, 2, 18, 15, 37, 62, 1, 39, 31, 51, 57

and for $n=127$

0, 7, 14, 63, 28, 54, 126, 1, 56, 90, 108, 87, 125, 55, 2, 31, 112, 43, 53, 29, 89, 57, 47, 82, 123, 105, 110, 66, 4, 19, 62, 15, 97, 77, 86, 109, 106, 46, 58, 100, 51, 75, 114, 17, 94, 68, 37, 22, 119, 122, 83, 40, 93, 18, 5, 13, 8, 21, 38, 104, 124, 88, 30, 3, 67, 95, 27, 64, 45, 107, 91, 79, 85, 78, 92, 41, 116, 33, 73, 71, 102, 118, 23, 50, 101, 72, 34, 11, 61, 20, 9, 70, 74, 52, 44, 65, 111, 32, 117, 103, 39, 84, 80, 99, 59, 25, 36, 69, 10, 35, 26, 96, 16, 115, 42, 113, 76, 98, 81, 48, 121, 120, 49, 24, 60, 12, 6
0, 10, 20, 92, 40, 64, 57, 85, 80, 126, 1, 82, 114, 25, 43, 105, 33, 111, 125, 81, 2, 88, 37, 96, 101, 13, 50, 79, 86, 113, 83, 54, 66, 16, 95, 38, 123, 22, 35, 60, 4, 69, 49, 14, 74, 56, 65, 55, 75, 42, 26, 121, 100, 97, 31, 47, 45, 6, 99, 122, 39, 93, 108, 68, 5, 46, 32, 106, 63, 41, 76, 116, 119, 104, 44, 48, 70, 103, 120, 27, 8, 19, 11, 30, 98, 7, 28, 91, 21, 124, 112, 87, 3, 61, 110, 34, 23, 53, 84, 58, 52, 24, 115, 77, 73, 15, 67, 109, 62, 107, 94, 17, 90, 29, 12, 102, 71, 118, 117, 72, 78, 51, 59, 36, 89, 18, 9
0, 14, 28, 37, 56, 105, 74, 64, 112, 115, 83, 77, 21, 126, 1, 23, 97, 62, 103, 107, 39, 12, 27, 15, 42, 94, 125, 22, 2, 80, 46, 72, 67, 58, 124, 95, 79, 3, 87, 20, 78, 96, 24, 91, 54, 110, 30, 76, 84, 89, 61, 98, 123, 59, 44, 86, 4, 120, 33, 53, 92, 50, 17, 70, 7, 82, 116, 32, 121, 102, 63, 75, 31, 117, 6, 71, 47, 11, 40, 36, 29, 111, 65, 10, 48, 109, 55, 38, 108, 49, 93, 43, 60, 90, 25, 35, 41, 16, 51, 101, 122, 99, 69, 18, 119, 5, 118, 19, 88, 85, 45, 81, 8, 114, 113, 9, 66, 73, 106, 104, 57, 68, 100, 52, 34, 26, 13
0, 19, 38, 13, 76, 62, 26, 44, 25, 63, 124, 97, 52, 3, 88, 84, 50, 119, 126, 1, 121, 99, 67, 47, 104, 8, 6, 59, 49, 85, 41, 66, 100, 79, 111, 96, 125, 120, 2, 53, 115, 30, 71, 58, 7, 105, 94, 23, 81, 28, 16, 55, 12, 39, 118, 51, 98, 122, 43, 27, 82, 92, 5, 9, 73, 70, 31, 22, 95, 112, 65, 42, 123, 64, 113, 87, 4, 93, 106, 33, 103, 48, 60, 90, 15, 29, 116, 75, 14, 91, 83, 89, 61, 77, 46, 68, 35, 11, 56, 21, 32, 107, 110, 80, 24, 45, 78, 101, 109, 108, 102, 34, 69, 74, 117, 40, 86, 114, 54, 17, 37, 20, 57, 72, 10, 36, 18
0, 21, 42, 30, 84, 95, 60, 19, 41, 22, 63, 68, 120, 118, 38, 65, 82, 98, 44, 7, 126, 1, 9, 78, 113, 56, 109, 124, 76, 46, 3, 102, 37, 119, 69, 93, 88, 32, 14, 75, 125, 8, 2, 47, 18, 61, 29, 43, 99, 72, 112, 79, 91, 117, 121, 104, 25, 116, 92, 70, 6, 45, 77, 10, 74, 15, 111, 73, 11, 34, 59, 96, 49, 67, 64, 39, 28, 62, 23, 51, 123, 110, 16, 101, 4, 87, 94, 85, 36, 103, 122, 52, 58, 35, 86, 5, 71, 100, 17, 48, 97, 83, 31, 89, 55, 114, 107, 106, 115, 26, 81, 66, 50, 24, 105, 108, 57, 53, 13, 33, 12, 54, 90, 80, 27, 40, 20
0, 31, 62, 7, 124, 82, 14, 3, 121, 44, 37, 34, 28, 91, 6, 63, 115, 69, 88, 106, 74, 40, 68, 116, 56, 86, 55, 117, 12, 101, 126, 1, 103, 84, 11, 118, 49, 10, 85, 57, 21, 66, 80, 76, 9, 50, 105, 89, 112, 36, 45, 94, 110, 73, 107, 26, 24, 39, 75, 81, 125, 102, 2, 15, 79, 67, 41, 65, 22, 17, 109, 95, 98, 53, 20, 58, 43, 122, 114, 64, 42, 59, 5, 92, 33, 38, 25, 108, 18, 47, 100, 13, 83, 104, 51, 71, 97, 96, 72, 111, 90, 29, 61, 32, 93, 46, 19, 54, 87, 70, 52, 99, 48, 119, 78, 16, 23, 27, 35, 113, 123, 8, 77, 120, 4, 60, 30
0, 39, 78, 109, 29, 104, 91, 101, 58, 74, 81, 27, 55, 80, 75, 107, 116, 41, 21, 63, 35, 18, 54, 28, 110, 123, 33, 11, 23, 4, 87, 90, 105, 26, 82, 20, 42, 68, 126, 1, 70, 17, 36, 115, 108, 79, 56, 60, 93, 51, 119, 49, 66, 62, 22, 12, 46, 97, 8, 96, 47, 113, 53, 19, 83, 118, 52, 114, 37, 77, 40, 117, 84, 95, 9, 14, 125, 69, 2, 45, 13, 10, 34, 64, 72, 121, 103, 30, 89, 88, 31, 6, 112, 48, 120, 73, 59, 57, 102, 122, 111, 7, 98, 86, 5, 32, 124, 15, 44, 3, 24, 100, 92, 61, 67, 43, 16, 71, 65, 50, 94, 85, 99, 25, 106, 76, 38
0, 41, 82, 73, 37, 111, 19, 36, 74, 97, 95, 110, 38, 121, 72, 83, 21, 28, 67, 6, 63, 16, 93, 102, 76, 48, 115, 92, 17, 120, 39, 81, 42, 123, 56, 62, 7, 4, 12, 30, 126, 1, 32, 107, 59, 47, 77, 45, 25, 109, 96, 75, 103, 61, 57, 69, 34, 54, 113, 44, 78, 53, 35, 20, 84, 100, 119, 18, 112, 55, 124, 105, 14, 3, 8, 51, 24, 46, 60, 104, 125, 31, 2, 15, 64, 117, 87, 86, 118, 101, 94, 98, 27, 22, 90, 10, 50, 9, 91, 116, 65, 89, 23, 52, 79, 71, 122, 43, 114, 49, 11, 5, 68, 58, 108, 26, 99, 85, 88, 66, 29, 13, 106, 33, 70, 80, 40
0, 55, 110, 88, 93, 97, 49, 20, 59, 25, 67, 48, 98, 120, 40, 81, 118, 19, 50, 17, 7, 83, 96, 94, 69, 9, 113, 63, 80, 41, 35, 53, 109, 56, 38, 30, 100, 116, 34, 42, 14, 29, 39, 121, 65, 103, 61, 75, 11, 6, 18, 119, 99, 31, 126, 1, 33, 117, 82, 8, 70, 46, 106, 27, 91, 44, 112, 10, 76, 24, 60, 104, 73, 72, 105, 47, 68, 95, 84, 90, 28, 15, 58, 21, 78, 124, 115, 101, 3, 123, 79, 64, 122, 4, 23, 77, 22, 5, 12, 52, 36, 87, 111, 45, 71, 74, 62, 114, 125, 32, 2, 102, 66, 26, 107, 86, 37, 57, 16, 51, 13, 43, 92, 89, 85, 108, 54
0, 73, 19, 42, 38, 35, 84, 114, 76, 111, 70, 90, 41, 20, 101, 61, 25, 125, 95, 2, 13, 65, 53, 56, 82, 16, 40, 91, 75, 115, 122, 105, 50, 104, 123, 5, 63, 48, 4, 124, 26, 12, 3, 49, 106, 69, 112, 99, 37, 43, 32, 59, 80, 22, 55, 54, 23, 67, 103, 51, 117, 15, 83, 36, 100, 21, 81, 57, 119, 45, 10, 94, 126, 1, 96, 28, 8, 109, 121, 116, 52, 66, 24, 62, 6, 88, 98, 113, 85, 93, 11, 27, 97, 89, 71, 18, 74, 92, 86, 47, 64, 14, 118, 58, 33, 31, 44, 120, 110, 77, 108, 9, 46, 87, 7, 29, 79, 60, 102, 68, 107, 78, 30, 34, 39, 17, 72
0, 87, 47, 57, 94, 21, 114, 98, 61, 39, 42, 28, 101, 19, 69, 59, 122, 116, 78, 13, 84, 5, 56, 48, 75, 104, 38, 62, 11, 36, 118, 77, 117, 37, 105, 100, 29, 33, 26, 9, 41, 40, 10, 63, 112, 125, 96, 2, 23, 67, 81, 103, 76, 119, 124, 113, 22, 3, 72, 15, 109, 8, 27, 43, 107, 92, 74, 49, 83, 14, 73, 93, 58, 70, 66, 24, 52, 31, 18, 102, 82, 50, 80, 68, 20, 95, 126, 1, 97, 115, 123, 120, 65, 71, 4, 85, 46, 88, 7, 110, 35, 12, 79, 51, 25, 34, 111, 64, 121, 60, 99, 106, 44, 55, 6, 89, 17, 32, 30, 53, 91, 108, 16, 90, 54, 45, 86
0, 89, 51, 21, 102, 28, 42, 33, 77, 62, 56, 111, 84, 60, 66, 35, 27, 103, 124, 83, 112, 3, 95, 122, 41, 29, 120, 16, 5, 25, 70, 68, 54, 7, 79, 15, 121, 96, 39, 38, 97, 24, 6, 55, 63, 93, 117, 114, 82, 125, 58, 2, 113, 118, 32, 43, 10, 87, 50, 90, 13, 75, 9, 44, 108, 74, 14, 80, 31, 119, 30, 81, 115, 105, 65, 61, 78, 8, 76, 34, 67, 71, 48, 19, 12, 91, 110, 57, 126, 1, 59, 85, 107, 45, 101, 22, 37, 40, 123, 104, 116, 94, 4, 17, 99, 73, 109, 92, 64, 106, 86, 11, 20, 52, 47, 72, 100, 46, 53, 69, 26, 36, 23, 98, 18, 49, 88
0, 97, 67, 123, 7, 50, 119, 4, 14, 92, 100, 104, 111, 49, 8, 79, 28, 75, 57, 40, 73, 108, 81, 34, 95, 66, 98, 37, 16, 55, 31, 30, 56, 76, 23, 44, 114, 27, 80, 109, 19, 102, 89, 94, 35, 122, 68, 85, 63, 13, 5, 84, 69, 107, 74, 29, 32, 18, 110, 105, 62, 86, 60, 48, 112, 125, 25, 2, 46, 52, 88, 103, 101, 20, 54, 17, 33, 82, 91, 15, 38, 22, 77, 118, 51, 47, 61, 106, 70, 42, 117, 78, 9, 116, 43, 24, 126, 1, 26, 115, 10, 72, 41, 71, 11, 59, 87, 53, 21, 39, 58, 12, 64, 121, 36, 99, 93, 90, 83, 6, 124, 113, 45, 3, 120, 65, 96
0, 107, 87, 100, 47, 37, 73, 115, 94, 114, 74, 70, 19, 22, 103, 77, 61, 46, 101, 12, 21, 20, 13, 72, 38, 96, 44, 30, 79, 110, 27, 56, 122, 41, 92, 69, 75, 5, 24, 91, 42, 33, 40, 123, 26, 111, 17, 4, 76, 104, 65, 99, 88, 63, 60, 78, 31, 68, 93, 116, 54, 16, 112, 53, 117, 50, 82, 121, 57, 35, 11, 102, 23, 6, 10, 36, 48, 15, 55, 28, 84, 98, 66, 109, 80, 125, 119, 2, 52, 113, 95, 39, 34, 58, 8, 90, 25, 124, 81, 51, 3, 18, 71, 14, 49, 118, 126, 1, 120, 83, 29, 45, 62, 89, 9, 7, 59, 64, 105, 86, 108, 67, 32, 43, 97, 85, 106
0, 109, 91, 117, 55, 70, 107, 90, 110, 73, 13, 41, 87, 10, 53, 58, 93, 25, 19, 18, 26, 49, 82, 103, 47, 17, 20, 95, 106, 71, 116, 92, 59, 81, 50, 66, 38, 44, 36, 113, 52, 11, 98, 112, 37, 67, 79, 24, 94, 21, 34, 123, 40, 14, 63, 4, 85, 62, 15, 32, 105, 96, 57, 54, 118, 122, 35, 45, 100, 84, 5, 29, 76, 9, 88, 115, 72, 111, 99, 46, 104, 33, 22, 120, 69, 56, 97, 12, 74, 125, 7, 2, 31, 16, 48, 27, 61, 86, 42, 78, 68, 121, 119, 23, 80, 60, 28, 6, 126, 1, 8, 77, 43, 39, 124, 75, 30, 3, 64, 102, 83, 101, 65, 51, 114, 89, 108
0, 114, 101, 93, 75, 27, 59, 70, 23, 21, 54, 61, 118, 14, 13, 119, 46, 82, 42, 39, 108, 9, 122, 8, 109, 58, 28, 5, 26, 76, 111, 86, 92, 102, 37, 67, 84, 34, 78, 19, 89, 72, 18, 79, 117, 62, 16, 98, 91, 87, 116, 80, 56, 121, 10, 96, 52, 64, 25, 6, 95, 11, 45, 120, 57, 110, 77, 35, 74, 94, 7, 123, 41, 83, 68, 4, 29, 66, 38, 43, 51, 97, 17, 73, 36, 103, 31, 49, 107, 40, 124, 48, 32, 3, 69, 60, 55, 81, 47, 125, 105, 2, 33, 85, 112, 100, 115, 88, 20, 24, 65, 30, 104, 126, 1, 106, 50, 44, 12, 15, 63, 53, 22, 71, 90, 99, 113
0, 118, 109, 38, 91, 68, 76, 49, 55, 10, 9, 56, 25, 115, 98, 37, 110, 33, 20, 65, 18, 60, 112, 54, 50, 12, 103, 75, 69, 43, 74, 104, 93, 17, 66, 124, 40, 15, 3, 106, 36, 99, 120, 29, 97, 116, 108, 119, 100, 7, 24, 57, 79, 83, 23, 8, 11, 51, 86, 64, 21, 95, 81, 122, 59, 19, 34, 88, 5, 28, 121, 82, 80, 96, 30, 27, 6, 101, 85, 52, 72, 62, 71, 53, 113, 78, 58, 123, 67, 92, 105, 4, 89, 32, 111, 61, 73, 44, 14, 41, 48, 77, 114, 26, 31, 90, 39, 125, 46, 2, 16, 94, 22, 84, 102, 13, 45, 126, 1, 47, 42, 70, 63, 87, 35, 107, 117
0, 121, 115, 67, 103, 78, 7, 6, 79, 46, 29, 51, 14, 85, 12, 111, 31, 101, 92, 117, 58, 91, 102, 68, 28, 47, 43, 88, 24, 10, 95, 16, 62, 83, 75, 53, 57, 118, 107, 66, 116, 93, 55, 26, 77, 104, 9, 25, 56, 54, 94, 11, 86, 35, 49, 42, 48, 36, 20, 82, 63, 100, 32, 60, 124, 97, 39, 3, 23, 89, 106, 119, 114, 122, 109, 34, 87, 44, 5, 8, 105, 90, 59, 33, 110, 13, 52, 76, 27, 69, 81, 21, 18, 41, 50, 30, 112, 65, 108, 123, 61, 17, 22, 4, 45, 80, 70, 38, 98, 74, 84, 15, 96, 125, 72, 2, 40, 19, 37, 71, 126, 1, 73, 99, 64, 113, 120

I think there is starting to be sufficient evidence to conjecture that all Mersenne numbers $n$ will have involutive perfect nonlinear exponential functions over $\mathbb{Z}/n\mathbb{Z}$, and for Mersenne primes these will be involutive perfect nonlinear functions over $GF(n)$.

$\endgroup$
14
  • $\begingroup$ Good idea to use algorithmic approach, great results !!! I tried to find using mathematical abstractions. $\endgroup$
    – user144684
    Aug 22, 2019 at 9:54
  • $\begingroup$ Incidentally, since there's no use of multiplication in the definition of these functions, it just occurred to me to try searching for suitable functions over $Z_{15}$, and there is one pair, with representative $0(1,4)(2,8)(3,14)(5,10)(6,13)(7,9)(11,12)$. $\endgroup$ Aug 22, 2019 at 10:15
  • $\begingroup$ Hmm. These examples are all exponential (specifically, $f(2x) = 2f(x)$). I should be able to enumerate exponential functions much more efficiently, so I can check whether this class extends to $GF(127)$... $\endgroup$ Aug 22, 2019 at 10:29
  • $\begingroup$ Little note: all of such functions produces starter. I'd give the name for such starter. $\endgroup$
    – user144684
    Aug 22, 2019 at 10:33
  • $\begingroup$ Amazing result !! $\endgroup$
    – user144684
    Aug 22, 2019 at 16:32
2
$\begingroup$

What you are looking for are called perfect nonlinear or differentially $1-$uniform functions.

They don't exist over even characteristic since if $x_0$ satisfies $$ f(x+a)-f(x)=b, $$ so does $x_0+a.$

For a long time only some power functions or functions equivalent to them were known. A recent paper lists the following known examples among others.

$$x^2~~ in ~~GF(p^n), $$

$$x^{p^k+1} ~~in ~~GF(p^n),\quad k \leq n/2~~and ~~n/(k,n)~~odd$$

$$x^{10} + x^6 − x^2 ~~in~~ GF(3^n), ~~n \geq 5 ~~odd$$

See New families of perfect nonlinear polynomial functions by Zhengbang Zha, Xueli Wang, Journal of Algebra (322):3912-3918.

for more. One class of such polynomials are called Dembowski-Ostrom polynomials. All of the above are, but a recent example $$x^{(3^k+1 )/2}$$ isn't.

Edit: I apologise, I shouldn't post before my morning coffee. This is now essentially a long comment.

The functions displayed are not involutions. Recent work on involutions is here. I think your question is quite difficult.

$\endgroup$
3
  • $\begingroup$ You mentioned x^2 \in GF(p^n) . is it involution for any field of odd characteristic ? $\endgroup$
    – user144684
    Aug 21, 2019 at 5:55
  • $\begingroup$ I need special involutions among perfect nonlinear or differentially 1−uniform functions $\endgroup$
    – user144684
    Aug 21, 2019 at 8:26
  • 1
    $\begingroup$ I tried to find these functions last 3 years :) I was aware about described papers and types of functions. I know that this question is very difficult :) $\endgroup$
    – user144684
    Aug 21, 2019 at 12:33
0
$\begingroup$

Taking into account Peter's Tailor analysis I can say the following. For example we have finite field $GF(p)$ for $p$ prime;

We can take element $2$ and obtain subgroup generated by $2$: $<2>$. This subgroup generates set of cosets:

$<2>$, $C_1<2>$ .... $C_{K-1}<2>$

where $k=(|GF^*(p)|/(|<2>|))$.

So exponential functions means that

f($C_i<2>$) = $C_j<2>$

and we have involution of cosets (taking into account that their number is even)

$(i_1,j_1),...,(i_r,j_r)$.

Plus we have the following condition:

for any two cosets $i,j$ if $(a,b)\in C_i<2>$, $(f(a),f(b))\in C_j<2>$

we have: $a/b$=$f(a)/f(b)$.

So we can iterate over all involutions on the set of such Cosets and iterate over corresponding mapping for each pair of cosets.

$\endgroup$
3
  • $\begingroup$ The biggest questions is: how to describe cosets mapping to get such functions. We dive to the Cyclotomy of Finite Field. $\endgroup$
    – user144684
    Aug 28, 2019 at 9:48
  • $\begingroup$ This is a place where I stuck and can't find solution. $\endgroup$
    – user144684
    Aug 28, 2019 at 9:48
  • $\begingroup$ 3'rd constraint works for 0, 12, 24, 8, 17, 28, 16, 9, 3, 7, 25, 30, 1, 27, 18, 21, 6, 4, 14, 20, 19, 15, 29, 26, 2, 10, 23, 13, 5, 22, 11 $\endgroup$
    – user144684
    Sep 14, 2019 at 3:48
0
$\begingroup$

$GF(31)$:

all these involutions satisfy all 3 constraints:

0, 12, 24, 8, 17, 28, 16, 9, 3, 7, 25, 30, 1, 27, 18, 21, 6, 4, 14, 20, 19, 15, 29, 26, 2, 10, 23, 13, 5, 22, 11

0, 13, 26, 23, 21, 7, 15, 5, 11, 25, 14, 8, 30, 1, 10, 6, 22, 27, 19, 18, 28, 4, 16, 3, 29, 9, 2, 17, 20, 24, 12

0, 14, 28, 5, 25, 3, 10, 16, 19, 24, 6, 23, 20, 30, 1, 22, 7, 18, 17, 8, 12, 27, 15, 11, 9, 4, 29, 21, 2, 26, 13

0, 18, 5, 29, 10, 2, 27, 22, 20, 16, 4, 19, 23, 14, 13, 24, 9, 30, 1, 11, 8, 25, 7, 12, 15, 21, 28, 6, 26, 3, 17

0, 19, 7, 11, 14, 29, 22, 2, 28, 15, 27, 3, 13, 12, 4, 9, 25, 21, 30, 1, 23, 17, 6, 20, 26, 16, 24, 10, 8, 5, 18

0, 20, 9, 26, 18, 8, 21, 29, 5, 2, 16, 12, 11, 17, 27, 25, 10, 13, 4, 30, 1, 6, 24, 28, 22, 15, 3, 14, 23, 7, 19

$\endgroup$
0
$\begingroup$

$Z/255Z$:

    $0, 16, 32, 220, 64, 41, 185, 101, 128, 190, 82, 69, 115, 212, 202, 254, 1, 204, 125, 145, 164, 44, 138, 234, 230, 49, 169, 177, 149, 122, 253, 203, 2, 215, 153, 38, 250, 160, 35, 180, 73, 5, 88, 56, 21, 201, 213, 124, 205, 25, 98, 68, 83, 67, 99, 192, 43, 165, 244, 159, 251, 142, 151, 118, 4, 74, 175, 53, 51, 11, 76, 158, 245, 40, 65, 114, 70, 208, 105, 163, 146, 194, 10, 52, 176, 170, 112, 184, 42, 193, 147, 111, 171, 226, 248, 132, 155, 168, 50, 54, 196, 7, 136, 243, 166, 78, 134, 237, 198, 189, 129, 91, 86, 174, 75, 12, 233, 139, 63, 221, 247, 227, 29, 218, 47, 18, 236, 135, 8, 110, 148, 178, 95, 162, 106, 127, 102, 200, 22, 117, 152, 216, 61, 229, 235, 19, 80, 90, 130, 28, 228, 62, 140, 34, 161, 96, 210, 207, 71, 59, 37, 154, 133, 79, 20, 57, 104, 209, 97, 26, 85, 92, 224, 183, 113, 66, 84, 27, 131, 249, 39, 246, 222, 173, 87, 6, 197, 238, 241, 109, 9, 195, 55, 89, 81, 191, 100, 186, 108, 242, 137, 45, 14, 31, 17, 48, 231, 157, 77, 167, 156, 232, 13, 46, 219, 33, 141, 252, 123, 214, 3, 119, 182, 225, 172, 223, 93, 121, 150, 143, 24, 206, 211, 116, 23, 144, 126, 107, 187, 240, 239, 188, 199, 103, 58, 72, 181, 120, 94, 179, 36, 60, 217, 30, 15$
    $0, 134, 13, 210, 26, 143, 165, 87, 52, 148, 31, 253, 75, 2, 174, 152, 104, 68, 41, 225, 62, 245, 251, 237, 150, 202, 4, 110, 93, 218, 49, 10, 208, 146, 136, 89, 82, 66, 195, 154, 124, 18, 235, 100, 247, 48, 219, 79, 45, 30, 149, 238, 8, 78, 220, 141, 186, 212, 181, 179, 98, 188, 20, 243, 161, 227, 37, 128, 17, 125, 178, 182, 164, 144, 132, 12, 135, 147, 53, 47, 248, 95, 36, 228, 215, 170, 200, 7, 239, 35, 96, 163, 183, 28, 158, 81, 90, 191, 60, 205, 43, 140, 221, 118, 16, 129, 156, 116, 185, 142, 27, 184, 117, 222, 169, 216, 107, 112, 103, 153, 196, 122, 121, 197, 40, 69, 231, 194, 67, 105, 199, 171, 74, 254, 1, 76, 34, 240, 250, 246, 101, 55, 109, 5, 73, 172, 33, 77, 9, 50, 24, 167, 15, 119, 39, 198, 106, 217, 94, 249, 241, 64, 190, 91, 72, 6, 201, 151, 175, 114, 85, 131, 145, 209, 14, 168, 223, 230, 70, 59, 192, 58, 71, 92, 111, 108, 56, 204, 61, 226, 162, 97, 180, 213, 127, 38, 120, 123, 155, 130, 86, 166, 25, 211, 187, 99, 236, 252, 32, 173, 3, 203, 57, 193, 232, 84, 115, 157, 29, 46, 54, 102, 113, 176, 234, 19, 189, 65, 83, 233, 177, 126, 214, 229, 224, 42, 206, 23, 51, 88, 137, 160, 244, 63, 242, 21, 139, 44, 80, 159, 138, 22, 207, 11, 133$
    $0, 13, 26, 191, 52, 71, 127, 89, 104, 235, 142, 176, 254, 1, 178, 186, 208, 68, 215, 220, 29, 81, 97, 183, 253, 177, 2, 145, 101, 20, 117, 74, 161, 125, 136, 54, 175, 143, 185, 179, 58, 124, 162, 224, 194, 167, 111, 63, 251, 205, 99, 238, 4, 109, 35, 196, 202, 157, 40, 114, 234, 105, 148, 47, 67, 209, 250, 64, 17, 84, 108, 5, 95, 227, 31, 233, 115, 91, 103, 90, 116, 21, 248, 214, 69, 170, 193, 225, 133, 7, 79, 77, 222, 135, 126, 72, 247, 22, 155, 50, 198, 28, 221, 78, 8, 61, 218, 169, 70, 53, 137, 46, 149, 123, 59, 76, 80, 30, 228, 153, 213, 249, 210, 113, 41, 33, 94, 6, 134, 223, 163, 172, 245, 88, 128, 93, 34, 110, 168, 219, 216, 200, 10, 37, 190, 27, 199, 217, 62, 112, 211, 159, 230, 119, 182, 98, 206, 57, 180, 151, 232, 32, 42, 130, 241, 244, 173, 45, 138, 107, 85, 240, 131, 166, 195, 36, 11, 25, 14, 39, 158, 212, 154, 23, 189, 38, 15, 204, 252, 184, 144, 3, 239, 86, 44, 174, 55, 237, 100, 146, 141, 236, 56, 207, 187, 49, 156, 203, 16, 65, 122, 150, 181, 120, 83, 18, 140, 147, 106, 139, 19, 102, 92, 129, 43, 87, 246, 73, 118, 231, 152, 229, 160, 75, 60, 9, 201, 197, 51, 192, 171, 164, 243, 242, 165, 132, 226, 96, 82, 121, 66, 48, 188, 24, 12$
    $0, 240, 225, 38, 195, 219, 76, 161, 135, 74, 183, 197, 152, 56, 67, 16, 15, 68, 148, 129, 111, 232, 139, 44, 49, 231, 112, 105, 134, 162, 32, 83, 30, 73, 136, 252, 41, 132, 3, 114, 222, 36, 209, 242, 23, 99, 88, 178, 98, 24, 207, 238, 224, 241, 210, 118, 13, 147, 69, 155, 64, 174, 166, 200, 60, 246, 146, 14, 17, 58, 249, 168, 82, 33, 9, 216, 6, 124, 228, 171, 189, 142, 72, 31, 163, 170, 229, 158, 46, 151, 198, 235, 176, 122, 101, 218, 196, 184, 48, 45, 159, 94, 221, 115, 193, 27, 227, 125, 165, 175, 236, 20, 26, 194, 39, 103, 138, 233, 55, 153, 128, 149, 93, 160, 77, 107, 145, 247, 120, 19, 237, 208, 37, 226, 28, 8, 34, 192, 116, 22, 243, 180, 81, 169, 164, 126, 66, 57, 18, 121, 177, 89, 12, 119, 248, 59, 201, 205, 87, 100, 123, 7, 29, 84, 144, 108, 62, 213, 71, 143, 85, 79, 203, 245, 61, 109, 92, 150, 47, 185, 141, 190, 215, 10, 97, 179, 244, 204, 202, 80, 181, 251, 137, 104, 113, 4, 96, 11, 90, 212, 63, 156, 188, 172, 187, 157, 230, 50, 131, 42, 54, 234, 199, 167, 250, 182, 75, 220, 95, 5, 217, 102, 40, 253, 52, 2, 133, 106, 78, 86, 206, 25, 21, 117, 211, 91, 110, 130, 51, 254, 1, 53, 43, 140, 186, 173, 65, 127, 154, 70, 214, 191, 35, 223, 239$
    $0, 197, 139, 50, 23, 66, 100, 171, 46, 20, 132, 246, 200, 220, 87, 169, 92, 68, 40, 251, 9, 214, 237, 4, 145, 129, 185, 177, 174, 157, 83, 148, 184, 130, 136, 48, 80, 199, 247, 180, 18, 62, 173, 178, 219, 201, 8, 252, 35, 191, 3, 238, 115, 225, 99, 67, 93, 165, 59, 58, 166, 250, 41, 203, 113, 144, 5, 55, 17, 181, 96, 103, 160, 241, 143, 114, 239, 120, 105, 190, 36, 109, 124, 30, 91, 170, 101, 14, 183, 149, 147, 84, 16, 56, 249, 167, 70, 222, 127, 54, 6, 86, 221, 71, 230, 78, 195, 138, 198, 81, 134, 176, 186, 64, 75, 52, 118, 224, 116, 153, 77, 231, 245, 133, 82, 158, 151, 98, 226, 25, 33, 213, 10, 123, 110, 212, 34, 253, 107, 2, 192, 216, 206, 74, 65, 24, 227, 90, 31, 89, 228, 126, 223, 119, 240, 161, 210, 29, 125, 229, 72, 155, 218, 179, 248, 57, 60, 95, 182, 15, 85, 7, 202, 42, 28, 211, 111, 27, 43, 163, 39, 69, 168, 88, 32, 26, 112, 204, 243, 194, 79, 49, 140, 234, 189, 106, 254, 1, 108, 37, 12, 45, 172, 63, 187, 208, 142, 242, 205, 217, 156, 175, 135, 131, 21, 233, 141, 209, 162, 44, 13, 102, 97, 152, 117, 53, 128, 146, 150, 159, 104, 121, 236, 215, 193, 244, 232, 22, 51, 76, 154, 73, 207, 188, 235, 122, 11, 38, 164, 94, 61, 19, 47, 137, 196$
    $0, 23, 46, 106, 92, 36, 212, 222, 184, 65, 72, 127, 169, 70, 189, 186, 113, 204, 130, 178, 144, 81, 254, 1, 83, 52, 140, 230, 123, 61, 117, 250, 226, 40, 153, 134, 5, 210, 101, 94, 33, 150, 162, 49, 253, 82, 2, 147, 166, 43, 104, 68, 25, 129, 205, 216, 246, 242, 122, 231, 234, 29, 245, 217, 197, 9, 80, 145, 51, 84, 13, 79, 10, 180, 165, 148, 202, 96, 188, 71, 66, 21, 45, 24, 69, 170, 98, 225, 251, 137, 164, 181, 4, 135, 39, 227, 77, 239, 86, 220, 208, 38, 136, 252, 50, 146, 3, 182, 155, 214, 177, 131, 237, 16, 229, 141, 244, 30, 207, 221, 213, 156, 58, 28, 235, 143, 179, 11, 139, 53, 18, 111, 160, 191, 35, 93, 102, 89, 168, 128, 26, 115, 158, 125, 20, 67, 105, 47, 75, 152, 41, 201, 149, 34, 192, 108, 121, 243, 142, 236, 132, 200, 42, 167, 90, 74, 48, 163, 138, 12, 85, 240, 196, 218, 195, 241, 247, 110, 19, 126, 73, 91, 107, 193, 8, 198, 15, 238, 78, 14, 199, 133, 154, 183, 223, 174, 172, 64, 185, 190, 161, 151, 76, 228, 17, 54, 249, 118, 100, 211, 37, 209, 6, 120, 109, 248, 55, 63, 173, 224, 99, 119, 7, 194, 219, 87, 32, 95, 203, 114, 27, 59, 233, 232, 60, 124, 159, 112, 187, 97, 171, 175, 57, 157, 116, 62, 56, 176, 215, 206, 31, 88, 103, 44, 22$
    $0, 25, 50, 223, 100, 138, 191, 112, 200, 120, 21, 245, 127, 99, 224, 33, 145, 68, 240, 92, 42, 10, 235, 196, 254, 1, 198, 104, 193, 181, 66, 45, 35, 15, 136, 32, 225, 179, 184, 106, 84, 157, 20, 121, 215, 31, 137, 101, 253, 197, 2, 238, 141, 147, 208, 63, 131, 83, 107, 82, 132, 186, 90, 55, 70, 162, 30, 216, 17, 130, 64, 109, 195, 236, 103, 199, 113, 228, 212, 174, 168, 160, 59, 57, 40, 170, 242, 167, 175, 203, 62, 209, 19, 158, 202, 176, 251, 190, 139, 13, 4, 47, 221, 74, 27, 248, 39, 58, 161, 71, 126, 246, 7, 76, 166, 243, 214, 122, 164, 153, 9, 43, 117, 183, 180, 194, 110, 12, 140, 239, 69, 56, 60, 250, 177, 144, 34, 46, 5, 98, 128, 52, 218, 150, 135, 16, 217, 53, 206, 188, 143, 178, 226, 119, 201, 159, 169, 41, 93, 155, 81, 108, 65, 182, 118, 227, 114, 87, 80, 156, 85, 211, 229, 232, 79, 88, 95, 134, 151, 37, 124, 29, 163, 123, 38, 249, 61, 204, 149, 219, 97, 6, 247, 28, 125, 72, 23, 49, 26, 75, 8, 154, 94, 89, 187, 207, 148, 205, 54, 91, 241, 171, 78, 233, 116, 44, 67, 146, 142, 189, 252, 102, 237, 3, 14, 36, 152, 165, 77, 172, 231, 230, 173, 213, 244, 22, 73, 222, 51, 129, 18, 210, 86, 115, 234, 11, 111, 192, 105, 185, 133, 96, 220, 48, 24$
    $0, 99, 198, 205, 141, 87, 155, 158, 27, 144, 174, 67, 55, 44, 61, 237, 54, 68, 33, 247, 93, 181, 134, 165, 110, 154, 88, 8, 122, 209, 219, 242, 108, 18, 136, 83, 66, 175, 239, 103, 186, 125, 107, 243, 13, 184, 75, 241, 220, 127, 53, 238, 176, 50, 16, 12, 244, 59, 163, 57, 183, 14, 229, 178, 216, 213, 36, 11, 17, 109, 166, 116, 132, 235, 95, 46, 223, 140, 206, 131, 117, 91, 250, 35, 214, 170, 231, 5, 26, 159, 113, 81, 150, 20, 227, 74, 185, 104, 254, 1, 106, 126, 221, 39, 97, 197, 100, 42, 32, 69, 24, 120, 233, 90, 118, 192, 71, 80, 114, 153, 111, 143, 28, 195, 203, 41, 101, 49, 177, 230, 171, 79, 72, 161, 22, 246, 34, 251, 218, 210, 77, 4, 232, 121, 9, 169, 215, 179, 190, 249, 92, 248, 191, 119, 25, 6, 157, 156, 7, 89, 234, 133, 182, 58, 245, 23, 70, 193, 173, 145, 85, 130, 207, 168, 10, 37, 52, 128, 63, 147, 226, 21, 162, 60, 45, 96, 40, 204, 199, 225, 148, 152, 115, 167, 208, 123, 253, 105, 2, 188, 212, 217, 252, 124, 187, 3, 78, 172, 194, 29, 139, 224, 200, 65, 84, 146, 64, 201, 138, 30, 48, 102, 240, 76, 211, 189, 180, 94, 236, 62, 129, 86, 142, 112, 160, 73, 228, 15, 51, 38, 222, 47, 31, 43, 56, 164, 135, 19, 151, 149, 82, 137, 202, 196, 98$
    $0, 141, 27, 48, 54, 92, 96, 79, 108, 31, 184, 123, 192, 208, 158, 203, 216, 68, 62, 173, 113, 116, 246, 65, 129, 253, 161, 2, 61, 69, 151, 9, 177, 227, 136, 191, 124, 86, 91, 55, 226, 178, 232, 146, 237, 252, 130, 60, 3, 218, 251, 238, 67, 217, 4, 39, 122, 185, 138, 166, 47, 28, 18, 75, 99, 23, 199, 52, 17, 29, 127, 81, 248, 149, 172, 63, 182, 118, 110, 7, 197, 71, 101, 157, 209, 170, 37, 250, 219, 148, 249, 38, 5, 235, 120, 234, 6, 111, 181, 64, 247, 82, 221, 212, 134, 231, 179, 196, 8, 152, 78, 97, 244, 20, 115, 114, 21, 175, 77, 153, 94, 225, 56, 11, 36, 171, 150, 70, 198, 24, 46, 167, 143, 189, 104, 229, 34, 214, 58, 160, 254, 1, 162, 132, 241, 223, 43, 155, 89, 73, 126, 30, 109, 119, 236, 147, 220, 83, 14, 165, 139, 26, 142, 168, 202, 159, 59, 131, 163, 206, 85, 125, 74, 19, 245, 117, 183, 32, 41, 106, 243, 98, 76, 176, 10, 57, 215, 204, 240, 133, 213, 35, 12, 211, 222, 242, 107, 80, 128, 66, 239, 205, 164, 15, 187, 201, 169, 210, 13, 84, 207, 193, 103, 190, 137, 186, 16, 53, 49, 88, 156, 102, 194, 145, 233, 121, 40, 33, 230, 135, 228, 105, 42, 224, 95, 93, 154, 44, 51, 200, 188, 144, 195, 180, 112, 174, 22, 100, 72, 90, 87, 50, 45, 25, 140$
    $0, 115, 230, 210, 205, 168, 165, 183, 155, 233, 81, 143, 75, 60, 111, 67, 55, 204, 211, 101, 162, 160, 31, 213, 150, 27, 120, 25, 222, 215, 134, 22, 110, 61, 153, 99, 167, 206, 202, 239, 69, 118, 65, 152, 62, 48, 171, 242, 45, 86, 54, 68, 240, 91, 50, 16, 189, 127, 175, 148, 13, 33, 44, 243, 220, 42, 122, 15, 51, 40, 198, 245, 79, 179, 157, 12, 149, 214, 223, 72, 138, 10, 236, 181, 130, 170, 49, 92, 124, 196, 96, 53, 87, 113, 229, 116, 90, 241, 172, 35, 108, 19, 136, 146, 225, 129, 182, 166, 100, 212, 32, 14, 123, 93, 254, 1, 95, 197, 41, 221, 26, 151, 66, 112, 88, 209, 231, 57, 185, 105, 84, 219, 244, 199, 30, 161, 102, 178, 80, 234, 141, 140, 235, 11, 158, 177, 103, 247, 59, 76, 24, 121, 43, 34, 173, 8, 191, 74, 144, 249, 21, 135, 20, 250, 217, 6, 107, 36, 5, 218, 85, 46, 98, 154, 184, 58, 248, 145, 137, 73, 192, 83, 106, 7, 174, 128, 226, 238, 203, 56, 232, 156, 180, 237, 227, 208, 89, 117, 70, 133, 216, 251, 38, 188, 17, 4, 37, 252, 195, 125, 3, 18, 109, 23, 77, 29, 200, 164, 169, 131, 64, 119, 28, 78, 246, 104, 186, 194, 253, 94, 2, 126, 190, 9, 139, 142, 82, 193, 187, 39, 52, 97, 47, 63, 132, 71, 224, 147, 176, 159, 163, 201, 207, 228, 114$
    $0, 157, 59, 53, 118, 173, 106, 104, 236, 120, 91, 199, 212, 224, 208, 33, 217, 204, 240, 27, 182, 95, 143, 113, 169, 126, 193, 19, 161, 75, 66, 44, 179, 15, 153, 207, 225, 117, 54, 191, 109, 171, 190, 55, 31, 116, 226, 61, 83, 177, 252, 68, 131, 3, 38, 43, 67, 253, 150, 2, 132, 47, 88, 140, 103, 107, 30, 56, 51, 215, 159, 210, 195, 93, 234, 29, 108, 192, 127, 203, 218, 245, 87, 48, 125, 170, 110, 82, 62, 185, 232, 10, 197, 73, 122, 21, 166, 248, 99, 98, 249, 230, 136, 64, 7, 163, 6, 65, 76, 40, 86, 246, 134, 23, 251, 178, 45, 37, 4, 221, 9, 233, 94, 183, 176, 84, 25, 78, 206, 154, 214, 52, 60, 227, 112, 144, 102, 141, 175, 184, 63, 137, 165, 22, 135, 231, 186, 223, 213, 155, 58, 158, 216, 34, 129, 149, 254, 1, 151, 70, 181, 28, 235, 105, 174, 142, 96, 229, 250, 24, 85, 41, 220, 5, 164, 138, 124, 49, 115, 32, 209, 160, 20, 123, 139, 89, 146, 238, 244, 219, 42, 39, 77, 26, 241, 72, 198, 92, 196, 11, 243, 239, 205, 79, 17, 202, 128, 35, 14, 180, 71, 242, 12, 148, 130, 69, 152, 16, 80, 189, 172, 119, 237, 147, 13, 36, 46, 133, 247, 167, 101, 145, 90, 121, 74, 162, 8, 222, 187, 201, 18, 194, 211, 200, 188, 81, 111, 228, 97, 100, 168, 114, 50, 57, 156$
    $0, 59, 118, 208, 236, 194, 161, 91, 217, 244, 133, 20, 67, 48, 182, 101, 179, 204, 233, 23, 11, 62, 40, 19, 134, 151, 96, 105, 109, 127, 202, 138, 103, 158, 153, 242, 211, 93, 46, 114, 22, 234, 124, 120, 80, 99, 38, 50, 13, 113, 47, 68, 192, 83, 210, 243, 218, 147, 254, 1, 149, 66, 21, 115, 206, 176, 61, 12, 51, 143, 229, 223, 167, 87, 186, 216, 92, 212, 228, 144, 44, 227, 213, 53, 248, 170, 240, 73, 160, 195, 198, 7, 76, 37, 100, 183, 26, 130, 226, 45, 94, 15, 136, 32, 129, 27, 166, 224, 165, 28, 231, 190, 181, 49, 39, 63, 253, 148, 2, 221, 43, 145, 132, 245, 42, 222, 230, 29, 157, 104, 97, 173, 122, 10, 24, 178, 102, 139, 31, 137, 203, 180, 191, 69, 79, 121, 174, 57, 117, 60, 177, 25, 184, 34, 169, 249, 201, 128, 33, 185, 88, 6, 199, 239, 171, 108, 106, 72, 241, 154, 85, 164, 225, 131, 146, 219, 65, 150, 135, 16, 141, 112, 14, 95, 152, 159, 74, 238, 200, 250, 111, 142, 52, 214, 5, 89, 197, 196, 90, 162, 188, 156, 30, 140, 17, 252, 64, 220, 3, 247, 54, 36, 77, 82, 193, 237, 75, 8, 56, 175, 207, 119, 125, 71, 107, 172, 98, 81, 78, 70, 126, 110, 251, 18, 41, 246, 4, 215, 187, 163, 86, 168, 35, 55, 9, 123, 235, 209, 84, 155, 189, 232, 205, 116, 58$
    $0, 122, 244, 48, 233, 117, 96, 175, 211, 116, 234, 13, 192, 11, 95, 118, 167, 204, 232, 49, 213, 31, 26, 41, 129, 78, 22, 172, 190, 66, 236, 21, 79, 142, 153, 201, 209, 226, 98, 140, 171, 23, 62, 198, 52, 252, 82, 223, 3, 19, 156, 68, 44, 230, 89, 169, 125, 100, 132, 135, 217, 128, 42, 75, 158, 93, 29, 194, 51, 199, 147, 144, 163, 184, 197, 63, 196, 185, 25, 32, 87, 241, 46, 110, 124, 170, 141, 80, 104, 54, 249, 183, 164, 65, 191, 14, 6, 161, 38, 149, 57, 216, 136, 240, 88, 231, 205, 246, 178, 222, 83, 182, 250, 146, 200, 154, 9, 5, 15, 221, 179, 254, 1, 181, 84, 56, 150, 188, 61, 24, 186, 215, 58, 134, 133, 59, 102, 152, 143, 148, 39, 86, 33, 138, 71, 228, 113, 70, 139, 99, 126, 239, 137, 34, 115, 212, 50, 195, 64, 165, 174, 97, 227, 72, 92, 159, 220, 16, 248, 55, 85, 40, 27, 219, 160, 7, 208, 202, 108, 120, 243, 123, 111, 91, 73, 77, 130, 238, 127, 218, 28, 94, 12, 235, 67, 157, 76, 74, 43, 69, 114, 35, 177, 247, 17, 106, 225, 210, 176, 36, 207, 8, 155, 20, 237, 131, 101, 60, 189, 173, 166, 119, 109, 47, 245, 206, 37, 162, 145, 251, 53, 105, 18, 4, 10, 193, 30, 214, 187, 151, 103, 81, 253, 180, 2, 224, 107, 203, 168, 90, 112, 229, 45, 242, 121$
    $0, 233, 211, 152, 167, 224, 49, 40, 79, 199, 193, 139, 98, 198, 80, 84, 158, 68, 143, 96, 131, 195, 23, 22, 196, 228, 141, 52, 160, 223, 168, 36, 61, 248, 136, 156, 31, 82, 192, 200, 7, 146, 135, 249, 46, 218, 44, 155, 137, 6, 201, 238, 27, 179, 104, 94, 65, 70, 191, 83, 81, 32, 72, 101, 122, 56, 241, 177, 17, 240, 57, 247, 62, 148, 164, 182, 129, 236, 145, 8, 14, 60, 37, 59, 15, 170, 243, 117, 92, 207, 181, 165, 88, 213, 55, 123, 19, 113, 12, 134, 147, 63, 221, 106, 54, 214, 103, 180, 208, 150, 188, 235, 130, 97, 140, 229, 127, 87, 166, 153, 162, 220, 64, 95, 144, 237, 202, 116, 244, 76, 112, 20, 227, 197, 99, 42, 34, 48, 225, 11, 114, 26, 239, 18, 124, 78, 41, 100, 73, 252, 109, 205, 3, 119, 217, 47, 35, 169, 16, 178, 28, 216, 120, 251, 74, 91, 118, 4, 30, 157, 85, 186, 231, 210, 234, 189, 184, 67, 159, 53, 107, 90, 75, 245, 176, 242, 171, 204, 110, 175, 246, 58, 38, 10, 226, 21, 24, 133, 13, 9, 39, 50, 126, 230, 187, 151, 212, 89, 108, 253, 173, 2, 206, 93, 105, 222, 161, 154, 45, 250, 121, 102, 215, 29, 5, 138, 194, 132, 25, 115, 203, 172, 254, 1, 174, 111, 77, 125, 51, 142, 69, 66, 185, 86, 128, 183, 190, 71, 33, 43, 219, 163, 149, 209, 232$
$\endgroup$
2
  • $\begingroup$ Since $255$ is not a prime power (so that $\mathbb Z / (255)$ is not a field), it is not clear what this post has to do with the question. $\endgroup$
    – Alex M.
    Oct 14, 2019 at 15:21
  • $\begingroup$ It mean that people found such involutions not only for fields but also for Rings (which are not Fields) $\endgroup$
    – user144684
    Oct 14, 2019 at 15:30
0
$\begingroup$

The perfect nonlinear function $f$ can be represented as a special sequence ($a_{1},...,a_{n}$).

The main property: $f(a_{i}) = a_{-i}$.

Other properties:

${a_{2^k}}$ = $2^k$;

There exist such element $\alpha$ that

${a_{-i} = a_{i} + i*(\alpha-1)}$

For $i \ne 0, i+1 \ne 0$ we have:

$ f(a_{i}) - f(a_{i}-a_{i+1}) = 1$

For any 2 not equal $i,k \ne 0, i+k \ne 0 $:

$ f(a_{i}) - f(a_{i}-a_{i+k}) = a_{k}$

I know yet 5 of the same nature sequences for the $GF(31)$.

I know a sequence of the same nature for the $GF(2^{k}-1)$ and prime $2^{k}-1$.

Looks like the following property holds as well:

$ a_{j} - a_{k} = a_{j+ \frac{a_{k}-a_{k-j}}{\alpha-1}} $

$ a_{i} = -f(i*(\alpha-1)) $

Example ($\alpha=18$):

|index   |  value |
|--------| -------|
|0       |   0    | 
|1       |   1    |
|2       |   2    | 
|3       |   23   |
|4       |   4    |
|5       |   19   |
|6       |   15   |
|7       |   3    |
|8       |   8    |
|9       |   28   |
|10      |   7    |
|11      |   13   |
|12      |   30   |
|13      |   21   |
|14      |   6    |
|15      |   9    |
|16      |   16   |
|17      |   27   |
|18      |   25   |
|19      |   17   |
|20      |   14   |
|21      |   22   |
|22      |   26   |
|23      |   20   |
|24      |   29   |
|25      |   24   |
|26      |   11   |
|27      |   10   |
|28      |   12   |
|29      |   5    |
|30      |   18   |
--------------------
$\endgroup$
6
  • $\begingroup$ It is extremely hard to understand your post: you make claims that you do not prove, and you claim to know results that you do not share with us. What is the point of your answer, then? $\endgroup$
    – Alex M.
    Jul 2, 2021 at 10:54
  • $\begingroup$ I spent many intellectual efforts to obtain these results, probably it would be interesting for the scientific society. $\endgroup$
    – Alexander
    Jul 2, 2021 at 11:01
  • $\begingroup$ I still hope to get some help and will finally discover the nature of these perfect non-linear involutive functions. $\endgroup$
    – Alexander
    Jul 2, 2021 at 11:02
  • $\begingroup$ BTW: I was an author of the original question (another temporary user) $\endgroup$
    – Alexander
    Jul 2, 2021 at 11:03
  • $\begingroup$ quite frankly I had a strong suspicion that you and the OP are connected, possibly the same person: the same LaTeX and graphical style, the same vocabulary, many other similarities. Please notice that, currently, the OP has written 3 posts that are not answers, to which I would add yours (which, again, is not an answer). If I were you or the OP, I would collect the useful information from all these 4 posts into a single one, and delete the other 3. $\endgroup$
    – Alex M.
    Jul 2, 2021 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.