Skip to content

Instantly share code, notes, and snippets.

@pjt33

pjt33/MO338802.cs

Created Aug 26, 2019
Embed
What would you like to do?
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
You can’t perform that action at this time.