Replace BikePolynomial with new BikeRing

- more efficient polynomial ring implementation
- refactor BikeEngine (performance)

4 files changed, 399 insertions, 508 deletions

diff --git a/crypto/src/pqc/crypto/bike/BikeEngine.cs b/crypto/src/pqc/crypto/bike/BikeEngine.cs
index a872c68a7..94f073bbb 100644
--- a/crypto/src/pqc/crypto/bike/BikeEngine.cs
+++ b/crypto/src/pqc/crypto/bike/BikeEngine.cs
@@ -1,5 +1,5 @@
 using System;
-
+using System.Diagnostics;
 using Org.BouncyCastle.Crypto;
 using Org.BouncyCastle.Crypto.Digests;
 using Org.BouncyCastle.Security;
@@ -10,29 +10,29 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
     internal sealed class BikeEngine
     {
         // degree of R
-        private int r;
+        private readonly int r;
 
         // the row weight
-        private int w;
+        private readonly int w;
 
         // Hamming weight of h0, h1
-        private int hw;
+        private readonly int hw;
 
         // the error weight
-        private int t;
+        private readonly int t;
 
         //the shared secret size
-        private int l;
+        private readonly int l;
 
         // number of iterations in BGF decoder
-        private int nbIter;
+        private readonly int nbIter;
 
         // tau
-        private int tau;
+        private readonly int tau;
 
-        private BikePolynomial reductionPoly;
-        private int L_BYTE;
-        private int R_BYTE;
+        private readonly BikeRing bikeRing;
+        private readonly int L_BYTE;
+        private readonly int R_BYTE;
 
         internal BikeEngine(int r, int w, int t, int l, int nbIter, int tau)
         {
@@ -45,9 +45,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             this.hw = this.w / 2;
             this.L_BYTE = l / 8;
             this.R_BYTE = (r + 7) / 8;
-
-            // generate reductionPoly (X^r + 1)
-            this.reductionPoly = new BikePolynomial(r);
+            this.bikeRing = new BikeRing(r);
         }
 
         internal int SessionKeySize => L_BYTE;
@@ -59,24 +57,21 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             return BikeUtilities.GenerateRandomByteArray(r * 2, 2 * R_BYTE, t, digest);
         }
 
-        private byte[] FunctionL(byte[] e0, byte[] e1)
+        private void FunctionL(byte[] e0, byte[] e1, byte[] result)
         {
             byte[] hashRes = new byte[48];
-            byte[] res = new byte[L_BYTE];
 
             Sha3Digest digest = new Sha3Digest(384);
             digest.BlockUpdate(e0, 0, e0.Length);
             digest.BlockUpdate(e1, 0, e1.Length);
             digest.DoFinal(hashRes, 0);
 
-            Array.Copy(hashRes, 0, res, 0, L_BYTE);
-            return res;
+            Array.Copy(hashRes, 0, result, 0, L_BYTE);
         }
 
