diff --git a/crypto/src/math/raw/Mod.cs b/crypto/src/math/raw/Mod.cs
new file mode 100644
index 000000000..63467e668
--- /dev/null
+++ b/crypto/src/math/raw/Mod.cs
@@ -0,0 +1,184 @@
+using System;
+using System.Diagnostics;
+
+using Org.BouncyCastle.Crypto.Utilities;
+using Org.BouncyCastle.Utilities;
+
+namespace Org.BouncyCastle.Math.Raw
+{
+ internal abstract class Mod
+ {
+ public static void Invert(uint[] p, uint[] x, uint[] z)
+ {
+ int len = p.Length;
+ if (Nat.IsZero(len, x))
+ throw new ArgumentException("cannot be 0", "x");
+ if (Nat.IsOne(len, x))
+ {
+ Array.Copy(x, 0, z, 0, len);
+ return;
+ }
+
+ uint[] u = Nat.Copy(len, x);
+ uint[] a = Nat.Create(len);
+ a[0] = 1;
+ int ac = 0;
+
+ if ((u[0] & 1) == 0)
+ {
+ InversionStep(p, u, len, a, ref ac);
+ }
+ if (Nat.IsOne(len, u))
+ {
+ InversionResult(p, ac, a, z);
+ return;
+ }
+
+ uint[] v = Nat.Copy(len, p);
+ uint[] b = Nat.Create(len);
+ int bc = 0;
+
+ int uvLen = len;
+
+ for (;;)
+ {
+ while (u[uvLen - 1] == 0 && v[uvLen - 1] == 0)
+ {
+ --uvLen;
+ }
+
+ if (Nat.Gte(len, u, v))
+ {
+ Nat.SubFrom(len, v, u);
+ Debug.Assert((u[0] & 1) == 0);
+ ac += Nat.SubFrom(len, b, a) - bc;
+ InversionStep(p, u, uvLen, a, ref ac);
+ if (Nat.IsOne(len, u))
+ {
+ InversionResult(p, ac, a, z);
+ return;
+ }
+ }
+ else
+ {
+ Nat.SubFrom(len, u, v);
+ Debug.Assert((v[0] & 1) == 0);
+ bc += Nat.SubFrom(len, a, b) - ac;
+ InversionStep(p, v, uvLen, b, ref bc);
+ if (Nat.IsOne(len, v))
+ {
+ InversionResult(p, bc, b, z);
+ return;
+ }
+ }
+ }
+ }
+
+ public static uint[] Random(uint[] p)
+ {
+ int len = p.Length;
+ Random rand = new Random();
+ uint[] s = Nat.Create(len);
+
+ uint m = p[len - 1];
+ m |= m >> 1;
+ m |= m >> 2;
+ m |= m >> 4;
+ m |= m >> 8;
+ m |= m >> 16;
+
+ do
+ {
+ byte[] bytes = new byte[len << 2];
+ rand.NextBytes(bytes);
+ Pack.BE_To_UInt32(bytes, 0, s);
+ s[len - 1] &= m;
+ }
+ while (Nat.Gte(len, s, p));
+
+ return s;
+ }
+
+ public static void Add(uint[] p, uint[] x, uint[] y, uint[] z)
+ {
+ int len = p.Length;
+ uint c = Nat.Add(len, x, y, z);
+ if (c != 0)
+ {
+ Nat.SubFrom(len, p, z);
+ }
+ }
+
+ public static void Subtract(uint[] p, uint[] x, uint[] y, uint[] z)
+ {
+ int len = p.Length;
+ int c = Nat.Sub(len, x, y, z);
+ if (c != 0)
+ {
+ Nat.AddTo(len, p, z);
+ }
+ }
+
+ private static void InversionResult(uint[] p, int ac, uint[] a, uint[] z)
+ {
+ if (ac < 0)
+ {
+ Nat.Add(p.Length, a, p, z);
+ }
+ else
+ {
+ Array.Copy(a, 0, z, 0, p.Length);
+ }
+ }
+
+ private static void InversionStep(uint[] p, uint[] u, int uLen, uint[] x, ref int xc)
+ {
+ int len = p.Length;
+ int count = 0;
+ while (u[0] == 0)
+ {
+ Nat.ShiftDownWord(uLen, u, 0);
+ count += 32;
+ }
+
+ {
+ int zeroes = GetTrailingZeroes(u[0]);
+ if (zeroes > 0)
+ {
+ Nat.ShiftDownBits(uLen, u, zeroes, 0);
+ count += zeroes;
+ }
+ }
+
+ for (int i = 0; i < count; ++i)
+ {
+ if ((x[0] & 1) != 0)
+ {
+ if (xc < 0)
+ {
+ xc += (int)Nat.AddTo(len, p, x);
+ }
+ else
+ {
+ xc += Nat.SubFrom(len, p, x);
+ }
+ }
+
+ Debug.Assert(xc == 0 || xc == -1);
+ Nat.ShiftDownBit(len, x, (uint)xc);
+ }
+ }
+
+ private static int GetTrailingZeroes(uint x)
+ {
+ Debug.Assert(x != 0);
+ int count = 0;
+ while ((x & 1) == 0)
+ {
+ x >>= 1;
+ ++count;
+ }
+ return count;
+ }
+ }
+}
|
