Nonlinear mod 5

This post is a follow-on to the previous post on perfectly nonlinear functions. In that post we defined a way to measure the degree of nonlinearity of a function between two Abelian groups. We looked at functions that take sequences of four bits to a single bit. In formal terms, our groups were GF(2⁴) and GF(2).

In this post we'll start out by looking at integers mod 5 to show how the content of the previous post takes a different form in different groups. Sometimes the simplicity of working in binary makes things harder to see. For example, we noted in the previous post that the distinction between addition and subtraction didn't matter. It matters in general!

Let B be the group of integers mod 5 and A the group of pairs of integers mod 5. That is, A is the direct product B * B. We will compute the uniformity of several functions from A to B. (Recall that less uniformity means more nonlinearity.) Then we'll conclude by looking what happens if we work modulo other integers.

Python code

Here's the code we'll use to compute uniformity.

 from itertools import product from numpy import array m = 5 r = range(m) def deriv(f, x, a): return (f(x + a) - f(x))%m def delta(f, a, b): return {x for x in product(r, r) if all(deriv(f, array(x), a) == b)} def uniformity(f): u = 0 for a in product(r, r): if a == (0, 0): continue for b in product(r, r): t = len(delta(f, array(a), array(b))) if t > u: u = t return u

We didn't call attention to it last time, but the function f(x + a) - f(x) is called a derivative of f, and that's why we named the function above deriv.

Here are a few functions whose uniformity we'd like to compute.

 # (u, v) -> u^2 + v^2 def F2(x): return sum(x**2)%m # (u, b) -> u^3 + v^3 def F3(x): return sum(x**3)%m # (u, b) -> u^2 + v def G(x): return (x[0]**2 + x[1])%m # (u, v) -> uv def H(x): return (x[0]*x[1])%m

Now let's look at their uniformity values.

 print( uniformity(F2) ) print( uniformity(F3) ) print( uniformity(G) ) print( uniformity(H) )

Results mod 5

This prints out 5, 10, 25, and 5. This says that the functions F2 and H are the most nonlinear, in fact perfectly nonlinear." The function G, although nonlinear, has the same uniformity as a linear function.

The function F3 may be the most interesting, having intermediate uniformity. In some sense the sum of cubes is closer to being a linear function than the sum of squares is.

Other moduli

We can easily look at other groups by simply changing the value of m at the top of the code.

If we set the modulus to 7, we get analogous results. The uniformities of the four functions are 7, 14, 49, and 7. They're ranked exactly as they were when the modulus was 5.

But that's not always the case for other moduli as you can see in the table below. Working mod 8, for example, the sum of squares is more uniform than the sum of cubes, the opposite of the case mod 5 or mod 7.

 |----+-----+-----+-----+----| | m | F2 | F3 | G | H | |----+-----+-----+-----+----| | 2 | 4 | 4 | 4 | 2 | | 3 | 3 | 9 | 9 | 3 | | 4 | 16 | 8 | 16 | 8 | | 5 | 5 | 10 | 25 | 5 | | 6 | 36 | 36 | 36 | 18 | | 7 | 7 | 14 | 49 | 7 | | 8 | 64 | 32 | 64 | 32 | | 9 | 27 | 81 | 81 | 27 | | 10 | 100 | 100 | 100 | 50 | | 11 | 11 | 22 | 121 | 11 | | 12 | 144 | 144 | 144 | 72 | |----+-----+-----+-----+----|

In every case, G is the most uniform function and H is the least. Also, G is strictly more uniform than H. But there are many different ways F2 and F3 can fit between G and H.

The post Nonlinear mod 5 first appeared on John D. Cook.