-        private byte[] FunctionK(byte[] m, byte[] c0, byte[] c1)
+        private void FunctionK(byte[] m, byte[] c0, byte[] c1, byte[] result)
         {
             byte[] hashRes = new byte[48];
-            byte[] res = new byte[L_BYTE];
 
             Sha3Digest digest = new Sha3Digest(384);
             digest.BlockUpdate(m, 0, m.Length);
@@ -84,8 +79,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             digest.BlockUpdate(c1, 0, c1.Length);
             digest.DoFinal(hashRes, 0);
 
-            Array.Copy(hashRes, 0, res, 0, L_BYTE);
-            return res;
+            Array.Copy(hashRes, 0, result, 0, L_BYTE);
         }
 
         /**
@@ -113,34 +107,17 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             digest.BlockUpdate(seed1, 0, seed1.Length);
 
             // 1. Randomly generate h0, h1
-            byte[] h0Tmp = BikeUtilities.GenerateRandomByteArray(r, R_BYTE, hw, digest);
-            byte[] h1Tmp = BikeUtilities.GenerateRandomByteArray(r, R_BYTE, hw, digest);
-
-            Array.Copy(h0Tmp, 0, h0, 0, h0.Length);
-            Array.Copy(h1Tmp, 0, h1, 0, h1.Length);
-
-            byte[] h1Bits = new byte[r];
-            byte[] h0Bits = new byte[r];
-
-            BikeUtilities.FromByteArrayToBitArray(h0Bits, h0Tmp);
-            BikeUtilities.FromByteArrayToBitArray(h1Bits, h1Tmp);
+            ulong[] h0Element = bikeRing.GenerateRandom(hw, digest);
+            ulong[] h1Element = bikeRing.GenerateRandom(hw, digest);
 
-            // remove last 0 bits (most significant bits with 0 mean non-sense)
-            byte[] h0Cut = BikeUtilities.RemoveLast0Bits(h0Bits);
-            byte[] h1Cut = BikeUtilities.RemoveLast0Bits(h1Bits);
+            bikeRing.EncodeBytes(h0Element, h0);
+            bikeRing.EncodeBytes(h1Element, h1);
 
             // 2. Compute h
-            BikePolynomial h0Poly = new BikePolynomial(h0Cut);
-            BikePolynomial h1Poly = new BikePolynomial(h1Cut);
-
-            BikePolynomial h0Inv = h0Poly.ModInverseBigDeg(reductionPoly);
-            BikePolynomial hPoly = h1Poly.ModKaratsubaMultiplyBigDeg(h0Inv, reductionPoly);
-
-            // Get coefficients of hPoly
-            byte[] hTmp = hPoly.GetEncoded();
-            byte[] hByte = new byte[R_BYTE];
-            BikeUtilities.FromBitArrayToByteArray(hByte, hTmp);
-            Array.Copy(hByte, 0, h, 0, h.Length);
+            ulong[] hElement = bikeRing.Create();
+            bikeRing.Inv(h0Element, hElement);
+            bikeRing.Multiply(hElement, h1Element, hElement);
+            bikeRing.EncodeBytes(hElement, h);
 
             //3. Parse seed2 as sigma
             Array.Copy(seed2, 0, sigma, 0, sigma.Length);
@@ -172,40 +149,35 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             BikeUtilities.FromByteArrayToBitArray(eBits, eBytes);
 
             byte[] e0Bits = Arrays.CopyOfRange(eBits, 0, r);
+            byte[] e0Bytes = new byte[R_BYTE];
+            BikeUtilities.FromBitArrayToByteArray(e0Bytes, e0Bits);
+
             byte[] e1Bits = Arrays.CopyOfRange(eBits, r, eBits.Length);
+            byte[] e1Bytes = new byte[R_BYTE];
+            BikeUtilities.FromBitArrayToByteArray(e1Bytes, e1Bits);
 
-            // remove last 0 bits (most significant bits with 0 mean no sense)
-            byte[] e0Cut = BikeUtilities.RemoveLast0Bits(e0Bits);
-            byte[] e1Cut = BikeUtilities.RemoveLast0Bits(e1Bits);
+            ulong[] e0Element = bikeRing.Create();
+            ulong[] e1Element = bikeRing.Create();
 
-            BikePolynomial e0 = new BikePolynomial(e0Cut);
-            BikePolynomial e1 = new BikePolynomial(e1Cut);
+            bikeRing.DecodeBytes(e0Bytes, e0Element);
+            bikeRing.DecodeBytes(e1Bytes, e1Element);
+
+            ulong[] hElement = bikeRing.Create();
+            bikeRing.DecodeBytes(h, hElement);
 
             // 3. Calculate c
             // calculate c0
-            byte[] h0Bits = new byte[r];
-            BikeUtilities.FromByteArrayToBitArray(h0Bits, h);
-            BikePolynomial hPoly = new BikePolynomial(BikeUtilities.RemoveLast0Bits(h0Bits));
-            BikePolynomial c0Poly = e0.Add(e1.ModKaratsubaMultiplyBigDeg(hPoly, reductionPoly));
-
-            byte[] c0Bits = c0Poly.GetEncoded();
-            byte[] c0Bytes = new byte[R_BYTE];
-            BikeUtilities.FromBitArrayToByteArray(c0Bytes, c0Bits);
-            Array.Copy(c0Bytes, 0, c0, 0, c0.Length);
+            ulong[] c0Element = bikeRing.Create();
+            bikeRing.Multiply(e1Element, hElement, c0Element);
+            bikeRing.Add(c0Element, e0Element, c0Element);
+            bikeRing.EncodeBytes(c0Element, c0);
 
             //calculate c1
-            byte[] e0Bytes = new byte[R_BYTE];
-            BikeUtilities.FromBitArrayToByteArray(e0Bytes, e0Bits);
-            byte[] e1Bytes = new byte[R_BYTE];
-            BikeUtilities.FromBitArrayToByteArray(e1Bytes, e1Bits);
-
-            byte[] tmp = FunctionL(e0Bytes, e1Bytes);
-            byte[] c1Tmp = BikeUtilities.XorBytes(m, tmp, L_BYTE);
-            Array.Copy(c1Tmp, 0, c1, 0, c1.Length);
+            FunctionL(e0Bytes, e1Bytes, c1);
+            BikeUtilities.XorTo(m, c1, L_BYTE);
 
             // 4. Calculate K
-            byte[] kTmp = FunctionK(m, c0, c1);
-            Array.Copy(kTmp, 0, k, 0, kTmp.Length);
+            FunctionK(m, c0, c1, k);
         }
 
         /**
@@ -221,18 +193,6 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
          **/
         internal void Decaps(byte[] k, byte[] h0, byte[] h1, byte[] sigma, byte[] c0, byte[] c1)
         {
-            //convert to bits
-            byte[] c0Bits = new byte[this.r];
-            byte[] h0Bits = new byte[this.r];
-            byte[] sigmaBits = new byte[this.l];
-
-            BikeUtilities.FromByteArrayToBitArray(c0Bits, c0);
-            BikeUtilities.FromByteArrayToBitArray(h0Bits, h0);
-            BikeUtilities.FromByteArrayToBitArray(sigmaBits, sigma);
-
-            byte[] c0Cut = BikeUtilities.RemoveLast0Bits(c0Bits);
-            byte[] h0Cut = BikeUtilities.RemoveLast0Bits(h0Bits);
-
             // Get compact version of h0, h1
             int[] h0Compact = new int[hw];
             int[] h1Compact = new int[hw];
@@ -240,10 +200,10 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             ConvertToCompact(h1Compact, h1);
 
             // Compute syndrome
-            byte[] syndrome = ComputeSyndrome(c0Cut, h0Cut);
+            byte[] syndromeBits = ComputeSyndrome(c0, h0);
 
             // 1. Compute e'
-            byte[] ePrimeBits = BGFDecoder(syndrome, h0Compact, h1Compact);
+            byte[] ePrimeBits = BGFDecoder(syndromeBits, h0Compact, h1Compact);
             byte[] ePrimeBytes = new byte[2 * R_BYTE];
             BikeUtilities.FromBitArrayToByteArray(ePrimeBytes, ePrimeBits);
 
@@ -256,30 +216,31 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             BikeUtilities.FromBitArrayToByteArray(e1Bytes, e1Bits);
 
             // 2. Compute m'
-            byte[] mPrime = BikeUtilities.XorBytes(c1, FunctionL(e0Bytes, e1Bytes), L_BYTE);
+            byte[] mPrime = new byte[L_BYTE];
+            FunctionL(e0Bytes, e1Bytes, mPrime);
+            BikeUtilities.XorTo(c1, mPrime, L_BYTE);
 
             // 3. Compute K
-            byte[] tmpK = new byte[l];
             byte[] wlist = FunctionH(mPrime);
             if (Arrays.AreEqual(ePrimeBytes, wlist))
             {
-                tmpK = FunctionK(mPrime, c0, c1);
+                FunctionK(mPrime, c0, c1, k);
             }
             else
             {
-                tmpK = FunctionK(sigma, c0, c1);
+                FunctionK(sigma, c0, c1, k);
             }
-            Array.Copy(tmpK, 0, k, 0, tmpK.Length);
         }
 
