Add fast coprime test

1 files changed, 185 insertions, 38 deletions

diff --git a/crypto/src/math/raw/Mod.cs b/crypto/src/math/raw/Mod.cs
index bc5942711..984c4808d 100644
--- a/crypto/src/math/raw/Mod.cs
+++ b/crypto/src/math/raw/Mod.cs
@@ -112,7 +112,7 @@ namespace Org.BouncyCastle.Math.Raw
             Decode30(bits, D, 0, z, 0);
             Debug.Assert(0 != Nat.LessThan(m.Length, z, m));
 
-            return (uint)(EqualTo(len30, F, 1) & EqualToZero(len30, G));
+            return (uint)(EqualTo(len30, F, 1) & EqualTo(len30, G, 0));
 #endif
         }
 
@@ -163,7 +163,7 @@ namespace Org.BouncyCastle.Math.Raw
             Decode30(bits, D, z);
             Debug.Assert(0 != Nat.LessThan(m.Length, z, m));
 
-            return (uint)(EqualTo(len30, F, 1) & EqualToZero(len30, G));
+            return (uint)(EqualTo(len30, F, 1) & EqualTo(len30, G, 0));
         }
 #endif
 
@@ -199,7 +199,7 @@ namespace Org.BouncyCastle.Math.Raw
             int maxDivsteps = GetMaximumDivsteps(bits) - clz;
 
             int divsteps = 0;
-            while (!EqualToZeroVar_Unlikely(lenFG, G))
+            while (!EqualToVar(lenFG, G, 0))
             {
                 if (divsteps >= maxDivsteps)
                     return false;
@@ -231,7 +231,7 @@ namespace Org.BouncyCastle.Math.Raw
             }
             Debug.Assert(0 == signF);
 
-            if (!EqualToOneVar_Expected(lenFG, F))
+            if (!EqualToVar(lenFG, F, 1))
                 return false;
 
             if (signD < 0)
@@ -282,7 +282,7 @@ namespace Org.BouncyCastle.Math.Raw
             int maxDivsteps = GetMaximumDivsteps(bits) - clz;
 
             int divsteps = 0;
-            while (!EqualToZeroVar_Unlikely(lenFG, G))
+            while (!EqualToVar(lenFG, G, 0))
             {
                 if (divsteps >= maxDivsteps)
                     return false;
@@ -314,7 +314,7 @@ namespace Org.BouncyCastle.Math.Raw
             }
             Debug.Assert(0 == signF);
 
-            if (!EqualToOneVar_Expected(lenFG, F))
+            if (!EqualToVar(lenFG, F, 1))
                 return false;
 
             if (signD < 0)
