Mod
Modular inversion as implemented in this class is based on the paper "Fast constant-time gcd computation and
modular inversion" by Daniel J. Bernstein and Bo-Yin Yang.
using Org.BouncyCastle.Crypto.Utilities;
using Org.BouncyCastle.Security;
using Org.BouncyCastle.Utilities;
using System;
namespace Org.BouncyCastle.Math.Raw
{
internal static class Mod
{
private const int M30 = 1073741823;
private const ulong M32UL = 4294967295;
private static readonly int MaxStackAlloc = Platform.Is64BitProcess ? 4096 : 1024;
public static void CheckedModOddInverse(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z)
{
if (ModOddInverse(m, x, z) == 0)
throw new ArithmeticException("Inverse does not exist.");
}
public static void CheckedModOddInverseVar(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z)
{
if (!ModOddInverseVar(m, x, z))
throw new ArithmeticException("Inverse does not exist.");
}
public static uint Inverse32(uint d)
{
uint num = d * (2 - d * d);
num *= 2 - d * num;
num *= 2 - d * num;
return num * (2 - d * num);
}
public static ulong Inverse64(ulong d)
{
ulong num = d * (2 - d * d);
num *= 2 - d * num;
num *= 2 - d * num;
num *= 2 - d * num;
return num * (2 - d * num);
}
public unsafe static uint ModOddInverse(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z)
{
int length = m.Length;
int num = (length << 5) - Integers.NumberOfLeadingZeros((int)m[length - 1]);
int num2 = (num + 29) / 30;
int num3 = num2 * 5;
Span<int> span;
int num4;
if (num3 * 4 <= MaxStackAlloc) {
num4 = num3;
span = new Span<int>(stackalloc byte[(int)checked(unchecked((ulong)(uint)num4) * 4)], num4);
} else
span = new int[num3];
Span<int> span2 = span;
Span<int> span3 = new Span<int>(stackalloc byte[16], 4);
Span<int> span4 = span2.Slice(0, num2);
num4 = num2;
span2 = span2.Slice(num4, span2.Length - num4);
Span<int> e = span2.Slice(0, num2);
num4 = num2;
span2 = span2.Slice(num4, span2.Length - num4);
Span<int> span5 = span2.Slice(0, num2);
num4 = num2;
span2 = span2.Slice(num4, span2.Length - num4);
Span<int> span6 = span2.Slice(0, num2);
num4 = num2;
span2 = span2.Slice(num4, span2.Length - num4);
Span<int> span7 = span2.Slice(0, num2);
e[0] = 1;
Encode30(num, x, span6);
Encode30(num, m, span7);
span7.CopyTo(span5);
int theta = 0;
int m0Inv = (int)Inverse32((uint)span7[0]);
int maximumHDDivsteps = GetMaximumHDDivsteps(num);
for (int i = 0; i < maximumHDDivsteps; i += 30) {
theta = HDDivsteps30(theta, span5[0], span6[0], span3);
UpdateDE30(num2, span4, e, span3, m0Inv, span7);
UpdateFG30(num2, span5, span6, span3);
}
int num5 = span5[num2 - 1] >> 31;
CNegate30(num2, num5, span5);
CNormalize30(num2, num5, span4, span7);
Decode30(num, span4, z);
return (uint)(EqualTo(num2, span5, 1) & EqualTo(num2, span6, 0));
}
public unsafe static bool ModOddInverseVar(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z)
{
int length = m.Length;
int num = (length << 5) - Integers.NumberOfLeadingZeros((int)m[length - 1]);
int num2 = (num + 29) / 30;
int num3 = num - Nat.GetBitLength(length, x);
int num4 = num2 * 5;
Span<int> span;
int num5;
if (num4 * 4 <= MaxStackAlloc) {
num5 = num4;
span = new Span<int>(stackalloc byte[(int)checked(unchecked((ulong)(uint)num5) * 4)], num5);
} else
span = new int[num4];
Span<int> span2 = span;
Span<int> span3 = new Span<int>(stackalloc byte[16], 4);
Span<int> span4 = span2.Slice(0, num2);
num5 = num2;
span2 = span2.Slice(num5, span2.Length - num5);
Span<int> e = span2.Slice(0, num2);
num5 = num2;
span2 = span2.Slice(num5, span2.Length - num5);
Span<int> span5 = span2.Slice(0, num2);
num5 = num2;
span2 = span2.Slice(num5, span2.Length - num5);
Span<int> span6 = span2.Slice(0, num2);
num5 = num2;
span2 = span2.Slice(num5, span2.Length - num5);
Span<int> span7 = span2.Slice(0, num2);
e[0] = 1;
Encode30(num, x, span6);
Encode30(num, m, span7);
span7.CopyTo(span5);
int eta = -num3;
int num6 = num2;
int num7 = num2;
int m0Inv = (int)Inverse32((uint)span7[0]);
int maximumDivsteps = GetMaximumDivsteps(num);
int num8 = num3;
while (!EqualToVar(num7, span6, 0)) {
if (num8 >= maximumDivsteps)
return false;
num8 += 30;
eta = Divsteps30Var(eta, span5[0], span6[0], span3);
UpdateDE30(num6, span4, e, span3, m0Inv, span7);
UpdateFG30(num7, span5, span6, span3);
num7 = TrimFG30Var(num7, span5, span6);
}
int num9 = span5[num7 - 1] >> 31;
int num10 = span4[num6 - 1] >> 31;
if (num10 < 0)
num10 = Add30(num6, span4, span7);
if (num9 < 0) {
num10 = Negate30(num6, span4);
Negate30(num7, span5);
}
if (!EqualToVar(num7, span5, 1))
return false;
if (num10 < 0)
num10 = Add30(num6, span4, span7);
Decode30(num, span4, z);
return true;
}
public unsafe static uint ModOddIsCoprime(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x)
{
int length = m.Length;
int num = (length << 5) - Integers.NumberOfLeadingZeros((int)m[length - 1]);
int num2 = (num + 29) / 30;
int num3 = num2 * 3;
Span<int> span;
int num4;
if (num3 * 4 <= MaxStackAlloc) {
num4 = num3;
span = new Span<int>(stackalloc byte[(int)checked(unchecked((ulong)(uint)num4) * 4)], num4);
} else
span = new int[num3];
Span<int> span2 = span;
Span<int> span3 = new Span<int>(stackalloc byte[16], 4);
Span<int> span4 = span2.Slice(0, num2);
num4 = num2;
span2 = span2.Slice(num4, span2.Length - num4);
Span<int> span5 = span2.Slice(0, num2);
num4 = num2;
span2 = span2.Slice(num4, span2.Length - num4);
Span<int> z = span2.Slice(0, num2);
Encode30(num, x, span5);
Encode30(num, m, z);
z.CopyTo(span4);
int theta = 0;
int maximumHDDivsteps = GetMaximumHDDivsteps(num);
for (int i = 0; i < maximumHDDivsteps; i += 30) {
theta = HDDivsteps30(theta, span4[0], span5[0], span3);
UpdateFG30(num2, span4, span5, span3);
}
int cond = span4[num2 - 1] >> 31;
CNegate30(num2, cond, span4);
return (uint)(EqualTo(num2, span4, 1) & EqualTo(num2, span5, 0));
}
public unsafe static bool ModOddIsCoprimeVar(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x)
{
int length = m.Length;
int num = (length << 5) - Integers.NumberOfLeadingZeros((int)m[length - 1]);
int num2 = (num + 29) / 30;
int num3 = num - Nat.GetBitLength(length, x);
int num4 = num2 * 3;
Span<int> span;
int num5;
if (num4 * 4 <= MaxStackAlloc) {
num5 = num4;
span = new Span<int>(stackalloc byte[(int)checked(unchecked((ulong)(uint)num5) * 4)], num5);
} else
span = new int[num4];
Span<int> span2 = span;
Span<int> span3 = new Span<int>(stackalloc byte[16], 4);
Span<int> span4 = span2.Slice(0, num2);
num5 = num2;
span2 = span2.Slice(num5, span2.Length - num5);
Span<int> span5 = span2.Slice(0, num2);
num5 = num2;
span2 = span2.Slice(num5, span2.Length - num5);
Span<int> z = span2.Slice(0, num2);
Encode30(num, x, span5);
Encode30(num, m, z);
z.CopyTo(span4);
int eta = -num3;
int num6 = num2;
int maximumDivsteps = GetMaximumDivsteps(num);
int num7 = num3;
while (!EqualToVar(num6, span5, 0)) {
if (num7 >= maximumDivsteps)
return false;
num7 += 30;
eta = Divsteps30Var(eta, span4[0], span5[0], span3);
UpdateFG30(num6, span4, span5, span3);
num6 = TrimFG30Var(num6, span4, span5);
}
if (span4[num6 - 1] >> 31 < 0)
Negate30(num6, span4);
return EqualToVar(num6, span4, 1);
}
public static uint[] Random(SecureRandom random, uint[] p)
{
int num = p.Length;
uint[] array = Nat.Create(num);
uint num2 = p[num - 1];
num2 |= num2 >> 1;
num2 |= num2 >> 2;
num2 |= num2 >> 4;
num2 |= num2 >> 8;
num2 |= num2 >> 16;
byte[] array2 = new byte[num << 2];
do {
random.NextBytes(array2);
Pack.BE_To_UInt32(array2, 0, array);
array[num - 1] &= num2;
} while (Nat.Gte(num, array, p));
return array;
}
public unsafe static void Random(SecureRandom random, ReadOnlySpan<uint> p, Span<uint> z)
{
int length = p.Length;
if (z.Length < length)
throw new ArgumentException("insufficient space", "z");
Span<uint> span = z.Slice(0, length);
uint num = p[length - 1];
num |= num >> 1;
num |= num >> 2;
num |= num >> 4;
num |= num >> 8;
num |= num >> 16;
int num2 = length * 4;
Span<byte> span2;
if (num2 <= MaxStackAlloc) {
int num3 = num2;
span2 = new Span<byte>(stackalloc byte[(int)(uint)num3], num3);
} else
span2 = new byte[num2];
Span<byte> span3 = span2;
do {
random.NextBytes(span3);
Pack.BE_To_UInt32(span3, span);
span[length - 1] &= num;
} while (Nat.Gte(length, span, p));
}
private static int Add30(int len30, Span<int> D, ReadOnlySpan<int> M)
{
int num = 0;
int num2 = len30 - 1;
for (int i = 0; i < num2; i++) {
num += D[i] + M[i];
D[i] = (num & 1073741823);
num >>= 30;
}
num += D[num2] + M[num2];
D[num2] = num;
return num >> 30;
}
private static void CNegate30(int len30, int cond, Span<int> D)
{
int num = 0;
int num2 = len30 - 1;
for (int i = 0; i < num2; i++) {
num += (D[i] ^ cond) - cond;
D[i] = (num & 1073741823);
num >>= 30;
}
num += (D[num2] ^ cond) - cond;
D[num2] = num;
}
private static void CNormalize30(int len30, int condNegate, Span<int> D, ReadOnlySpan<int> M)
{
int num = len30 - 1;
int num2 = 0;
int num3 = D[num] >> 31;
for (int i = 0; i < num; i++) {
int num4 = D[i] + (M[i] & num3);
num4 = (num4 ^ condNegate) - condNegate;
num2 += num4;
D[i] = (num2 & 1073741823);
num2 >>= 30;
}
int num5 = D[num] + (M[num] & num3);
num5 = (num5 ^ condNegate) - condNegate;
num2 += num5;
D[num] = num2;
int num6 = 0;
int num7 = D[num] >> 31;
for (int j = 0; j < num; j++) {
int num8 = D[j] + (M[j] & num7);
num6 += num8;
D[j] = (num6 & 1073741823);
num6 >>= 30;
}
int num9 = D[num] + (M[num] & num7);
num6 += num9;
D[num] = num6;
}
private static void Decode30(int bits, ReadOnlySpan<int> x, Span<uint> z)
{
int i = 0;
ulong num = 0;
int num2 = 0;
int num3 = 0;
while (bits > 0) {
for (; i < System.Math.Min(32, bits); i += 30) {
num = (ulong)((long)num | ((long)x[num2++] << i));
}
z[num3++] = (uint)num;
num >>= 32;
i -= 32;
bits -= 32;
}
}
private static int Divsteps30Var(int eta, int f0, int g0, Span<int> t)
{
int num = 1;
int num2 = 0;
int num3 = 0;
int num4 = 1;
int num5 = f0;
int num6 = g0;
int num7 = 30;
while (true) {
int num8 = Integers.NumberOfTrailingZeros(num6 | (-1 << num7));
num6 >>= num8;
num <<= num8;
num2 <<= num8;
eta -= num8;
num7 -= num8;
if (num7 <= 0)
break;
int num14;
if (eta <= 0) {
eta = 2 - eta;
int num9 = num5;
num5 = num6;
num6 = -num9;
int num10 = num;
num = num3;
num3 = -num10;
int num11 = num2;
num2 = num4;
num4 = -num11;
int num12 = (eta > num7) ? num7 : eta;
int num13 = (int)((uint.MaxValue >> 32 - num12) & 63);
num14 = ((num5 * num6 * (num5 * num5 - 2)) & num13);
} else {
int num12 = (eta > num7) ? num7 : eta;
int num13 = (int)((uint.MaxValue >> 32 - num12) & 15);
num14 = num5 + (((num5 + 1) & 4) << 1);
num14 = ((num14 * -num6) & num13);
}
num6 += num5 * num14;
num3 += num * num14;
num4 += num2 * num14;
}
t[0] = num;
t[1] = num2;
t[2] = num3;
t[3] = num4;
return eta;
}
private static void Encode30(int bits, ReadOnlySpan<uint> x, Span<int> z)
{
int num = 0;
ulong num2 = 0;
int num3 = 0;
int num4 = 0;
while (bits > 0) {
if (num < System.Math.Min(30, bits)) {
num2 = (ulong)((long)num2 | (((long)x[num3++] & 4294967295) << num));
num += 32;
}
z[num4++] = ((int)num2 & 1073741823);
num2 >>= 30;
num -= 30;
bits -= 30;
}
}
private static int EqualTo(int len, ReadOnlySpan<int> x, int y)
{
int num = x[0] ^ y;
for (int i = 1; i < len; i++) {
num |= x[i];
}
num = ((int)((uint)num >> 1) | (num & 1));
return num - 1 >> 31;
}
private static bool EqualToVar(int len, ReadOnlySpan<int> x, int y)
{
int num = x[0] ^ y;
if (num != 0)
return false;
for (int i = 1; i < len; i++) {
num |= x[i];
}
return num == 0;
}
private static int GetMaximumDivsteps(int bits)
{
return (int)(188898 * (long)bits + ((bits < 46) ? 308405 : 181188) >> 16);
}
private static int GetMaximumHDDivsteps(int bits)
{
return (int)(150964 * (long)bits + 99243 >> 16);
}
private static int HDDivsteps30(int theta, int f0, int g0, Span<int> t)
{
int num = 1073741824;
int num2 = 0;
int num3 = 0;
int num4 = 1073741824;
int num5 = f0;
int num6 = g0;
for (int i = 0; i < 30; i++) {
int num7 = theta >> 31;
int num8 = -(num6 & 1);
int num9 = num5 ^ num7;
int num10 = num ^ num7;
int num11 = num2 ^ num7;
num6 -= (num9 & num8);
num3 -= (num10 & num8);
num4 -= (num11 & num8);
int num12 = num8 & ~num7;
theta = (theta ^ num12) + 1;
num5 += (num6 & num12);
num += (num3 & num12);
num2 += (num4 & num12);
num6 >>= 1;
num3 >>= 1;
num4 >>= 1;
}
t[0] = num;
t[1] = num2;
t[2] = num3;
t[3] = num4;
return theta;
}
private static int Negate30(int len30, Span<int> D)
{
int num = 0;
int num2 = len30 - 1;
for (int i = 0; i < num2; i++) {
num -= D[i];
D[i] = (num & 1073741823);
num >>= 30;
}
num -= D[num2];
D[num2] = num;
return num >> 30;
}
private static int TrimFG30Var(int len30, Span<int> F, Span<int> G)
{
int num = F[len30 - 1];
int num2 = G[len30 - 1];
if (((len30 - 2 >> 31) | (num ^ (num >> 31)) | (num2 ^ (num2 >> 31))) == 0) {
F[len30 - 2] |= num << 30;
G[len30 - 2] |= num2 << 30;
len30--;
}
return len30;
}
private static void UpdateDE30(int len30, Span<int> D, Span<int> E, ReadOnlySpan<int> t, int m0Inv32, ReadOnlySpan<int> M)
{
int num = t[0];
int num2 = t[1];
int num3 = t[2];
int num4 = t[3];
int num5 = D[len30 - 1] >> 31;
int num6 = E[len30 - 1] >> 31;
int num7 = (num & num5) + (num2 & num6);
int num8 = (num3 & num5) + (num4 & num6);
int num9 = M[0];
int num10 = D[0];
int num11 = E[0];
long num12 = (long)num * (long)num10 + (long)num2 * (long)num11;
long num13 = (long)num3 * (long)num10 + (long)num4 * (long)num11;
num7 -= ((m0Inv32 * (int)num12 + num7) & 1073741823);
num8 -= ((m0Inv32 * (int)num13 + num8) & 1073741823);
num12 += (long)num9 * (long)num7;
num13 += (long)num9 * (long)num8;
num12 >>= 30;
num13 >>= 30;
for (int i = 1; i < len30; i++) {
num9 = M[i];
num10 = D[i];
num11 = E[i];
num12 += (long)num * (long)num10 + (long)num2 * (long)num11 + (long)num9 * (long)num7;
num13 += (long)num3 * (long)num10 + (long)num4 * (long)num11 + (long)num9 * (long)num8;
D[i - 1] = ((int)num12 & 1073741823);
num12 >>= 30;
E[i - 1] = ((int)num13 & 1073741823);
num13 >>= 30;
}
D[len30 - 1] = (int)num12;
E[len30 - 1] = (int)num13;
}
private static void UpdateFG30(int len30, Span<int> F, Span<int> G, ReadOnlySpan<int> t)
{
int num = t[0];
int num2 = t[1];
int num3 = t[2];
int num4 = t[3];
int num5 = F[0];
int num6 = G[0];
long num7 = (long)num * (long)num5 + (long)num2 * (long)num6;
long num8 = (long)num3 * (long)num5 + (long)num4 * (long)num6;
num7 >>= 30;
num8 >>= 30;
for (int i = 1; i < len30; i++) {
num5 = F[i];
num6 = G[i];
num7 += (long)num * (long)num5 + (long)num2 * (long)num6;
num8 += (long)num3 * (long)num5 + (long)num4 * (long)num6;
F[i - 1] = ((int)num7 & 1073741823);
num7 >>= 30;
G[i - 1] = ((int)num8 & 1073741823);
num8 >>= 30;
}
F[len30 - 1] = (int)num7;
G[len30 - 1] = (int)num8;
}
}
}