-        private byte[] ComputeSyndrome(byte[] h0, byte[] c0)
+        private byte[] ComputeSyndrome(byte[] c0, byte[] h0)
         {
-            BikePolynomial coPoly = new BikePolynomial(c0);
-            BikePolynomial h0Poly = new BikePolynomial(h0);
-
-            BikePolynomial s = coPoly.ModKaratsubaMultiplyBigDeg(h0Poly, reductionPoly);
-            byte[] transposedS = Transpose(s.GetEncoded());
-            return transposedS;
+            ulong[] c0Element = bikeRing.Create();
+            ulong[] h0Element = bikeRing.Create();
+            bikeRing.DecodeBytes(c0, c0Element);
+            bikeRing.DecodeBytes(h0, h0Element);
+            ulong[] sElement = bikeRing.Create();
+            bikeRing.Multiply(c0Element, h0Element, sElement);
+            return Transpose(bikeRing.EncodeBits(sElement));
         }
 
         private byte[] BGFDecoder(byte[] s, int[] h0Compact, int[] h1Compact)
@@ -314,12 +275,11 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
 
         private byte[] Transpose(byte[] input)
         {
-            byte[] tmp = BikeUtilities.Append0s(input, r); // append zeros to s
             byte[] output = new byte[r];
-            output[0] = tmp[0];
+            output[0] = input[0];
             for (int i = 1; i < r; i++)
             {
-                output[i] = tmp[r - i];
+                output[i] = input[r - i];
             }
             return output;
         }
@@ -332,13 +292,14 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             // calculate for h0compact
             for (int j = 0; j < r; j++)
             {
-                if (Ctr(h0CompactCol, s, j) >= T)
+                int ctr = Ctr(h0CompactCol, s, j);
+                if (ctr >= T)
                 {
                     UpdateNewErrorIndex(e, j);
                     updatedIndices[j] = 1;
                     black[j] = 1;
                 }
-                else if (Ctr(h0CompactCol, s, j) >= T - tau)
+                else if (ctr >= T - tau)
                 {
                     gray[j] = 1;
                 }
@@ -347,13 +308,14 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             // calculate for h1Compact
             for (int j = 0; j < r; j++)
             {
-                if (Ctr(h1CompactCol, s, j) >= T)
+                int ctr = Ctr(h1CompactCol, s, j);
+                if (ctr >= T)
                 {
                     UpdateNewErrorIndex(e, r + j);
                     updatedIndices[r + j] = 1;
                     black[r + j] = 1;
                 }
-                else if (Ctr(h1CompactCol, s, j) >= T - tau)
+                else if (ctr >= T - tau)
                 {
                     gray[r + j] = 1;
                 }
@@ -369,13 +331,14 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             }
         }
 