@@ -330,6 +330,182 @@ namespace Org.BouncyCastle.Math.Raw
         }
 #endif
 
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+        public static uint ModOddIsCoprime(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x)
+        {
+            int len32 = m.Length;
+            Debug.Assert(len32 > 0);
+            Debug.Assert((m[0] & 1) != 0);
+            Debug.Assert(m[len32 - 1] != 0);
+
+            int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]);
+            int len30 = (bits + 29) / 30;
+
+            int allocSize = len30 * 3;
+            Span<int> alloc = (allocSize * Integers.NumBytes <= MaxStackAlloc)
+                ? stackalloc int[allocSize]
+                : new int[allocSize];
+
+            Span<int> t = stackalloc int[4];
+            Span<int> F = alloc[..len30]; alloc = alloc[len30..];
+            Span<int> G = alloc[..len30]; alloc = alloc[len30..];
+            Span<int> M = alloc[..len30];
+
+            Encode30(bits, x, G);
+            Encode30(bits, m, M);
+            M.CopyTo(F);
+
+            int delta = 0;
+            int maxDivsteps = GetMaximumDivsteps(bits);
+
+            for (int divSteps = 0; divSteps < maxDivsteps; divSteps += 30)
+            {
+                delta = Divsteps30(delta, F[0], G[0], t);
+                UpdateFG30(len30, F, G, t);
+            }
+
+            int signF = F[len30 - 1] >> 31;
+            CNegate30(len30, signF, F);
+
+            return (uint)(EqualTo(len30, F, 1) & EqualTo(len30, G, 0));
+        }
+#else
+        public static uint ModOddIsCoprime(uint[] m, uint[] x)
+        {
+            int len32 = m.Length;
+            Debug.Assert(len32 > 0);
+            Debug.Assert((m[0] & 1) != 0);
+            Debug.Assert(m[len32 - 1] != 0);
+
+            int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]);
+            int len30 = (bits + 29) / 30;
+
+            int[] t = new int[4];
+            int[] F = new int[len30];
+            int[] G = new int[len30];
+            int[] M = new int[len30];
+
+            Encode30(bits, x, 0, G, 0);
+            Encode30(bits, m, 0, M, 0);
+            Array.Copy(M, 0, F, 0, len30);
+
+            int delta = 0;
+            int maxDivsteps = GetMaximumDivsteps(bits);
+
+            for (int divSteps = 0; divSteps < maxDivsteps; divSteps += 30)
+            {
+                delta = Divsteps30(delta, F[0], G[0], t);
+                UpdateFG30(len30, F, G, t);
+            }
+
+            int signF = F[len30 - 1] >> 31;
+            CNegate30(len30, signF, F);
+
+            return (uint)(EqualTo(len30, F, 1) & EqualTo(len30, G, 0));
+        }
+#endif
+
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+        public static bool ModOddIsCoprimeVar(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x)
+        {
+            int len32 = m.Length;
+            Debug.Assert(len32 > 0);
+            Debug.Assert((m[0] & 1) != 0);
+            Debug.Assert(m[len32 - 1] != 0);
+
+            int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]);
+            int len30 = (bits + 29) / 30;
+
+            int allocSize = len30 * 3;
+            Span<int> alloc = (allocSize * Integers.NumBytes <= MaxStackAlloc)
+                ? stackalloc int[allocSize]
+                : new int[allocSize];
+
+            Span<int> t = stackalloc int[4];
+            Span<int> F = alloc[..len30]; alloc = alloc[len30..];
+            Span<int> G = alloc[..len30]; alloc = alloc[len30..];
+            Span<int> M = alloc[..len30];
+
+            Encode30(bits, x, G);
+            Encode30(bits, m, M);
+            M.CopyTo(F);
+
+            int clz = System.Math.Max(0, bits - 1 - Nat.GetBitLength(len32, x));
+            int eta = -1 - clz;
+            int lenFG = len30;
+            int maxDivsteps = GetMaximumDivsteps(bits) - clz;
+
+            int divsteps = 0;
+            while (!EqualToVar(lenFG, G, 0))
+            {
+                if (divsteps >= maxDivsteps)
+                    return false;
+
+                divsteps += 30;
+
+                eta = Divsteps30Var(eta, F[0], G[0], t);
+                UpdateFG30(lenFG, F, G, t);
+                lenFG = TrimFG30Var(lenFG, F, G);
+            }
+
+            int signF = F[lenFG - 1] >> 31;
+            if (signF < 0)
+            {
+                signF = Negate30(lenFG, F);
+            }
+            Debug.Assert(0 == signF);
+
+            return EqualToVar(lenFG, F, 1);
+        }
+#else
+        public static bool ModOddIsCoprimeVar(uint[] m, uint[] x)
+        {
+            int len32 = m.Length;
+            Debug.Assert(len32 > 0);
+            Debug.Assert((m[0] & 1) != 0);
+            Debug.Assert(m[len32 - 1] != 0);
+
+            int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]);
+            int len30 = (bits + 29) / 30;
+
+            int[] t = new int[4];
+            int[] F = new int[len30];
+            int[] G = new int[len30];
+            int[] M = new int[len30];
+
+            Encode30(bits, x, 0, G, 0);
+            Encode30(bits, m, 0, M, 0);
+            Array.Copy(M, 0, F, 0, len30);
+
+            int clz = System.Math.Max(0, bits - 1 - Nat.GetBitLength(len32, x));
+            int eta = -1 - clz;
+            int lenFG = len30;
+            int maxDivsteps = GetMaximumDivsteps(bits) - clz;
+
+            int divsteps = 0;
+            while (!EqualToVar(lenFG, G, 0))
+            {
+                if (divsteps >= maxDivsteps)
+                    return false;
+
+                divsteps += 30;
+
+                eta = Divsteps30Var(eta, F[0], G[0], t);
+                UpdateFG30(lenFG, F, G, t);
+                lenFG = TrimFG30Var(lenFG, F, G);
+            }
+
+            int signF = F[lenFG - 1] >> 31;
+            if (signF < 0)
+            {
+                signF = Negate30(lenFG, F);
+            }
+            Debug.Assert(0 == signF);
+
+            return EqualToVar(lenFG, F, 1);
+        }
+#endif
+
         public static uint[] Random(SecureRandom random, uint[] p)
         {
             int len = p.Length;
@@ -692,41 +868,12 @@ namespace Org.BouncyCastle.Math.Raw
         }
 
 #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
-        private static bool EqualToOneVar_Expected(int len, ReadOnlySpan<int> x)
+        private static bool EqualToVar(int len, ReadOnlySpan<int> x, int y)
 #else
-        private static bool EqualToOneVar_Expected(int len, int[] x)
+        private static bool EqualToVar(int len, int[] x, int y)
 #endif
         {
-            int d = x[0] ^ 1;
-            for (int i = 1; i < len; ++i)
-            {
-                d |= x[i];
-            }
-            return d == 0;
-        }
-
-#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
-        private static int EqualToZero(int len, ReadOnlySpan<int> x)
-#else
-        private static int EqualToZero(int len, int[] x)
-#endif
-        {
-            int d = 0;
-            for (int i = 0; i < len; ++i)
-            {
-                d |= x[i];
-            }
-            d = (int)((uint)d >> 1) | (d & 1);
-            return (d - 1) >> 31;
-        }
-
-#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
-        private static bool EqualToZeroVar_Unlikely(int len, ReadOnlySpan<int> x)
-#else
-        private static bool EqualToZeroVar_Unlikely(int len, int[] x)
-#endif
-        {
-            int d = x[0];
+            int d = x[0] ^ y;
             if (d != 0)
                 return false;