Skip to content

Instantly share code, notes, and snippets.

@NickStrupat
Created October 29, 2024 05:05
Show Gist options
  • Save NickStrupat/464b3f63bfad7d780fada2974ae62a8f to your computer and use it in GitHub Desktop.
Save NickStrupat/464b3f63bfad7d780fada2974ae62a8f to your computer and use it in GitHub Desktop.
using System;
public readonly struct PrimeQuadraticResiduePermuter32(UInt32 seed)
{
public UInt32 this[UInt32 x] => Permute(Permute(unchecked(x + seed)) ^ Xor);
private const UInt32 Xor = 0x5bf03635;
private static UInt32 Permute(UInt32 x)
{
const UInt32 prime = 4_294_967_291; // The largest prime less than 2^32 that is congruent to 3 mod 4.
if (x >= prime)
return x; // The 5 integers out of range are mapped to themselves.
var square = (UInt64) x * x;
var residue = (UInt32)(square % prime);
return x <= prime / 2 ? residue : prime - residue;
}
}
public readonly struct PrimeQuadraticResiduePermuter64(UInt64 seed)
{
public UInt64 this[UInt64 x] => Permute(Permute(unchecked(x + seed)) ^ Xor);
private const UInt64 Xor = 0x5bf036355bf03635;
private static UInt64 Permute(UInt64 x)
{
const UInt64 prime = 18_446_744_073_709_551_427; // The largest prime less than 2^64 that is congruent to 3 mod 4.
if (x >= prime)
return x; // The 188 integers out of range are mapped to themselves.
var square = (UInt128) x * x;
var residue = (UInt64)(square % prime);
return x <= prime / 2 ? residue : prime - residue;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment