Add new package for working with finite fields and their extensions

8 files changed, 220 insertions, 0 deletions

diff --git a/core/src/main/java/org/bouncycastle/math/field/ExtensionField.java b/core/src/main/java/org/bouncycastle/math/field/ExtensionField.java
new file mode 100644
index 00000000..dfefba7e
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/math/field/ExtensionField.java
@@ -0,0 +1,8 @@
+package org.bouncycastle.math.field;
+
+public interface ExtensionField extends FiniteField
+{
+    FiniteField getSubfield();
+
+    int getDegree();
+}
diff --git a/core/src/main/java/org/bouncycastle/math/field/FiniteField.java b/core/src/main/java/org/bouncycastle/math/field/FiniteField.java
new file mode 100644
index 00000000..0a5baa09
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/math/field/FiniteField.java
@@ -0,0 +1,10 @@
+package org.bouncycastle.math.field;
+
+import java.math.BigInteger;
+
+public interface FiniteField
+{
+    BigInteger getCharacteristic();
+
+    int getDimension();
+}
diff --git a/core/src/main/java/org/bouncycastle/math/field/FiniteFields.java b/core/src/main/java/org/bouncycastle/math/field/FiniteFields.java
new file mode 100644
index 00000000..036ed7f2
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/math/field/FiniteFields.java
@@ -0,0 +1,38 @@
+package org.bouncycastle.math.field;
+
+import java.math.BigInteger;
+
+public abstract class FiniteFields
+{
+    static final FiniteField GF_2 = new PrimeField(BigInteger.valueOf(2));
+    static final FiniteField GF_3 = new PrimeField(BigInteger.valueOf(3));
+
+    public static PolynomialExtensionField getBinaryExtensionField(int[] exponents)
+    {
+        return new GenericPolynomialExtensionField(GF_2, new GF2Polynomial(exponents));
+    }
+
+    public static FiniteField getPrimeField(BigInteger characteristic)
+    {
+        characteristic = characteristic.abs();
+
+        int bitLength = characteristic.bitLength();
+        if (bitLength < 3)
+        {
+            if (bitLength < 2)
+            {
+                throw new IllegalArgumentException("'characteristic' must be >= 2");
+            }
+
+            switch (characteristic.intValue())
+            {
+            case 2:
+                return GF_2;
+            case 3:
+                return GF_3;
+            }
+        }
+
+        return new PrimeField(characteristic);
+    }
+}
diff --git a/core/src/main/java/org/bouncycastle/math/field/GF2Polynomial.java b/core/src/main/java/org/bouncycastle/math/field/GF2Polynomial.java
new file mode 100644
index 00000000..73be7685
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/math/field/GF2Polynomial.java
@@ -0,0 +1,42 @@
+package org.bouncycastle.math.field;
+
+import org.bouncycastle.util.Arrays;
+
+class GF2Polynomial implements Polynomial
+{
+    protected final int[] exponents;
+
+    GF2Polynomial(int[] exponents)
+    {
+        this.exponents = Arrays.clone(exponents);
+    }
+
+    public int getDegree()
+    {
+        return exponents[exponents.length - 1];
+    }
+
+    public int[] getExponentsPresent()
+    {
+        return Arrays.clone(exponents);
+    }
+
+    public boolean equals(Object obj)
+    {
+        if (this == obj)
+        {
+            return true;
+        }
+        if (!(obj instanceof GF2Polynomial))
+        {
+            return false;
+        }
+        GF2Polynomial other = (GF2Polynomial)obj;
+        return Arrays.areEqual(exponents, other.exponents);
+    }
+
+    public int hashCode()
+    {
+        return Arrays.hashCode(exponents);
+    }
+}
diff --git a/core/src/main/java/org/bouncycastle/math/field/GenericPolynomialExtensionField.java b/core/src/main/java/org/bouncycastle/math/field/GenericPolynomialExtensionField.java
new file mode 100644
index 00000000..d217a6ca
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/math/field/GenericPolynomialExtensionField.java
@@ -0,0 +1,62 @@
+package org.bouncycastle.math.field;
+
+import java.math.BigInteger;
+
+import org.bouncycastle.util.Integers;
+
+class GenericPolynomialExtensionField implements PolynomialExtensionField
+{
+    protected final FiniteField subfield;
+    protected final Polynomial minimalPolynomial;
+
+    GenericPolynomialExtensionField(FiniteField subfield, Polynomial polynomial)
+    {
+        this.subfield = subfield;
+        this.minimalPolynomial = polynomial;
+    }
+
+    public BigInteger getCharacteristic()
+    {
+        return subfield.getCharacteristic();
+    }
+
+    public int getDimension()
+    {
+        return subfield.getDimension() * minimalPolynomial.getDegree();
+    }
+
+    public final FiniteField getSubfield()
+    {
+        return subfield;
+    }
+
+    public int getDegree()
+    {
+        return minimalPolynomial.getDegree();
+    }
+
+    public Polynomial getMinimalPolynomial()
+    {
+        return minimalPolynomial;
+    }
+
+    public boolean equals(Object obj)
+    {
+        if (this == obj)
+        {
+            return true;
+        }
+        if (!(obj instanceof GenericPolynomialExtensionField))
+        {
+            return false;
+        }
+        GenericPolynomialExtensionField other = (GenericPolynomialExtensionField)obj;
+        return subfield.equals(other.subfield) && minimalPolynomial.equals(other.minimalPolynomial);
+    }
+
+    public int hashCode()
+    {
+        return subfield.hashCode()
+            ^ Integers.rotateLeft(minimalPolynomial.hashCode(), 16);
+    }
+}
diff --git a/core/src/main/java/org/bouncycastle/math/field/Polynomial.java b/core/src/main/java/org/bouncycastle/math/field/Polynomial.java
new file mode 100644
index 00000000..e5ccd61c
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/math/field/Polynomial.java
@@ -0,0 +1,12 @@
+package org.bouncycastle.math.field;
+
+public interface Polynomial
+{
+    int getDegree();
+
+//    BigInteger[] getCoefficients();
+
+    int[] getExponentsPresent();
+
+//    Term[] getNonZeroTerms();
+}
diff --git a/core/src/main/java/org/bouncycastle/math/field/PolynomialExtensionField.java b/core/src/main/java/org/bouncycastle/math/field/PolynomialExtensionField.java
new file mode 100644
index 00000000..aedcbee3
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/math/field/PolynomialExtensionField.java
@@ -0,0 +1,6 @@
+package org.bouncycastle.math.field;
+
+public interface PolynomialExtensionField extends ExtensionField
+{
+    Polynomial getMinimalPolynomial();
+}
diff --git a/core/src/main/java/org/bouncycastle/math/field/PrimeField.java b/core/src/main/java/org/bouncycastle/math/field/PrimeField.java
new file mode 100644
index 00000000..fd1e2532
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/math/field/PrimeField.java
@@ -0,0 +1,42 @@
+package org.bouncycastle.math.field;
+
+import java.math.BigInteger;
+
+class PrimeField implements FiniteField
+{
+    protected final BigInteger characteristic;
+
+    PrimeField(BigInteger characteristic)
+    {
+        this.characteristic = characteristic;
+    }
+
+    public BigInteger getCharacteristic()
+    {
+        return characteristic;
+    }
+
+    public int getDimension()
+    {
+        return 1;
+    }
+
+    public boolean equals(Object obj)
+    {
+        if (this == obj)
+        {
+            return true;
+        }
+        if (!(obj instanceof PrimeField))
+        {
+            return false;
+        }
+        PrimeField other = (PrimeField)obj;
+        return characteristic.equals(other.characteristic);
+    }
+
+    public int hashCode()
+    {
+        return characteristic.hashCode();
+    }
+}