-        private void BFMaskedIter(byte[] s, byte[] e, byte[] mask, int T, int[] h0Compact, int[] h1Compact, int[] h0CompactCol, int[] h1CompactCol)
+        private void BFMaskedIter(byte[] s, byte[] e, byte[] mask, int T, int[] h0Compact, int[] h1Compact,
+            int[] h0CompactCol, int[] h1CompactCol)
         {
             int[] updatedIndices = new int[2 * r];
 
             for (int j = 0; j < r; j++)
             {
-                if (Ctr(h0CompactCol, s, j) >= T && mask[j] == 1)
+                if (mask[j] == 1 && Ctr(h0CompactCol, s, j) >= T)
                 {
                     UpdateNewErrorIndex(e, j);
                     updatedIndices[j] = 1;
@@ -384,7 +347,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
 
             for (int j = 0; j < r; j++)
             {
-                if (Ctr(h1CompactCol, s, j) >= T && mask[r + j] == 1)
+                if (mask[r + j] == 1 && Ctr(h1CompactCol, s, j) >= T)
                 {
                     UpdateNewErrorIndex(e, r + j);
                     updatedIndices[r + j] = 1;
@@ -429,13 +392,20 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
 
         private int Ctr(int[] hCompactCol, byte[] s, int j)
         {
+            Debug.Assert(0 <= j && j < r);
+
             int count = 0;
             for (int i = 0; i < hw; i++)
             {
-                if (s[(hCompactCol[i] + j) % r] == 1)
-                {
-                    count += 1;
-                }
+                //int sPos = (hCompactCol[i] + j) % r;
+                int sPos = hCompactCol[i] + j - r;
+                sPos += (sPos >> 31) & r;
+
+                //if (s[sPos] == 1)
+                //{
+                //    count += 1;
+                //}
+                count += s[sPos];
             }
             return count;
         }
diff --git a/crypto/src/pqc/crypto/bike/BikePolynomial.cs b/crypto/src/pqc/crypto/bike/BikePolynomial.cs
deleted file mode 100644
index eea34d838..000000000
--- a/crypto/src/pqc/crypto/bike/BikePolynomial.cs
+++ /dev/null
@@ -1,365 +0,0 @@
-using System;
-
-using Org.BouncyCastle.Utilities;
-
-namespace Org.BouncyCastle.Pqc.Crypto.Bike
-{
-    internal class BikePolynomial
-    {
-        /**
-         * For the polynomial representation the map f: R->Z*,
-         * <tt>poly(X) -> [coef_0, coef_1, ...]</tt> is used, where
-         * <tt>coef_i</tt> is the <tt>i</tt>th coefficient of the polynomial
-         * represented as int (see {@link GF2mField}). The polynomials are stored
-         * as int arrays.
-         */
-        private readonly int[] m_coefficients;
-
-        /**
-         * Construct a monomial of the given degree over the finite field GF(2^m).
-         *
-         * @param field  the finite field GF(2^m)
-         * @param degree the degree of the monomial
-         */
-        internal BikePolynomial(int degree)
-        {
-            // Initial value (X^degree + 1)
-            this.m_coefficients = new int[degree + 1];
-            this.m_coefficients[degree] = 1;
-            this.m_coefficients[0] ^= 1;
-        }
-
-        /**
-         * Construct the polynomial over the given finite field GF(2^m) from the
-         * given coefficient vector.
-         *
-         * @param field  finite field GF2m
-         * @param coeffs the coefficient vector
-         */
-        private BikePolynomial(int[] coeffs)
-        {
-            this.m_coefficients = coeffs;
-        }
-
-        /**
-         * Create a polynomial over the finite field GF(2^m).
-         *
-         * @param field the finite field GF(2^m)
-         * @param enc   byte[] polynomial in byte array form
-         */
-        internal BikePolynomial(byte[] enc)
-        {
-            // decodes polynomial
-            this.m_coefficients = new int[enc.Length];
-            for (int i = 0; i < m_coefficients.Length; i++)
-            {
-                m_coefficients[i] = enc[i];
-                if ((m_coefficients[i] >> 1) != 0)
-                    throw new ArgumentException(
-                        "Error: byte array is not encoded polynomial over given finite field GF2m");
-            }
-            // if HC = 0 for non-zero polynomial, returns error
-            if ((m_coefficients.Length != 1) && (m_coefficients[m_coefficients.Length - 1] == 0))
-                throw new ArgumentException("Error: byte array is not encoded polynomial over given finite field GF2m");
-        }
-
-        /**
-         * Returns encoded polynomial, i.e., this polynomial in byte array form
-         *
-         * @return the encoded polynomial
-         */
-        internal byte[] GetEncoded()
-        {
-            byte[] res = new byte[m_coefficients.Length];
-            for (int i = 0; i < m_coefficients.Length; i++)
-            {
-                res[i] = (byte)m_coefficients[i];
-            }
-            return res;
-        }
-
-        /**
-         * Compute the sum of this polynomial and the given polynomial.
-         *
-         * @param addend the addend
-         * @return <tt>this + a</tt> (newly created)
-         */
-        internal BikePolynomial Add(BikePolynomial addend)
-        {
-            int[] resultCoeff = Add(m_coefficients, addend.m_coefficients);
-            return new BikePolynomial(NormalForm(resultCoeff));
-        }
-
-        /**
-         * Compute the sum of two polynomials a and b over the finite field
-         * <tt>GF(2^m)</tt>.
-         *
-         * @param a the first polynomial
-         * @param b the second polynomial
-         * @return a + b
-         */
-        private static int[] Add(int[] a, int[] b)
-        {
-            int[] result, addend;
-            if (a.Length < b.Length)
-            {
-                result = new int[b.Length];
-                Array.Copy(b, 0, result, 0, b.Length);
-                addend = a;
-            }
-            else
-            {
-                result = new int[a.Length];
-                Array.Copy(a, 0, result, 0, a.Length);
-                addend = b;
-            }
-
-            for (int i = addend.Length - 1; i >= 0; i--)
-            {
-                result[i] ^= addend[i];
-            }
-
-            return result;
-        }
-
-        private static void AddAt(int[] x, int[] z, int zPos)
-        {
-            for (int i = 0; i < x.Length; ++i)
-            {
-                z[zPos + i] ^= x[i];
-            }
-        }
-
-        /**
-         * Compute the result of the division of two polynomials over the field
-         * <tt>GF(2^m)</tt>.
-         *
-         * @param a the first polynomial
-         * @param f the second polynomial
-         * @return int[][] {q,r}, where a = q*f+r and deg(r) &lt; deg(f);
-         */
-        private static int[][] Div(int[] a, int[] f)
-        {
-            int df = ComputeDegree(f);
-            if (df == -1)
-                throw new ArithmeticException("Division by zero.");
-
-            int degreeR1 = ComputeDegree(a);
-            int[][] result = new int[2][];
-            result[0] = new int[System.Math.Max(0, degreeR1 - df) + 1];
-            result[1] = Arrays.CopyOf(a, degreeR1 + 1);
-
-            while (df <= degreeR1)
-            {
-                int n = degreeR1 - df;
-                result[0][n] ^= 1;
-                AddAt(f, result[1], n);
-                degreeR1 = ComputeDegree(result[1], degreeR1 - 1);
-            }
-            result[1] = NormalForm(result[1]);
-            return result;
-        }
-
-        /**
-         * Reduce a polynomial modulo another polynomial.
-         *
-         * @param a the polynomial
-         * @param f the reduction polynomial
-         * @return <tt>a mod f</tt>
-         */
-        private static int[] Mod(int[] a, int[] f)
-        {
-            int df = ComputeDegree(f);
-            if (df == -1)
-                throw new ArithmeticException("Division by zero");
-
-            int degreeR = ComputeDegree(a);
-            int[] result = Arrays.CopyOf(a, degreeR + 1);
-
-            while (df <= degreeR)
-            {
-                int n = degreeR - df;
-                AddAt(f, result, n);
-                degreeR = ComputeDegree(result, degreeR - 1);
-            }
-            return NormalForm(result);
-        }
-
-        /**
-         * Compute the degree of a polynomial.
-         *
-         * @param a the polynomial
-         * @return the degree of the polynomial <tt>a</tt>. If <tt>a</tt> is
-         *         the zero polynomial, return -1.
-         */
-        private static int ComputeDegree(int[] a)
-        {
-            return ComputeDegree(a, a.Length - 1);
-        }
-
-        private static int ComputeDegree(int[] a, int from)
-        {
-            int degree;
-            for (degree = from; degree >= 0 && a[degree] == 0; degree--)
-            {
-            }
-            return degree;
-        }
-
-        /**
-         * Strip leading zero coefficients from the given polynomial.
-         *
-         * @param a the polynomial
-         * @return the reduced polynomial
-         */
-        private static int[] NormalForm(int[] a)
-        {
-            int d = ComputeDegree(a);
-
-            // if a is the zero polynomial
-            if (d == -1)
-            {
-                // return new zero polynomial
-                return new int[1];
-            }
-
-            // if a already is in normal form
-            if (a.Length == d + 1)
-            {
-                // return a clone of a
-                return Arrays.Clone(a);
-            }
-
-            // else, reduce a
-            int[] result = new int[d + 1];
-            Array.Copy(a, 0, result, 0, d + 1);
-            return result;
-        }
-
-        /**
-         * Compute the product of this polynomial and another polynomial modulo a
-         * third polynomial.
-         *
-         * @param a another polynomial
-         * @param b the reduction polynomial
-         * @return <tt>this * a mod b</tt>
-         */
-        internal BikePolynomial ModKaratsubaMultiplyBigDeg(BikePolynomial a, BikePolynomial b)
-        {
-            int[] resultCoeff = ModKaratsubaMultiplyBigDeg(m_coefficients, a.m_coefficients, b.m_coefficients);
-            return new BikePolynomial(resultCoeff);
-        }
-
-        /**
-         * Compute the inverse of this polynomial modulo the given polynomial.
-         *
-         * @param a the reduction polynomial
-         * @return <tt>this^(-1) mod a</tt>
-         */
-        internal BikePolynomial ModInverseBigDeg(BikePolynomial a)
-        {
-            int[] resultCoeff = ModInvBigDeg(m_coefficients, a.m_coefficients);
-            return new BikePolynomial(resultCoeff);
-        }
-
-        private static int[] ModInvBigDeg(int[] b, int[] g)
-        {
-            int[] r0 = NormalForm(g);
-            int[] r1 = Mod(b, g);
-            int[] s0 = { 0 };
-            int[] s1 = { 1 };
-            int[] s2;
-            int[][] q;
-            while (ComputeDegree(r1) != -1)
-            {
-                q = Div(r0, r1);
-                r0 = NormalForm(r1);
-                r1 = NormalForm(q[1]);
-                s2 = Add(s0, ModKaratsubaMultiplyBigDeg(q[0], s1, g));
-                s0 = NormalForm(s1);
-                s1 = NormalForm(s2);
-            }
-            return s0;
-        }
-
-        /**
-         * Compute the product of two polynomials modulo a third polynomial over the
-         * finite field <tt>GF(2^m)</tt>.
-         *
-         * @param aa the first polynomial
-         * @param bb the second polynomial
-         * @param g the reduction polynomial
-         * @return <tt>a * b mod g</tt>
-         */
-        private static int[] ModKaratsubaMultiplyBigDeg(int[] aa, int[] bb, int[] g)
-        {
-            int[] a, b;
-            if (aa.Length >= bb.Length)
-            {
-                a = aa;
-                b = bb;
-            }
-            else
-            {
-                a = bb;
-                b = aa;
-            }
-
-            int n = a.Length;
-            int m = b.Length;
-
-            int[] D = new int[(n + m) / 2];
-            int[] S = new int[n + m - 1];
-            int[] T = new int[n + m - 1];
-            int[] C = new int[n + m - 1];
-
-            for (int i = 0; i < m; i++)
-            {
-                D[i] = a[i] * b[i];
-            }
-
-            for (int i = 1; i < n + m - 2; i++)
-            {
-                int pLimit = System.Math.Min(m, (i + 1) >> 1);
-                for (int p = 0; p < pLimit; p++)
-                {
-                    int q = i - p;
-                    int aq = q < a.Length ? a[q] : 0;
-
-                    if (q < m)
-                    {
-                        S[i] += (a[p] + aq) * (b[p] + b[q]);
-                        T[i] += D[p] + D[q];
-                    }
-                    else if (q < n)
-                    {
-                        S[i] += (a[p] + aq) * b[p];
-                        T[i] += D[p];
-                    }
-                }
-            }
-
-            for (int i = 0; i < n + m - 1; i++)
-            {
-                if (i == 0)
-                {
-                    C[i] = D[i] % 2;
-                }
-                else if (i == n + m - 2)
-                {
-                    C[i] = (a[a.Length - 1] * b[b.Length - 1]) % 2;
-                }
-                else if (i % 2 == 1)
-                {
-                    C[i] = (S[i] - T[i]) % 2;
-                }
-                else
-                {
-                    C[i] = (S[i] - T[i] + D[i / 2]) % 2;
-                }
-            }
-
-            return Mod(C, g);
-        }
-    }
-}
diff --git a/crypto/src/pqc/crypto/bike/BikeRing.cs b/crypto/src/pqc/crypto/bike/BikeRing.cs
new file mode 100644
index 000000000..c2b2102b8
--- /dev/null
+++ b/crypto/src/pqc/crypto/bike/BikeRing.cs
@@ -0,0 +1,314 @@
+using System;
+using System.Diagnostics;
+#if NETCOREAPP3_0_OR_GREATER
+using System.Runtime.Intrinsics;
+using System.Runtime.Intrinsics.X86;
+#endif
+
+using Org.BouncyCastle.Crypto;
+using Org.BouncyCastle.Crypto.Utilities;
+using Org.BouncyCastle.Math.Raw;
+using Org.BouncyCastle.Utilities;
+
+namespace Org.BouncyCastle.Pqc.Crypto.Bike
+{
+    internal sealed class BikeRing
+    {
+        private readonly int m_bits;
+        private readonly int m_size;
+        private readonly int m_sizeExt;
+
+        internal BikeRing(int r)
+        {
+            if ((r & 0x80000001) != 1)
+                throw new ArgumentException();
+
+            m_bits = r;
+            m_size = (r + 63) >> 6;
+            m_sizeExt = m_size * 2;
+        }
+
+        internal void Add(ulong[] x, ulong[] y, ulong[] z)
+        {
+            for (int i = 0; i < Size; ++i)
+            {
+                z[i] = x[i] ^ y[i];
+            }
+        }
+
+        internal void Copy(ulong[] x, ulong[] z)
+        {
+            for (int i = 0; i < Size; ++i)
+            {
+                z[i] = x[i];
+            }
+        }
+
+        internal ulong[] Create()
+        {
+            return new ulong[Size];
+        }
+
+        internal ulong[] CreateExt()
+        {
+            return new ulong[SizeExt];
+        }
+
+        internal ulong[] DecodeBits(byte[] bs)
+        {
+            if (bs.Length > m_bits)
+                throw new ArgumentException();
+
+            ulong[] z = Create();
+            for (int i = 0; i < bs.Length; ++i)
+            {
+                ulong bit = bs[i];
+                if ((bit >> 1) != 0UL)
+                    throw new ArgumentException();
+
+                z[i >> 6] |= bit << (i & 63);
+            }
+            return z;
+        }
+
+        internal void DecodeBytes(byte[] bs, ulong[] z)
+        {
+            int partialBits = m_bits & 63;
+            Pack.LE_To_UInt64(bs, 0, z, 0, Size - 1);
+            byte[] last = new byte[8];
+            Array.Copy(bs, (Size - 1) << 3, last, 0, (partialBits + 7) >> 3);
+            z[Size - 1] = Pack.LE_To_UInt64(last);
+            Debug.Assert((z[Size - 1] >> partialBits) == 0);
+        }
+
+        internal byte[] EncodeBits(ulong[] x)
+        {
+            byte[] bs = new byte[m_bits];
+            for (int i = 0; i < m_bits; ++i)
+            {
+                bs[i] = (byte)((x[i >> 6] >> (i & 63)) & 1UL);
+            }
+            return bs;
+        }
+
+        internal void EncodeBytes(ulong[] x, byte[] bs)
+        {
+            int partialBits = m_bits & 63;
+            Debug.Assert((x[Size - 1] >> partialBits) == 0);
+            Pack.UInt64_To_LE(x, 0, Size - 1, bs, 0);
+            byte[] last = new byte[8];
+            Pack.UInt64_To_LE(x[Size - 1], last);
+            Array.Copy(last, 0, bs, (Size - 1) << 3, (partialBits + 7) >> 3);
+        }
+
+        internal ulong[] GenerateRandom(int weight, IXof digest)
+        {
+            byte[] buf = new byte[4];
+            int highest = Integers.HighestOneBit(m_bits);
+            int mask = highest | (highest - 1);
+
+            ulong[] z = Create();
+            int count = 0;
+            while (count < weight)
+            {
+                digest.Output(buf, 0, 4);
+                int candidate = (int)Pack.LE_To_UInt32(buf) & mask;
+                if (candidate < m_bits)
+                {
+                    int pos = candidate >> 6;
+                    ulong bit = 1UL << (candidate & 63);
+                    if ((z[pos] & bit) == 0UL)
+                    {
+                        z[pos] |= bit;
+                        ++count;
+                    }
+                }
+            }
+            return z;
+        }
+
+        internal void Inv(ulong[] a, ulong[] z)
+        {
+            ulong[] f = Create();
+            ulong[] g = Create();
+            ulong[] t = Create();
+
+            Copy(a, f);
+            Copy(a, t);
+
+            int rSub2 = m_bits - 2;
+            int bits = 32 - Integers.NumberOfLeadingZeros(rSub2);
+
+            for (int i = 1; i < bits; ++i)
+            {
+                SquareN(f, 1 << (i - 1), g);
+                Multiply(f, g, f);
+
+                if ((rSub2 & (1 << i)) != 0)
+                {
+                    int n = rSub2 & ((1 << i) - 1);
+                    SquareN(f, n, g);
+                    Multiply(t, g, t);
+                }
+            }
+
+            Square(t, z);
+        }
+
+        internal void Multiply(ulong[] x, ulong[] y, ulong[] z)
+        {
+            ulong[] tt = CreateExt();
+            ImplMultiplyAcc(x, y, tt);
+            Reduce(tt, z);
+        }
+
+        internal void Reduce(ulong[] tt, ulong[] z)
+        {
+            int partialBits = m_bits & 63;
+            int excessBits = 64 - partialBits;
+            ulong partialMask = ulong.MaxValue >> excessBits;
+
+            ulong c = Nat.ShiftUpBits64(Size, tt, Size, excessBits, tt[Size - 1], z, 0);
+            Debug.Assert(c == 0UL);
+
+            for (int i = 0; i < Size; ++i)
+            {
+                z[i] ^= tt[i];
+            }
+
+            z[Size - 1] &= partialMask;
+        }
+
+        internal int Size => m_size;
+
+        internal int SizeExt => m_sizeExt;
+
+        internal void Square(ulong[] x, ulong[] z)
+        {
+            ulong[] tt = CreateExt();
+            ImplSquare(x, tt);
+            Reduce(tt, z);
+        }
+
+        internal void SquareN(ulong[] x, int n, ulong[] z)
+        {
+            Debug.Assert(n > 0);
+
+            ulong[] tt = CreateExt();
+            ImplSquare(x, tt);
+            Reduce(tt, z);
+
+            while (--n > 0)
+            {
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+            }
+        }
+
+        private void ImplMultiplyAcc(ulong[] x, ulong[] y, ulong[] zz)
+        {
+            ulong[] u = new ulong[16];
+
+            // Schoolbook
+
+            //for (int i = 0; i < Size; ++i)
+            //{
+            //    ulong x_i = x[i];
+
+            //    for (int j = 0; j < Size; ++j)
+            //    {
+            //        ulong y_j = y[j];
+
+            //        ImplMulwAcc(u, x_i, y_j, zz, i + j);
+            //    }
+            //}
+
+            // Arbitrary-degree Karatsuba
+
+            for (int i = 0; i < Size; ++i)
+            {
+                ImplMulwAcc(u, x[i], y[i], zz, i << 1);
+            }
+
+            ulong v0 = zz[0], v1 = zz[1];
+            for (int i = 1; i < Size; ++i)
+            {
+                v0 ^= zz[i << 1]; zz[i] = v0 ^ v1; v1 ^= zz[(i << 1) + 1];
+            }
+
+            ulong w = v0 ^ v1;
+            for (int i = 0; i < Size; ++i)
+            {
+                zz[Size + i] = zz[i] ^ w;
+            }
+
+            int last = Size - 1;
+            for (int zPos = 1; zPos < (last * 2); ++zPos)
+            {
+                int hi = System.Math.Min(last, zPos);
+                int lo = zPos - hi;
+
+                while (lo < hi)
+                {
+                    ImplMulwAcc(u, x[lo] ^ x[hi], y[lo] ^ y[hi], zz, zPos);
+
+                    ++lo;
+                    --hi;
+                }
+            }
+        }
+
+        private static void ImplMulwAcc(ulong[] u, ulong x, ulong y, ulong[] z, int zOff)
+        {
+#if NETCOREAPP3_0_OR_GREATER
+            if (Pclmulqdq.IsSupported)
+            {
+                var X = Vector128.CreateScalar(x);
+                var Y = Vector128.CreateScalar(y);
+                var Z = Pclmulqdq.CarrylessMultiply(X, Y, 0x00);
+                z[zOff    ] ^= Z.GetElement(0);
+                z[zOff + 1] ^= Z.GetElement(1);
+                return;
+            }
+#endif
+
+            //u[0] = 0;
+            u[1] = y;
+            for (int i = 2; i < 16; i += 2)
+            {
+                u[i    ] = u[i >> 1] << 1;
+                u[i + 1] = u[i     ] ^  y;
+            }
+
+            uint j = (uint)x;
+            ulong g, h = 0, l = u[j & 15]
+                              ^ u[(j >> 4) & 15] << 4;
+            int k = 56;
+            do
+            {
+                j  = (uint)(x >> k);
+                g  = u[j & 15]
+                   ^ u[(j >> 4) & 15] << 4;
+                l ^= (g << k);
+                h ^= (g >> -k);
+            }
+            while ((k -= 8) > 0);
+
+            for (int p = 0; p < 7; ++p)
+            {
+                x = (x & 0xFEFEFEFEFEFEFEFEUL) >> 1;
+                h ^= x & (ulong)((long)(y << p) >> 63);
+            }
+
+            Debug.Assert(h >> 63 == 0);
+
+            z[zOff    ] ^= l;
+            z[zOff + 1] ^= h;
+        }
+
+        private void ImplSquare(ulong[] x, ulong[] zz)
+        {
+            Interleave.Expand64To128(x, 0, Size, zz, 0);
+        }
+    }
+}
diff --git a/crypto/src/pqc/crypto/bike/BikeUtilities.cs b/crypto/src/pqc/crypto/bike/BikeUtilities.cs
index 5facdaacf..09143aea0 100644
--- a/crypto/src/pqc/crypto/bike/BikeUtilities.cs
+++ b/crypto/src/pqc/crypto/bike/BikeUtilities.cs
@@ -1,6 +1,4 @@
-using System;
-
-using Org.BouncyCastle.Crypto.Utilities;
+using Org.BouncyCastle.Crypto.Utilities;
 using Org.BouncyCastle.Crypto;
 using Org.BouncyCastle.Utilities;
 
@@ -8,15 +6,12 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
 {
     internal class BikeUtilities
     {
-        internal static byte[] XorBytes(byte[] a, byte[] b, int size)
+        internal static void XorTo(byte[] x, byte[] z, int zLen)
         {
-            byte[] output = new byte[size];
-
-            for (int i = 0; i < size; i++)
+            for (int i = 0; i < zLen; ++i)
             {
-                output[i] = (byte)(a[i] ^ b[i]);
+                z[i] ^= x[i];
             }
-            return output;
         }
 
         internal static int GetHammingWeight(byte[] bytes)
@@ -82,29 +77,6 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             }
         }
 
-        internal static byte[] RemoveLast0Bits(byte[] output)
-        {
-            int lastIndexOf1 = 0;
-            for (int i = output.Length - 1; i >= 0; i--)
-            {
-                if (output[i] == 1)
-                {
-                    lastIndexOf1 = i;
-                    break;
-                }
-            }
-            byte[] res = new byte[lastIndexOf1 + 1];
-            Array.Copy(output, 0, res, 0, res.Length);
-            return res;
-        }
-
-        internal static byte[] Append0s(byte[] input, int length)
-        {
-            byte[] output = new byte[length];
-            Array.Copy(input, 0, output, 0, input.Length);
-            return output;
-        }
-
         internal static byte[] GenerateRandomByteArray(int mod, int size, int weight, IXof digest)
         {
             byte[] buf = new byte[4];