Skip to main content
MathOverflow

Return to Answer

added 11904 characters in body
Source Link
Peter Taylor
Peter Taylor
  • 7.2k
  • 1
  • 21
  • 29

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. This could well be a coincidence. I don't think that my search is efficient enough to be worth attempting $GF(127)$

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)$

.

I note that the three fields for which I have found solutions have orders which are Mersenne primes. This could well be a coincidence. I don't think that my search is efficient enough to be worth attempting $GF(127)$

.

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)$

.

Source Link
Peter Taylor
Peter Taylor
  • 7.2k
  • 1
  • 21
  • 29

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 the three fields for which I have found solutions have orders which are Mersenne primes. This could well be a coincidence. I don't think that my search is efficient enough to be worth attempting $GF(127)$.