Perfectly nonlinear involutions

MO338802.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace Sandbox
{
    class MO338802
    {
        public static void Main()
        {
            foreach (var (q, ch) in new (uint, uint)[] {(3, 3), (5, 5), (7, 7), (9, 3)}) Search(q, ch);
            Console.WriteLine("===");
            for (int i = 2; i < 5; i++) SearchExponential(i);
        }

        /// <summary>Brute force search for solutions in a finite field</summary>
        /// <param name="q">The order of the field</param>
        /// <param name="characteristic">The characteristic of the field</param>
        internal static void Search(uint q, uint characteristic)
        {
            _Search(new uint[q], characteristic, new List<uint>(), new uint[q]);
        }

        /// <summary>Guided search for solutions over Z/nZ (where n is 2^a - 1) satisfying f(2x) = 2f(x)</summary>
        /// <param name="a">The index of the Mersenne number</param>
        internal static void SearchExponential(int a)
        {
            uint n = (1U << a) - 1;
            // 2^a == 1 (mod n), so we have cycles of length a
            // We group those cycles in singles or pairs. (Singles only work if a is even).
            IList<uint[]> cycles = new List<uint[]>();
            ISet<uint> seen = new HashSet<uint>();
            for (uint i = 1; i < n; i++)
            {
                if (seen.Contains(i)) continue;

                var cycle = new List<uint>();
                uint x = i;
                for (int j = 0; j < a; j++)
                {
                    cycle.Add(x);
                    seen.Add(x);
                    x = x * 2 % n;
                    if (x == cycle[0]) break;
                }
                cycles.Add(cycle.ToArray());
            }

            _SearchExponential(n, new uint[n], cycles, new BigInteger[n]);
        }

        private static void _Search(uint[] f, uint characteristic, IList<uint> visited, uint[] gs)
        {
            if (visited.Count == f.Length - 1)
            {
                Console.WriteLine(string.Join(", ", f));
                return;
            }

            uint? x = null;
            for (uint i = 1; i < f.Length; i++)
            {
                if (f[i] != 0) continue;

                if (x == null) x = i;
                else
                {
                    visited.Add(x.Value);
                    visited.Add(i);
                    f[x.Value] = i;
                    f[i] = x.Value;

                    try
                    {
                        bool conflict = false;
                        uint[] gs_ext = (uint[])gs.Clone();

                        // For each a, we require g_a(z) = f(z+a) - f(z) to be injective.
                        // Do these two new values of f(z) (namely f(x) and f(i)) cause this to fail?
                        for (uint a = 1; a < f.Length && !conflict; a++)
                        {
                            // We consider up to four newly revealed values of g_a
                            foreach (var z in new[] { x.Value, Sub(x.Value, a, characteristic), i, Sub(i, a, characteristic)}.Distinct())
                            {
                                var z_plus_a = Add(z, a, characteristic);
                                if (f[z] != 0 && f[z_plus_a] != 0)
                                {
                                    var flag = 1U << (int)Sub(f[z_plus_a], f[z], characteristic);
                                    if ((gs_ext[a] & flag) != 0)
                                    {
                                        conflict = true;
                                        break;
                                    }
                                    gs_ext[a] |= flag;
                                }
                            }
                        }

                        if (!conflict) _Search(f, characteristic, visited, gs_ext);
                    }
                    finally
                    {
                        f[x.Value] = f[i] = 0;
                        visited.RemoveAt(visited.Count - 1);
                        visited.RemoveAt(visited.Count - 1);
                    }
                }
            }
        }

        private static void _SearchExponential(uint n, uint[] f, IList<uint[]> cycles, BigInteger[] gs)
        {
            if (cycles.Count == 0)
            {
                Console.WriteLine(string.Join(", ", f));
                return;
            }

            var c0 = cycles[0];
            for (int i = c0.Length % 2; i < cycles.Count; i++)
            {
                var c1 = cycles[i];
                if (c1.Length != c0.Length) continue;

                // Pair c0 with c1
                var offsets = i == 0 ? Enumerable.Repeat(c0.Length / 2, 1) : Enumerable.Range(1, c0.Length);
                foreach (var offset in offsets)
                {
                    for (int j = 0; j < c0.Length; j++)
                    {
                        int k = (j + offset) % c0.Length;
                        f[c0[j]] = c1[k];
                        f[c1[k]] = c0[j];
                    }

                    bool conflict = false;
                    var gs_ext = gs.ToArray();

                    // For each a, we require g_a(z) = f(z+a) - f(z) to be injective.
                    // Do these new values of f(z) cause this to fail?
                    for (uint a = 1; a < f.Length && !conflict; a++)
                    {
                        var newAssignments = new HashSet<uint>();
                        newAssignments.UnionWith(c0);
                        newAssignments.UnionWith(c1);
                        newAssignments.UnionWith(c0.Select(z => (z + n - a) % n));
                        newAssignments.UnionWith(c1.Select(z => (z + n - a) % n));

                        foreach (var z in newAssignments)
                        {
                            var z_plus_a = (z + a) % n;
                            if (f[z] != 0 && f[z_plus_a] != 0)
                            {
                                var flag = BigInteger.One << (int)((f[z_plus_a] + n - f[z]) % n);
                                if ((gs_ext[a] & flag) != 0)
                                {
                                    conflict = true;
                                    break;
                                }
                                gs_ext[a] |= flag;
                            }
                        }
                    }

                    if (!conflict) _SearchExponential(n, f, cycles.Except(new[] { c0, c1 }).ToList(), gs_ext);

                    for (int j = 0; j < c0.Length; j++)
                    {
                        int k = (j + offset) % c0.Length;
                        f[c0[j]] = 0;
                        f[c1[k]] = 0;
                    }
                }
            }
        }

        private static uint Add(uint a, uint b, uint characteristic)
        {
            uint rv = 0, pow = 1;
            while (a > 0 || b > 0)
            {
                rv += ((a + b) % characteristic) * pow;
                pow *= characteristic;
                a /= characteristic;
                b /= characteristic;
            }
            return rv;
        }

        private static uint Sub(uint a, uint b, uint characteristic)
        {
            uint rv = 0, pow = 1;
            while (a > 0 || b > 0)
            {
                rv += (characteristic + a % characteristic - b % characteristic) % characteristic * pow;
                pow *= characteristic;
                a /= characteristic;
                b /= characteristic;
            }
            return rv;
        }
    }
}