Perfectly nonlinear involutions
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; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment