diff options
Diffstat (limited to 'bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial')
22 files changed, 0 insertions, 3755 deletions
diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/BigDecimalPolynomial.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/BigDecimalPolynomial.java deleted file mode 100644 index 697f51a..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/BigDecimalPolynomial.java +++ /dev/null @@ -1,258 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial; - -import java.math.BigDecimal; - -/** - * A polynomial with {@link BigDecimal} coefficients. - * Some methods (like <code>add</code>) change the polynomial, others (like <code>mult</code>) do - * not but return the result as a new polynomial. - */ -public class BigDecimalPolynomial -{ - private static final BigDecimal ZERO = new BigDecimal("0"); - private static final BigDecimal ONE_HALF = new BigDecimal("0.5"); - - BigDecimal[] coeffs; - - /** - * Constructs a new polynomial with <code>N</code> coefficients initialized to 0. - * - * @param N the number of coefficients - */ - BigDecimalPolynomial(int N) - { - coeffs = new BigDecimal[N]; - for (int i = 0; i < N; i++) - { - coeffs[i] = ZERO; - } - } - - /** - * Constructs a new polynomial with a given set of coefficients. - * - * @param coeffs the coefficients - */ - BigDecimalPolynomial(BigDecimal[] coeffs) - { - this.coeffs = coeffs; - } - - /** - * Constructs a <code>BigDecimalPolynomial</code> from a <code>BigIntPolynomial</code>. The two polynomials are independent of each other. - * - * @param p the original polynomial - */ - public BigDecimalPolynomial(BigIntPolynomial p) - { - int N = p.coeffs.length; - coeffs = new BigDecimal[N]; - for (int i = 0; i < N; i++) - { - coeffs[i] = new BigDecimal(p.coeffs[i]); - } - } - - /** - * Divides all coefficients by 2. - */ - public void halve() - { - for (int i = 0; i < coeffs.length; i++) - { - coeffs[i] = coeffs[i].multiply(ONE_HALF); - } - } - - /** - * Multiplies the polynomial by another. Does not change this polynomial - * but returns the result as a new polynomial. - * - * @param poly2 the polynomial to multiply by - * @return a new polynomial - */ - public BigDecimalPolynomial mult(BigIntPolynomial poly2) - { - return mult(new BigDecimalPolynomial(poly2)); - } - - /** - * Multiplies the polynomial by another, taking the indices mod N. Does not - * change this polynomial but returns the result as a new polynomial. - * - * @param poly2 the polynomial to multiply by - * @return a new polynomial - */ - public BigDecimalPolynomial mult(BigDecimalPolynomial poly2) - { - int N = coeffs.length; - if (poly2.coeffs.length != N) - { - throw new IllegalArgumentException("Number of coefficients must be the same"); - } - - BigDecimalPolynomial c = multRecursive(poly2); - - if (c.coeffs.length > N) - { - for (int k = N; k < c.coeffs.length; k++) - { - c.coeffs[k - N] = c.coeffs[k - N].add(c.coeffs[k]); - } - c.coeffs = copyOf(c.coeffs, N); - } - return c; - } - - /** - * Karazuba multiplication - */ - private BigDecimalPolynomial multRecursive(BigDecimalPolynomial poly2) - { - BigDecimal[] a = coeffs; - BigDecimal[] b = poly2.coeffs; - - int n = poly2.coeffs.length; - if (n <= 1) - { - BigDecimal[] c = coeffs.clone(); - for (int i = 0; i < coeffs.length; i++) - { - c[i] = c[i].multiply(poly2.coeffs[0]); - } - return new BigDecimalPolynomial(c); - } - else - { - int n1 = n / 2; - - BigDecimalPolynomial a1 = new BigDecimalPolynomial(copyOf(a, n1)); - BigDecimalPolynomial a2 = new BigDecimalPolynomial(copyOfRange(a, n1, n)); - BigDecimalPolynomial b1 = new BigDecimalPolynomial(copyOf(b, n1)); - BigDecimalPolynomial b2 = new BigDecimalPolynomial(copyOfRange(b, n1, n)); - - BigDecimalPolynomial A = (BigDecimalPolynomial)a1.clone(); - A.add(a2); - BigDecimalPolynomial B = (BigDecimalPolynomial)b1.clone(); - B.add(b2); - - BigDecimalPolynomial c1 = a1.multRecursive(b1); - BigDecimalPolynomial c2 = a2.multRecursive(b2); - BigDecimalPolynomial c3 = A.multRecursive(B); - c3.sub(c1); - c3.sub(c2); - - BigDecimalPolynomial c = new BigDecimalPolynomial(2 * n - 1); - for (int i = 0; i < c1.coeffs.length; i++) - { - c.coeffs[i] = c1.coeffs[i]; - } - for (int i = 0; i < c3.coeffs.length; i++) - { - c.coeffs[n1 + i] = c.coeffs[n1 + i].add(c3.coeffs[i]); - } - for (int i = 0; i < c2.coeffs.length; i++) - { - c.coeffs[2 * n1 + i] = c.coeffs[2 * n1 + i].add(c2.coeffs[i]); - } - return c; - } - } - - /** - * Adds another polynomial which can have a different number of coefficients. - * - * @param b another polynomial - */ - public void add(BigDecimalPolynomial b) - { - if (b.coeffs.length > coeffs.length) - { - int N = coeffs.length; - coeffs = copyOf(coeffs, b.coeffs.length); - for (int i = N; i < coeffs.length; i++) - { - coeffs[i] = ZERO; - } - } - for (int i = 0; i < b.coeffs.length; i++) - { - coeffs[i] = coeffs[i].add(b.coeffs[i]); - } - } - - /** - * Subtracts another polynomial which can have a different number of coefficients. - * - * @param b - */ - void sub(BigDecimalPolynomial b) - { - if (b.coeffs.length > coeffs.length) - { - int N = coeffs.length; - coeffs = copyOf(coeffs, b.coeffs.length); - for (int i = N; i < coeffs.length; i++) - { - coeffs[i] = ZERO; - } - } - for (int i = 0; i < b.coeffs.length; i++) - { - coeffs[i] = coeffs[i].subtract(b.coeffs[i]); - } - } - - /** - * Rounds all coefficients to the nearest integer. - * - * @return a new polynomial with <code>BigInteger</code> coefficients - */ - public BigIntPolynomial round() - { - int N = coeffs.length; - BigIntPolynomial p = new BigIntPolynomial(N); - for (int i = 0; i < N; i++) - { - p.coeffs[i] = coeffs[i].setScale(0, BigDecimal.ROUND_HALF_EVEN).toBigInteger(); - } - return p; - } - - /** - * Makes a copy of the polynomial that is independent of the original. - */ - public Object clone() - { - return new BigDecimalPolynomial(coeffs.clone()); - } - - private BigDecimal[] copyOf(BigDecimal[] a, int length) - { - BigDecimal[] tmp = new BigDecimal[length]; - - System.arraycopy(a, 0, tmp, 0, a.length < length ? a.length : length); - - return tmp; - } - - private BigDecimal[] copyOfRange(BigDecimal[] a, int from, int to) - { - int newLength = to - from; - BigDecimal[] tmp = new BigDecimal[to - from]; - - System.arraycopy(a, from, tmp, 0, (a.length - from) < newLength ? (a.length - from) : newLength); - - return tmp; - } - - public BigDecimal[] getCoeffs() - { - BigDecimal[] tmp = new BigDecimal[coeffs.length]; - - System.arraycopy(coeffs, 0, tmp, 0, coeffs.length); - - return tmp; - } - -} diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/BigIntPolynomial.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/BigIntPolynomial.java deleted file mode 100644 index 3c79b2e..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/BigIntPolynomial.java +++ /dev/null @@ -1,394 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial; - -import java.math.BigDecimal; -import java.math.BigInteger; -import java.security.SecureRandom; -import java.util.ArrayList; -import java.util.Collections; -import java.util.List; - -import org.bouncycastle.util.Arrays; - -/** - * A polynomial with {@link BigInteger} coefficients.<br> - * Some methods (like <code>add</code>) change the polynomial, others (like <code>mult</code>) do - * not but return the result as a new polynomial. - */ -public class BigIntPolynomial -{ - private final static double LOG_10_2 = Math.log10(2); - - BigInteger[] coeffs; - - /** - * Constructs a new polynomial with <code>N</code> coefficients initialized to 0. - * - * @param N the number of coefficients - */ - BigIntPolynomial(int N) - { - coeffs = new BigInteger[N]; - for (int i = 0; i < N; i++) - { - coeffs[i] = Constants.BIGINT_ZERO; - } - } - - /** - * Constructs a new polynomial with a given set of coefficients. - * - * @param coeffs the coefficients - */ - BigIntPolynomial(BigInteger[] coeffs) - { - this.coeffs = coeffs; - } - - /** - * Constructs a <code>BigIntPolynomial</code> from a <code>IntegerPolynomial</code>. The two polynomials are - * independent of each other. - * - * @param p the original polynomial - */ - public BigIntPolynomial(IntegerPolynomial p) - { - coeffs = new BigInteger[p.coeffs.length]; - for (int i = 0; i < coeffs.length; i++) - { - coeffs[i] = BigInteger.valueOf(p.coeffs[i]); - } - } - - /** - * Generates a random polynomial with <code>numOnes</code> coefficients equal to 1, - * <code>numNegOnes</code> coefficients equal to -1, and the rest equal to 0. - * - * @param N number of coefficients - * @param numOnes number of 1's - * @param numNegOnes number of -1's - * @return - */ - static BigIntPolynomial generateRandomSmall(int N, int numOnes, int numNegOnes) - { - List coeffs = new ArrayList(); - for (int i = 0; i < numOnes; i++) - { - coeffs.add(Constants.BIGINT_ONE); - } - for (int i = 0; i < numNegOnes; i++) - { - coeffs.add(BigInteger.valueOf(-1)); - } - while (coeffs.size() < N) - { - coeffs.add(Constants.BIGINT_ZERO); - } - Collections.shuffle(coeffs, new SecureRandom()); - - BigIntPolynomial poly = new BigIntPolynomial(N); - for (int i = 0; i < coeffs.size(); i++) - { - poly.coeffs[i] = (BigInteger)coeffs.get(i); - } - return poly; - } - - /** - * Multiplies the polynomial by another, taking the indices mod N. Does not - * change this polynomial but returns the result as a new polynomial.<br> - * Both polynomials must have the same number of coefficients. - * - * @param poly2 the polynomial to multiply by - * @return a new polynomial - */ - public BigIntPolynomial mult(BigIntPolynomial poly2) - { - int N = coeffs.length; - if (poly2.coeffs.length != N) - { - throw new IllegalArgumentException("Number of coefficients must be the same"); - } - - BigIntPolynomial c = multRecursive(poly2); - - if (c.coeffs.length > N) - { - for (int k = N; k < c.coeffs.length; k++) - { - c.coeffs[k - N] = c.coeffs[k - N].add(c.coeffs[k]); - } - c.coeffs = Arrays.copyOf(c.coeffs, N); - } - return c; - } - - /** - * Karazuba multiplication - */ - private BigIntPolynomial multRecursive(BigIntPolynomial poly2) - { - BigInteger[] a = coeffs; - BigInteger[] b = poly2.coeffs; - - int n = poly2.coeffs.length; - if (n <= 1) - { - BigInteger[] c = Arrays.clone(coeffs); - for (int i = 0; i < coeffs.length; i++) - { - c[i] = c[i].multiply(poly2.coeffs[0]); - } - return new BigIntPolynomial(c); - } - else - { - int n1 = n / 2; - - BigIntPolynomial a1 = new BigIntPolynomial(Arrays.copyOf(a, n1)); - BigIntPolynomial a2 = new BigIntPolynomial(Arrays.copyOfRange(a, n1, n)); - BigIntPolynomial b1 = new BigIntPolynomial(Arrays.copyOf(b, n1)); - BigIntPolynomial b2 = new BigIntPolynomial(Arrays.copyOfRange(b, n1, n)); - - BigIntPolynomial A = (BigIntPolynomial)a1.clone(); - A.add(a2); - BigIntPolynomial B = (BigIntPolynomial)b1.clone(); - B.add(b2); - - BigIntPolynomial c1 = a1.multRecursive(b1); - BigIntPolynomial c2 = a2.multRecursive(b2); - BigIntPolynomial c3 = A.multRecursive(B); - c3.sub(c1); - c3.sub(c2); - - BigIntPolynomial c = new BigIntPolynomial(2 * n - 1); - for (int i = 0; i < c1.coeffs.length; i++) - { - c.coeffs[i] = c1.coeffs[i]; - } - for (int i = 0; i < c3.coeffs.length; i++) - { - c.coeffs[n1 + i] = c.coeffs[n1 + i].add(c3.coeffs[i]); - } - for (int i = 0; i < c2.coeffs.length; i++) - { - c.coeffs[2 * n1 + i] = c.coeffs[2 * n1 + i].add(c2.coeffs[i]); - } - return c; - } - } - - /** - * Adds another polynomial which can have a different number of coefficients, - * and takes the coefficient values mod <code>modulus</code>. - * - * @param b another polynomial - */ - void add(BigIntPolynomial b, BigInteger modulus) - { - add(b); - mod(modulus); - } - - /** - * Adds another polynomial which can have a different number of coefficients. - * - * @param b another polynomial - */ - public void add(BigIntPolynomial b) - { - if (b.coeffs.length > coeffs.length) - { - int N = coeffs.length; - coeffs = Arrays.copyOf(coeffs, b.coeffs.length); - for (int i = N; i < coeffs.length; i++) - { - coeffs[i] = Constants.BIGINT_ZERO; - } - } - for (int i = 0; i < b.coeffs.length; i++) - { - coeffs[i] = coeffs[i].add(b.coeffs[i]); - } - } - - /** - * Subtracts another polynomial which can have a different number of coefficients. - * - * @param b another polynomial - */ - public void sub(BigIntPolynomial b) - { - if (b.coeffs.length > coeffs.length) - { - int N = coeffs.length; - coeffs = Arrays.copyOf(coeffs, b.coeffs.length); - for (int i = N; i < coeffs.length; i++) - { - coeffs[i] = Constants.BIGINT_ZERO; - } - } - for (int i = 0; i < b.coeffs.length; i++) - { - coeffs[i] = coeffs[i].subtract(b.coeffs[i]); - } - } - - /** - * Multiplies each coefficient by a <code>BigInteger</code>. Does not return a new polynomial but modifies this polynomial. - * - * @param factor - */ - public void mult(BigInteger factor) - { - for (int i = 0; i < coeffs.length; i++) - { - coeffs[i] = coeffs[i].multiply(factor); - } - } - - /** - * Multiplies each coefficient by a <code>int</code>. Does not return a new polynomial but modifies this polynomial. - * - * @param factor - */ - void mult(int factor) - { - mult(BigInteger.valueOf(factor)); - } - - /** - * Divides each coefficient by a <code>BigInteger</code> and rounds the result to the nearest whole number.<br> - * Does not return a new polynomial but modifies this polynomial. - * - * @param divisor the number to divide by - */ - public void div(BigInteger divisor) - { - BigInteger d = divisor.add(Constants.BIGINT_ONE).divide(BigInteger.valueOf(2)); - for (int i = 0; i < coeffs.length; i++) - { - coeffs[i] = coeffs[i].compareTo(Constants.BIGINT_ZERO) > 0 ? coeffs[i].add(d) : coeffs[i].add(d.negate()); - coeffs[i] = coeffs[i].divide(divisor); - } - } - - /** - * Divides each coefficient by a <code>BigDecimal</code> and rounds the result to <code>decimalPlaces</code> places. - * - * @param divisor the number to divide by - * @param decimalPlaces the number of fractional digits to round the result to - * @return a new <code>BigDecimalPolynomial</code> - */ - public BigDecimalPolynomial div(BigDecimal divisor, int decimalPlaces) - { - BigInteger max = maxCoeffAbs(); - int coeffLength = (int)(max.bitLength() * LOG_10_2) + 1; - // factor = 1/divisor - BigDecimal factor = Constants.BIGDEC_ONE.divide(divisor, coeffLength + decimalPlaces + 1, BigDecimal.ROUND_HALF_EVEN); - - // multiply each coefficient by factor - BigDecimalPolynomial p = new BigDecimalPolynomial(coeffs.length); - for (int i = 0; i < coeffs.length; i++) - // multiply, then truncate after decimalPlaces so subsequent operations aren't slowed down - { - p.coeffs[i] = new BigDecimal(coeffs[i]).multiply(factor).setScale(decimalPlaces, BigDecimal.ROUND_HALF_EVEN); - } - - return p; - } - - /** - * Returns the base10 length of the largest coefficient. - * - * @return length of the longest coefficient - */ - public int getMaxCoeffLength() - { - return (int)(maxCoeffAbs().bitLength() * LOG_10_2) + 1; - } - - private BigInteger maxCoeffAbs() - { - BigInteger max = coeffs[0].abs(); - for (int i = 1; i < coeffs.length; i++) - { - BigInteger coeff = coeffs[i].abs(); - if (coeff.compareTo(max) > 0) - { - max = coeff; - } - } - return max; - } - - /** - * Takes each coefficient modulo a number. - * - * @param modulus - */ - public void mod(BigInteger modulus) - { - for (int i = 0; i < coeffs.length; i++) - { - coeffs[i] = coeffs[i].mod(modulus); - } - } - - /** - * Returns the sum of all coefficients, i.e. evaluates the polynomial at 0. - * - * @return the sum of all coefficients - */ - BigInteger sumCoeffs() - { - BigInteger sum = Constants.BIGINT_ZERO; - for (int i = 0; i < coeffs.length; i++) - { - sum = sum.add(coeffs[i]); - } - return sum; - } - - /** - * Makes a copy of the polynomial that is independent of the original. - */ - public Object clone() - { - return new BigIntPolynomial(coeffs.clone()); - } - - public int hashCode() - { - final int prime = 31; - int result = 1; - result = prime * result + Arrays.hashCode(coeffs); - return result; - } - - public boolean equals(Object obj) - { - if (this == obj) - { - return true; - } - if (obj == null) - { - return false; - } - if (getClass() != obj.getClass()) - { - return false; - } - BigIntPolynomial other = (BigIntPolynomial)obj; - if (!Arrays.areEqual(coeffs, other.coeffs)) - { - return false; - } - return true; - } - - public BigInteger[] getCoeffs() - { - return Arrays.clone(coeffs); - } -} diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/Constants.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/Constants.java deleted file mode 100644 index 2b41b19..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/Constants.java +++ /dev/null @@ -1,12 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial; - -import java.math.BigDecimal; -import java.math.BigInteger; - -public class Constants -{ - static final BigInteger BIGINT_ZERO = BigInteger.valueOf(0); - static final BigInteger BIGINT_ONE = BigInteger.valueOf(1); - - static final BigDecimal BIGDEC_ONE = BigDecimal.valueOf(1); -} diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/DenseTernaryPolynomial.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/DenseTernaryPolynomial.java deleted file mode 100644 index 85730da..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/DenseTernaryPolynomial.java +++ /dev/null @@ -1,142 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial; - -import java.security.SecureRandom; - -import org.bouncycastle.pqc.math.ntru.util.Util; -import org.bouncycastle.util.Arrays; - -/** - * A <code>TernaryPolynomial</code> with a "high" number of nonzero coefficients. - */ -public class DenseTernaryPolynomial - extends IntegerPolynomial - implements TernaryPolynomial -{ - - /** - * Constructs a new <code>DenseTernaryPolynomial</code> with <code>N</code> coefficients. - * - * @param N the number of coefficients - */ - DenseTernaryPolynomial(int N) - { - super(N); - checkTernarity(); - } - - /** - * Constructs a <code>DenseTernaryPolynomial</code> from a <code>IntegerPolynomial</code>. The two polynomials are - * independent of each other. - * - * @param intPoly the original polynomial - */ - public DenseTernaryPolynomial(IntegerPolynomial intPoly) - { - this(intPoly.coeffs); - } - - /** - * Constructs a new <code>DenseTernaryPolynomial</code> with a given set of coefficients. - * - * @param coeffs the coefficients - */ - public DenseTernaryPolynomial(int[] coeffs) - { - super(coeffs); - checkTernarity(); - } - - private void checkTernarity() - { - for (int i = 0; i != coeffs.length; i++) - { - int c = coeffs[i]; - if (c < -1 || c > 1) - { - throw new IllegalStateException("Illegal value: " + c + ", must be one of {-1, 0, 1}"); - } - } - } - - /** - * Generates a random polynomial with <code>numOnes</code> coefficients equal to 1, - * <code>numNegOnes</code> coefficients equal to -1, and the rest equal to 0. - * - * @param N number of coefficients - * @param numOnes number of 1's - * @param numNegOnes number of -1's - */ - public static DenseTernaryPolynomial generateRandom(int N, int numOnes, int numNegOnes, SecureRandom random) - { - int[] coeffs = Util.generateRandomTernary(N, numOnes, numNegOnes, random); - return new DenseTernaryPolynomial(coeffs); - } - - /** - * Generates a polynomial with coefficients randomly selected from <code>{-1, 0, 1}</code>. - * - * @param N number of coefficients - */ - public static DenseTernaryPolynomial generateRandom(int N, SecureRandom random) - { - DenseTernaryPolynomial poly = new DenseTernaryPolynomial(N); - for (int i = 0; i < N; i++) - { - poly.coeffs[i] = random.nextInt(3) - 1; - } - return poly; - } - - public IntegerPolynomial mult(IntegerPolynomial poly2, int modulus) - { - // even on 32-bit systems, LongPolynomial5 multiplies faster than IntegerPolynomial - if (modulus == 2048) - { - IntegerPolynomial poly2Pos = (IntegerPolynomial)poly2.clone(); - poly2Pos.modPositive(2048); - LongPolynomial5 poly5 = new LongPolynomial5(poly2Pos); - return poly5.mult(this).toIntegerPolynomial(); - } - else - { - return super.mult(poly2, modulus); - } - } - - public int[] getOnes() - { - int N = coeffs.length; - int[] ones = new int[N]; - int onesIdx = 0; - for (int i = 0; i < N; i++) - { - int c = coeffs[i]; - if (c == 1) - { - ones[onesIdx++] = i; - } - } - return Arrays.copyOf(ones, onesIdx); - } - - public int[] getNegOnes() - { - int N = coeffs.length; - int[] negOnes = new int[N]; - int negOnesIdx = 0; - for (int i = 0; i < N; i++) - { - int c = coeffs[i]; - if (c == -1) - { - negOnes[negOnesIdx++] = i; - } - } - return Arrays.copyOf(negOnes, negOnesIdx); - } - - public int size() - { - return coeffs.length; - } -} diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/IntegerPolynomial.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/IntegerPolynomial.java deleted file mode 100644 index c6bd7fb..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/IntegerPolynomial.java +++ /dev/null @@ -1,1358 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial; - -import java.io.IOException; -import java.io.InputStream; -import java.math.BigInteger; -import java.util.ArrayList; -import java.util.Iterator; -import java.util.LinkedList; -import java.util.List; -import java.util.concurrent.Callable; -import java.util.concurrent.ExecutorService; -import java.util.concurrent.Executors; -import java.util.concurrent.Future; -import java.util.concurrent.LinkedBlockingQueue; - -import org.bouncycastle.pqc.math.ntru.euclid.BigIntEuclidean; -import org.bouncycastle.pqc.math.ntru.util.ArrayEncoder; -import org.bouncycastle.pqc.math.ntru.util.Util; -import org.bouncycastle.util.Arrays; - -/** - * A polynomial with <code>int</code> coefficients.<br> - * Some methods (like <code>add</code>) change the polynomial, others (like <code>mult</code>) do - * not but return the result as a new polynomial. - */ -public class IntegerPolynomial - implements Polynomial -{ - private static final int NUM_EQUAL_RESULTANTS = 3; - /** - * Prime numbers > 4500 for resultant computation. Starting them below ~4400 causes incorrect results occasionally. - * Fortunately, 4500 is about the optimum number for performance.<br/> - * This array contains enough prime numbers so primes never have to be computed on-line for any standard {@link org.bouncycastle.pqc.crypto.ntru.NTRUSigningParameters}. - */ - private static final int[] PRIMES = new int[]{ - 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, - 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, - 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, - 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, - 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, - 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, - 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, - 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, - 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, - 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, - 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, - 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, - 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, - 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, - 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, - 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, - 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, - 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, - 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, - 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, - 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, - 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, - 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, - 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, - 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, - 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, - 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, - 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, - 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, - 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, - 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, - 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, - 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, - 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, - 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, - 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, - 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, - 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, - 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, - 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, - 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, - 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, - 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, - 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, - 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, - 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, - 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, - 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, - 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, - 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, - 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, - 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, - 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, - 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, - 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, - 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, - 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, - 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, - 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, - 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, - 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, - 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973}; - private static final List BIGINT_PRIMES; - - static - { - BIGINT_PRIMES = new ArrayList(); - for (int i = 0; i != PRIMES.length; i++) - { - BIGINT_PRIMES.add(BigInteger.valueOf(PRIMES[i])); - } - } - - public int[] coeffs; - - /** - * Constructs a new polynomial with <code>N</code> coefficients initialized to 0. - * - * @param N the number of coefficients - */ - public IntegerPolynomial(int N) - { - coeffs = new int[N]; - } - - /** - * Constructs a new polynomial with a given set of coefficients. - * - * @param coeffs the coefficients - */ - public IntegerPolynomial(int[] coeffs) - { - this.coeffs = coeffs; - } - - /** - * Constructs a <code>IntegerPolynomial</code> from a <code>BigIntPolynomial</code>. The two polynomials are independent of each other. - * - * @param p the original polynomial - */ - public IntegerPolynomial(BigIntPolynomial p) - { - coeffs = new int[p.coeffs.length]; - for (int i = 0; i < p.coeffs.length; i++) - { - coeffs[i] = p.coeffs[i].intValue(); - } - } - - /** - * Decodes a byte array to a polynomial with <code>N</code> ternary coefficients<br> - * Ignores any excess bytes. - * - * @param data an encoded ternary polynomial - * @param N number of coefficients - * @return the decoded polynomial - */ - public static IntegerPolynomial fromBinary3Sves(byte[] data, int N) - { - return new IntegerPolynomial(ArrayEncoder.decodeMod3Sves(data, N)); - } - - /** - * Converts a byte array produced by {@link #toBinary3Tight()} to a polynomial. - * - * @param b a byte array - * @param N number of coefficients - * @return the decoded polynomial - */ - public static IntegerPolynomial fromBinary3Tight(byte[] b, int N) - { - return new IntegerPolynomial(ArrayEncoder.decodeMod3Tight(b, N)); - } - - /** - * Reads data produced by {@link #toBinary3Tight()} from an input stream and converts it to a polynomial. - * - * @param is an input stream - * @param N number of coefficients - * @return the decoded polynomial - */ - public static IntegerPolynomial fromBinary3Tight(InputStream is, int N) - throws IOException - { - return new IntegerPolynomial(ArrayEncoder.decodeMod3Tight(is, N)); - } - - /** - * Returns a polynomial with N coefficients between <code>0</code> and <code>q-1</code>.<br> - * <code>q</code> must be a power of 2.<br> - * Ignores any excess bytes. - * - * @param data an encoded ternary polynomial - * @param N number of coefficients - * @param q - * @return the decoded polynomial - */ - public static IntegerPolynomial fromBinary(byte[] data, int N, int q) - { - return new IntegerPolynomial(ArrayEncoder.decodeModQ(data, N, q)); - } - - /** - * Returns a polynomial with N coefficients between <code>0</code> and <code>q-1</code>.<br> - * <code>q</code> must be a power of 2.<br> - * Ignores any excess bytes. - * - * @param is an encoded ternary polynomial - * @param N number of coefficients - * @param q - * @return the decoded polynomial - */ - public static IntegerPolynomial fromBinary(InputStream is, int N, int q) - throws IOException - { - return new IntegerPolynomial(ArrayEncoder.decodeModQ(is, N, q)); - } - - /** - * Encodes a polynomial with ternary coefficients to binary. - * <code>coeffs[2*i]</code> and <code>coeffs[2*i+1]</code> must not both equal -1 for any integer <code>i</code>, - * so this method is only safe to use with polynomials produced by <code>fromBinary3Sves()</code>. - * - * @return the encoded polynomial - */ - public byte[] toBinary3Sves() - { - return ArrayEncoder.encodeMod3Sves(coeffs); - } - - /** - * Converts a polynomial with ternary coefficients to binary. - * - * @return the encoded polynomial - */ - public byte[] toBinary3Tight() - { - BigInteger sum = Constants.BIGINT_ZERO; - for (int i = coeffs.length - 1; i >= 0; i--) - { - sum = sum.multiply(BigInteger.valueOf(3)); - sum = sum.add(BigInteger.valueOf(coeffs[i] + 1)); - } - - int size = (BigInteger.valueOf(3).pow(coeffs.length).bitLength() + 7) / 8; - byte[] arr = sum.toByteArray(); - - if (arr.length < size) - { - // pad with leading zeros so arr.length==size - byte[] arr2 = new byte[size]; - System.arraycopy(arr, 0, arr2, size - arr.length, arr.length); - return arr2; - } - - if (arr.length > size) - // drop sign bit - { - arr = Arrays.copyOfRange(arr, 1, arr.length); - } - return arr; - } - - /** - * Encodes a polynomial whose coefficients are between 0 and q, to binary. q must be a power of 2. - * - * @param q - * @return the encoded polynomial - */ - public byte[] toBinary(int q) - { - return ArrayEncoder.encodeModQ(coeffs, q); - } - - /** - * Multiplies the polynomial with another, taking the values mod modulus and the indices mod N - */ - public IntegerPolynomial mult(IntegerPolynomial poly2, int modulus) - { - IntegerPolynomial c = mult(poly2); - c.mod(modulus); - return c; - } - - /** - * Multiplies the polynomial with another, taking the indices mod N - */ - public IntegerPolynomial mult(IntegerPolynomial poly2) - { - int N = coeffs.length; - if (poly2.coeffs.length != N) - { - throw new IllegalArgumentException("Number of coefficients must be the same"); - } - - IntegerPolynomial c = multRecursive(poly2); - - if (c.coeffs.length > N) - { - for (int k = N; k < c.coeffs.length; k++) - { - c.coeffs[k - N] += c.coeffs[k]; - } - c.coeffs = Arrays.copyOf(c.coeffs, N); - } - return c; - } - - public BigIntPolynomial mult(BigIntPolynomial poly2) - { - return new BigIntPolynomial(this).mult(poly2); - } - - /** - * Karazuba multiplication - */ - private IntegerPolynomial multRecursive(IntegerPolynomial poly2) - { - int[] a = coeffs; - int[] b = poly2.coeffs; - - int n = poly2.coeffs.length; - if (n <= 32) - { - int cn = 2 * n - 1; - IntegerPolynomial c = new IntegerPolynomial(new int[cn]); - for (int k = 0; k < cn; k++) - { - for (int i = Math.max(0, k - n + 1); i <= Math.min(k, n - 1); i++) - { - c.coeffs[k] += b[i] * a[k - i]; - } - } - return c; - } - else - { - int n1 = n / 2; - - IntegerPolynomial a1 = new IntegerPolynomial(Arrays.copyOf(a, n1)); - IntegerPolynomial a2 = new IntegerPolynomial(Arrays.copyOfRange(a, n1, n)); - IntegerPolynomial b1 = new IntegerPolynomial(Arrays.copyOf(b, n1)); - IntegerPolynomial b2 = new IntegerPolynomial(Arrays.copyOfRange(b, n1, n)); - - IntegerPolynomial A = (IntegerPolynomial)a1.clone(); - A.add(a2); - IntegerPolynomial B = (IntegerPolynomial)b1.clone(); - B.add(b2); - - IntegerPolynomial c1 = a1.multRecursive(b1); - IntegerPolynomial c2 = a2.multRecursive(b2); - IntegerPolynomial c3 = A.multRecursive(B); - c3.sub(c1); - c3.sub(c2); - - IntegerPolynomial c = new IntegerPolynomial(2 * n - 1); - for (int i = 0; i < c1.coeffs.length; i++) - { - c.coeffs[i] = c1.coeffs[i]; - } - for (int i = 0; i < c3.coeffs.length; i++) - { - c.coeffs[n1 + i] += c3.coeffs[i]; - } - for (int i = 0; i < c2.coeffs.length; i++) - { - c.coeffs[2 * n1 + i] += c2.coeffs[i]; - } - return c; - } - } - - /** - * Computes the inverse mod <code>q; q</code> must be a power of 2.<br> - * Returns <code>null</code> if the polynomial is not invertible. - * - * @param q the modulus - * @return a new polynomial - */ - public IntegerPolynomial invertFq(int q) - { - int N = coeffs.length; - int k = 0; - IntegerPolynomial b = new IntegerPolynomial(N + 1); - b.coeffs[0] = 1; - IntegerPolynomial c = new IntegerPolynomial(N + 1); - IntegerPolynomial f = new IntegerPolynomial(N + 1); - f.coeffs = Arrays.copyOf(coeffs, N + 1); - f.modPositive(2); - // set g(x) = x^N − 1 - IntegerPolynomial g = new IntegerPolynomial(N + 1); - g.coeffs[0] = 1; - g.coeffs[N] = 1; - while (true) - { - while (f.coeffs[0] == 0) - { - for (int i = 1; i <= N; i++) - { - f.coeffs[i - 1] = f.coeffs[i]; // f(x) = f(x) / x - c.coeffs[N + 1 - i] = c.coeffs[N - i]; // c(x) = c(x) * x - } - f.coeffs[N] = 0; - c.coeffs[0] = 0; - k++; - if (f.equalsZero()) - { - return null; // not invertible - } - } - if (f.equalsOne()) - { - break; - } - if (f.degree() < g.degree()) - { - // exchange f and g - IntegerPolynomial temp = f; - f = g; - g = temp; - // exchange b and c - temp = b; - b = c; - c = temp; - } - f.add(g, 2); - b.add(c, 2); - } - - if (b.coeffs[N] != 0) - { - return null; - } - // Fq(x) = x^(N-k) * b(x) - IntegerPolynomial Fq = new IntegerPolynomial(N); - int j = 0; - k %= N; - for (int i = N - 1; i >= 0; i--) - { - j = i - k; - if (j < 0) - { - j += N; - } - Fq.coeffs[j] = b.coeffs[i]; - } - - return mod2ToModq(Fq, q); - } - - /** - * Computes the inverse mod q from the inverse mod 2 - * - * @param Fq - * @param q - * @return The inverse of this polynomial mod q - */ - private IntegerPolynomial mod2ToModq(IntegerPolynomial Fq, int q) - { - if (Util.is64BitJVM() && q == 2048) - { - LongPolynomial2 thisLong = new LongPolynomial2(this); - LongPolynomial2 FqLong = new LongPolynomial2(Fq); - int v = 2; - while (v < q) - { - v *= 2; - LongPolynomial2 temp = (LongPolynomial2)FqLong.clone(); - temp.mult2And(v - 1); - FqLong = thisLong.mult(FqLong).mult(FqLong); - temp.subAnd(FqLong, v - 1); - FqLong = temp; - } - return FqLong.toIntegerPolynomial(); - } - else - { - int v = 2; - while (v < q) - { - v *= 2; - IntegerPolynomial temp = new IntegerPolynomial(Arrays.copyOf(Fq.coeffs, Fq.coeffs.length)); - temp.mult2(v); - Fq = mult(Fq, v).mult(Fq, v); - temp.sub(Fq, v); - Fq = temp; - } - return Fq; - } - } - - /** - * Computes the inverse mod 3. - * Returns <code>null</code> if the polynomial is not invertible. - * - * @return a new polynomial - */ - public IntegerPolynomial invertF3() - { - int N = coeffs.length; - int k = 0; - IntegerPolynomial b = new IntegerPolynomial(N + 1); - b.coeffs[0] = 1; - IntegerPolynomial c = new IntegerPolynomial(N + 1); - IntegerPolynomial f = new IntegerPolynomial(N + 1); - f.coeffs = Arrays.copyOf(coeffs, N + 1); - f.modPositive(3); - // set g(x) = x^N − 1 - IntegerPolynomial g = new IntegerPolynomial(N + 1); - g.coeffs[0] = -1; - g.coeffs[N] = 1; - while (true) - { - while (f.coeffs[0] == 0) - { - for (int i = 1; i <= N; i++) - { - f.coeffs[i - 1] = f.coeffs[i]; // f(x) = f(x) / x - c.coeffs[N + 1 - i] = c.coeffs[N - i]; // c(x) = c(x) * x - } - f.coeffs[N] = 0; - c.coeffs[0] = 0; - k++; - if (f.equalsZero()) - { - return null; // not invertible - } - } - if (f.equalsAbsOne()) - { - break; - } - if (f.degree() < g.degree()) - { - // exchange f and g - IntegerPolynomial temp = f; - f = g; - g = temp; - // exchange b and c - temp = b; - b = c; - c = temp; - } - if (f.coeffs[0] == g.coeffs[0]) - { - f.sub(g, 3); - b.sub(c, 3); - } - else - { - f.add(g, 3); - b.add(c, 3); - } - } - - if (b.coeffs[N] != 0) - { - return null; - } - // Fp(x) = [+-] x^(N-k) * b(x) - IntegerPolynomial Fp = new IntegerPolynomial(N); - int j = 0; - k %= N; - for (int i = N - 1; i >= 0; i--) - { - j = i - k; - if (j < 0) - { - j += N; - } - Fp.coeffs[j] = f.coeffs[0] * b.coeffs[i]; - } - - Fp.ensurePositive(3); - return Fp; - } - - /** - * Resultant of this polynomial with <code>x^n-1</code> using a probabilistic algorithm. - * <p> - * Unlike EESS, this implementation does not compute all resultants modulo primes - * such that their product exceeds the maximum possible resultant, but rather stops - * when <code>NUM_EQUAL_RESULTANTS</code> consecutive modular resultants are equal.<br> - * This means the return value may be incorrect. Experiments show this happens in - * about 1 out of 100 cases when <code>N=439</code> and <code>NUM_EQUAL_RESULTANTS=2</code>, - * so the likelyhood of leaving the loop too early is <code>(1/100)^(NUM_EQUAL_RESULTANTS-1)</code>. - * <p> - * Because of the above, callers must verify the output and try a different polynomial if necessary. - * - * @return <code>(rho, res)</code> satisfying <code>res = rho*this + t*(x^n-1)</code> for some integer <code>t</code>. - */ - public Resultant resultant() - { - int N = coeffs.length; - - // Compute resultants modulo prime numbers. Continue until NUM_EQUAL_RESULTANTS consecutive modular resultants are equal. - LinkedList<ModularResultant> modResultants = new LinkedList<ModularResultant>(); - BigInteger prime = null; - BigInteger pProd = Constants.BIGINT_ONE; - BigInteger res = Constants.BIGINT_ONE; - int numEqual = 1; // number of consecutive modular resultants equal to each other - Iterator<BigInteger> primes = BIGINT_PRIMES.iterator(); - while (true) - { - prime = primes.hasNext() ? primes.next() : prime.nextProbablePrime(); - ModularResultant crr = resultant(prime.intValue()); - modResultants.add(crr); - - BigInteger temp = pProd.multiply(prime); - BigIntEuclidean er = BigIntEuclidean.calculate(prime, pProd); - BigInteger resPrev = res; - res = res.multiply(er.x.multiply(prime)); - BigInteger res2 = crr.res.multiply(er.y.multiply(pProd)); - res = res.add(res2).mod(temp); - pProd = temp; - - BigInteger pProd2 = pProd.divide(BigInteger.valueOf(2)); - BigInteger pProd2n = pProd2.negate(); - if (res.compareTo(pProd2) > 0) - { - res = res.subtract(pProd); - } - else if (res.compareTo(pProd2n) < 0) - { - res = res.add(pProd); - } - - if (res.equals(resPrev)) - { - numEqual++; - if (numEqual >= NUM_EQUAL_RESULTANTS) - { - break; - } - } - else - { - numEqual = 1; - } - } - - // Combine modular rho's to obtain the final rho. - // For efficiency, first combine all pairs of small resultants to bigger resultants, - // then combine pairs of those, etc. until only one is left. - while (modResultants.size() > 1) - { - ModularResultant modRes1 = modResultants.removeFirst(); - ModularResultant modRes2 = modResultants.removeFirst(); - ModularResultant modRes3 = ModularResultant.combineRho(modRes1, modRes2); - modResultants.addLast(modRes3); - } - BigIntPolynomial rhoP = modResultants.getFirst().rho; - - BigInteger pProd2 = pProd.divide(BigInteger.valueOf(2)); - BigInteger pProd2n = pProd2.negate(); - if (res.compareTo(pProd2) > 0) - { - res = res.subtract(pProd); - } - if (res.compareTo(pProd2n) < 0) - { - res = res.add(pProd); - } - - for (int i = 0; i < N; i++) - { - BigInteger c = rhoP.coeffs[i]; - if (c.compareTo(pProd2) > 0) - { - rhoP.coeffs[i] = c.subtract(pProd); - } - if (c.compareTo(pProd2n) < 0) - { - rhoP.coeffs[i] = c.add(pProd); - } - } - - return new Resultant(rhoP, res); - } - - /** - * Multithreaded version of {@link #resultant()}. - * - * @return <code>(rho, res)</code> satisfying <code>res = rho*this + t*(x^n-1)</code> for some integer <code>t</code>. - */ - public Resultant resultantMultiThread() - { - int N = coeffs.length; - - // upper bound for resultant(f, g) = ||f, 2||^deg(g) * ||g, 2||^deg(f) = squaresum(f)^(N/2) * 2^(deg(f)/2) because g(x)=x^N-1 - // see http://jondalon.mathematik.uni-osnabrueck.de/staff/phpages/brunsw/CompAlg.pdf chapter 3 - BigInteger max = squareSum().pow((N + 1) / 2); - max = max.multiply(BigInteger.valueOf(2).pow((degree() + 1) / 2)); - BigInteger max2 = max.multiply(BigInteger.valueOf(2)); - - // compute resultants modulo prime numbers - BigInteger prime = BigInteger.valueOf(10000); - BigInteger pProd = Constants.BIGINT_ONE; - LinkedBlockingQueue<Future<ModularResultant>> resultantTasks = new LinkedBlockingQueue<Future<ModularResultant>>(); - Iterator<BigInteger> primes = BIGINT_PRIMES.iterator(); - ExecutorService executor = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors()); - while (pProd.compareTo(max2) < 0) - { - if (primes.hasNext()) - { - prime = primes.next(); - } - else - { - prime = prime.nextProbablePrime(); - } - Future<ModularResultant> task = executor.submit(new ModResultantTask(prime.intValue())); - resultantTasks.add(task); - pProd = pProd.multiply(prime); - } - - // Combine modular resultants to obtain the resultant. - // For efficiency, first combine all pairs of small resultants to bigger resultants, - // then combine pairs of those, etc. until only one is left. - ModularResultant overallResultant = null; - while (!resultantTasks.isEmpty()) - { - try - { - Future<ModularResultant> modRes1 = resultantTasks.take(); - Future<ModularResultant> modRes2 = resultantTasks.poll(); - if (modRes2 == null) - { - // modRes1 is the only one left - overallResultant = modRes1.get(); - break; - } - Future<ModularResultant> newTask = executor.submit(new CombineTask(modRes1.get(), modRes2.get())); - resultantTasks.add(newTask); - } - catch (Exception e) - { - throw new IllegalStateException(e.toString()); - } - } - executor.shutdown(); - BigInteger res = overallResultant.res; - BigIntPolynomial rhoP = overallResultant.rho; - - BigInteger pProd2 = pProd.divide(BigInteger.valueOf(2)); - BigInteger pProd2n = pProd2.negate(); - - if (res.compareTo(pProd2) > 0) - { - res = res.subtract(pProd); - } - if (res.compareTo(pProd2n) < 0) - { - res = res.add(pProd); - } - - for (int i = 0; i < N; i++) - { - BigInteger c = rhoP.coeffs[i]; - if (c.compareTo(pProd2) > 0) - { - rhoP.coeffs[i] = c.subtract(pProd); - } - if (c.compareTo(pProd2n) < 0) - { - rhoP.coeffs[i] = c.add(pProd); - } - } - - return new Resultant(rhoP, res); - } - - /** - * Resultant of this polynomial with <code>x^n-1 mod p</code>. - * - * @return <code>(rho, res)</code> satisfying <code>res = rho*this + t*(x^n-1) mod p</code> for some integer <code>t</code>. - */ - public ModularResultant resultant(int p) - { - // Add a coefficient as the following operations involve polynomials of degree deg(f)+1 - int[] fcoeffs = Arrays.copyOf(coeffs, coeffs.length + 1); - IntegerPolynomial f = new IntegerPolynomial(fcoeffs); - int N = fcoeffs.length; - - IntegerPolynomial a = new IntegerPolynomial(N); - a.coeffs[0] = -1; - a.coeffs[N - 1] = 1; - IntegerPolynomial b = new IntegerPolynomial(f.coeffs); - IntegerPolynomial v1 = new IntegerPolynomial(N); - IntegerPolynomial v2 = new IntegerPolynomial(N); - v2.coeffs[0] = 1; - int da = N - 1; - int db = b.degree(); - int ta = da; - int c = 0; - int r = 1; - while (db > 0) - { - c = Util.invert(b.coeffs[db], p); - c = (c * a.coeffs[da]) % p; - a.multShiftSub(b, c, da - db, p); - v1.multShiftSub(v2, c, da - db, p); - - da = a.degree(); - if (da < db) - { - r *= Util.pow(b.coeffs[db], ta - da, p); - r %= p; - if (ta % 2 == 1 && db % 2 == 1) - { - r = (-r) % p; - } - IntegerPolynomial temp = a; - a = b; - b = temp; - int tempdeg = da; - da = db; - temp = v1; - v1 = v2; - v2 = temp; - ta = db; - db = tempdeg; - } - } - r *= Util.pow(b.coeffs[0], da, p); - r %= p; - c = Util.invert(b.coeffs[0], p); - v2.mult(c); - v2.mod(p); - v2.mult(r); - v2.mod(p); - - // drop the highest coefficient so #coeffs matches the original input - v2.coeffs = Arrays.copyOf(v2.coeffs, v2.coeffs.length - 1); - return new ModularResultant(new BigIntPolynomial(v2), BigInteger.valueOf(r), BigInteger.valueOf(p)); - } - - /** - * Computes <code>this-b*c*(x^k) mod p</code> and stores the result in this polynomial.<br/> - * See steps 4a,4b in EESS algorithm 2.2.7.1. - * - * @param b - * @param c - * @param k - * @param p - */ - private void multShiftSub(IntegerPolynomial b, int c, int k, int p) - { - int N = coeffs.length; - for (int i = k; i < N; i++) - { - coeffs[i] = (coeffs[i] - b.coeffs[i - k] * c) % p; - } - } - - /** - * Adds the squares of all coefficients. - * - * @return the sum of squares - */ - private BigInteger squareSum() - { - BigInteger sum = Constants.BIGINT_ZERO; - for (int i = 0; i < coeffs.length; i++) - { - sum = sum.add(BigInteger.valueOf(coeffs[i] * coeffs[i])); - } - return sum; - } - - /** - * Returns the degree of the polynomial - * - * @return the degree - */ - int degree() - { - int degree = coeffs.length - 1; - while (degree > 0 && coeffs[degree] == 0) - { - degree--; - } - return degree; - } - - /** - * Adds another polynomial which can have a different number of coefficients, - * and takes the coefficient values mod <code>modulus</code>. - * - * @param b another polynomial - */ - public void add(IntegerPolynomial b, int modulus) - { - add(b); - mod(modulus); - } - - /** - * Adds another polynomial which can have a different number of coefficients. - * - * @param b another polynomial - */ - public void add(IntegerPolynomial b) - { - if (b.coeffs.length > coeffs.length) - { - coeffs = Arrays.copyOf(coeffs, b.coeffs.length); - } - for (int i = 0; i < b.coeffs.length; i++) - { - coeffs[i] += b.coeffs[i]; - } - } - - /** - * Subtracts another polynomial which can have a different number of coefficients, - * and takes the coefficient values mod <code>modulus</code>. - * - * @param b another polynomial - */ - public void sub(IntegerPolynomial b, int modulus) - { - sub(b); - mod(modulus); - } - - /** - * Subtracts another polynomial which can have a different number of coefficients. - * - * @param b another polynomial - */ - public void sub(IntegerPolynomial b) - { - if (b.coeffs.length > coeffs.length) - { - coeffs = Arrays.copyOf(coeffs, b.coeffs.length); - } - for (int i = 0; i < b.coeffs.length; i++) - { - coeffs[i] -= b.coeffs[i]; - } - } - - /** - * Subtracts a <code>int</code> from each coefficient. Does not return a new polynomial but modifies this polynomial. - * - * @param b - */ - void sub(int b) - { - for (int i = 0; i < coeffs.length; i++) - { - coeffs[i] -= b; - } - } - - /** - * Multiplies each coefficient by a <code>int</code>. Does not return a new polynomial but modifies this polynomial. - * - * @param factor - */ - public void mult(int factor) - { - for (int i = 0; i < coeffs.length; i++) - { - coeffs[i] *= factor; - } - } - - /** - * Multiplies each coefficient by a 2 and applies a modulus. Does not return a new polynomial but modifies this polynomial. - * - * @param modulus a modulus - */ - private void mult2(int modulus) - { - for (int i = 0; i < coeffs.length; i++) - { - coeffs[i] *= 2; - coeffs[i] %= modulus; - } - } - - /** - * Multiplies each coefficient by a 2 and applies a modulus. Does not return a new polynomial but modifies this polynomial. - * - * @param modulus a modulus - */ - public void mult3(int modulus) - { - for (int i = 0; i < coeffs.length; i++) - { - coeffs[i] *= 3; - coeffs[i] %= modulus; - } - } - - /** - * Divides each coefficient by <code>k</code> and rounds to the nearest integer. Does not return a new polynomial but modifies this polynomial. - * - * @param k the divisor - */ - public void div(int k) - { - int k2 = (k + 1) / 2; - for (int i = 0; i < coeffs.length; i++) - { - coeffs[i] += coeffs[i] > 0 ? k2 : -k2; - coeffs[i] /= k; - } - } - - /** - * Takes each coefficient modulo 3 such that all coefficients are ternary. - */ - public void mod3() - { - for (int i = 0; i < coeffs.length; i++) - { - coeffs[i] %= 3; - if (coeffs[i] > 1) - { - coeffs[i] -= 3; - } - if (coeffs[i] < -1) - { - coeffs[i] += 3; - } - } - } - - /** - * Ensures all coefficients are between 0 and <code>modulus-1</code> - * - * @param modulus a modulus - */ - public void modPositive(int modulus) - { - mod(modulus); - ensurePositive(modulus); - } - - /** - * Reduces all coefficients to the interval [-modulus/2, modulus/2) - */ - void modCenter(int modulus) - { - mod(modulus); - for (int j = 0; j < coeffs.length; j++) - { - while (coeffs[j] < modulus / 2) - { - coeffs[j] += modulus; - } - while (coeffs[j] >= modulus / 2) - { - coeffs[j] -= modulus; - } - } - } - - /** - * Takes each coefficient modulo <code>modulus</code>. - */ - public void mod(int modulus) - { - for (int i = 0; i < coeffs.length; i++) - { - coeffs[i] %= modulus; - } - } - - /** - * Adds <code>modulus</code> until all coefficients are above 0. - * - * @param modulus a modulus - */ - public void ensurePositive(int modulus) - { - for (int i = 0; i < coeffs.length; i++) - { - while (coeffs[i] < 0) - { - coeffs[i] += modulus; - } - } - } - - /** - * Computes the centered euclidean norm of the polynomial. - * - * @param q a modulus - * @return the centered norm - */ - public long centeredNormSq(int q) - { - int N = coeffs.length; - IntegerPolynomial p = (IntegerPolynomial)clone(); - p.shiftGap(q); - - long sum = 0; - long sqSum = 0; - for (int i = 0; i != p.coeffs.length; i++) - { - int c = p.coeffs[i]; - sum += c; - sqSum += c * c; - } - - long centeredNormSq = sqSum - sum * sum / N; - return centeredNormSq; - } - - /** - * Shifts all coefficients so the largest gap is centered around <code>-q/2</code>. - * - * @param q a modulus - */ - void shiftGap(int q) - { - modCenter(q); - - int[] sorted = Arrays.clone(coeffs); - - sort(sorted); - - int maxrange = 0; - int maxrangeStart = 0; - for (int i = 0; i < sorted.length - 1; i++) - { - int range = sorted[i + 1] - sorted[i]; - if (range > maxrange) - { - maxrange = range; - maxrangeStart = sorted[i]; - } - } - - int pmin = sorted[0]; - int pmax = sorted[sorted.length - 1]; - - int j = q - pmax + pmin; - int shift; - if (j > maxrange) - { - shift = (pmax + pmin) / 2; - } - else - { - shift = maxrangeStart + maxrange / 2 + q / 2; - } - - sub(shift); - } - - private void sort(int[] ints) - { - boolean swap = true; - - while (swap) - { - swap = false; - for (int i = 0; i != ints.length - 1; i++) - { - if (ints[i] > ints[i+1]) - { - int tmp = ints[i]; - ints[i] = ints[i+1]; - ints[i+1] = tmp; - swap = true; - } - } - } - } - - /** - * Shifts the values of all coefficients to the interval <code>[-q/2, q/2]</code>. - * - * @param q a modulus - */ - public void center0(int q) - { - for (int i = 0; i < coeffs.length; i++) - { - while (coeffs[i] < -q / 2) - { - coeffs[i] += q; - } - while (coeffs[i] > q / 2) - { - coeffs[i] -= q; - } - } - } - - /** - * Returns the sum of all coefficients, i.e. evaluates the polynomial at 0. - * - * @return the sum of all coefficients - */ - public int sumCoeffs() - { - int sum = 0; - for (int i = 0; i < coeffs.length; i++) - { - sum += coeffs[i]; - } - return sum; - } - - /** - * Tests if <code>p(x) = 0</code>. - * - * @return true iff all coefficients are zeros - */ - private boolean equalsZero() - { - for (int i = 0; i < coeffs.length; i++) - { - if (coeffs[i] != 0) - { - return false; - } - } - return true; - } - - /** - * Tests if <code>p(x) = 1</code>. - * - * @return true iff all coefficients are equal to zero, except for the lowest coefficient which must equal 1 - */ - public boolean equalsOne() - { - for (int i = 1; i < coeffs.length; i++) - { - if (coeffs[i] != 0) - { - return false; - } - } - return coeffs[0] == 1; - } - - /** - * Tests if <code>|p(x)| = 1</code>. - * - * @return true iff all coefficients are equal to zero, except for the lowest coefficient which must equal 1 or -1 - */ - private boolean equalsAbsOne() - { - for (int i = 1; i < coeffs.length; i++) - { - if (coeffs[i] != 0) - { - return false; - } - } - return Math.abs(coeffs[0]) == 1; - } - - /** - * Counts the number of coefficients equal to an integer - * - * @param value an integer - * @return the number of coefficients equal to <code>value</code> - */ - public int count(int value) - { - int count = 0; - for (int i = 0; i != coeffs.length; i++) - { - if (coeffs[i] == value) - { - count++; - } - } - return count; - } - - /** - * Multiplication by <code>X</code> in <code>Z[X]/Z[X^n-1]</code>. - */ - public void rotate1() - { - int clast = coeffs[coeffs.length - 1]; - for (int i = coeffs.length - 1; i > 0; i--) - { - coeffs[i] = coeffs[i - 1]; - } - coeffs[0] = clast; - } - - public void clear() - { - for (int i = 0; i < coeffs.length; i++) - { - coeffs[i] = 0; - } - } - - public IntegerPolynomial toIntegerPolynomial() - { - return (IntegerPolynomial)clone(); - } - - public Object clone() - { - return new IntegerPolynomial(coeffs.clone()); - } - - public boolean equals(Object obj) - { - if (obj instanceof IntegerPolynomial) - { - return Arrays.areEqual(coeffs, ((IntegerPolynomial)obj).coeffs); - } - else - { - return false; - } - } - - /** - * Calls {@link IntegerPolynomial#resultant(int) - */ - private class ModResultantTask - implements Callable<ModularResultant> - { - private int modulus; - - private ModResultantTask(int modulus) - { - this.modulus = modulus; - } - - public ModularResultant call() - { - return resultant(modulus); - } - } - - /** - * Calls {@link ModularResultant#combineRho(ModularResultant, ModularResultant) - */ - private class CombineTask - implements Callable<ModularResultant> - { - private ModularResultant modRes1; - private ModularResultant modRes2; - - private CombineTask(ModularResultant modRes1, ModularResultant modRes2) - { - this.modRes1 = modRes1; - this.modRes2 = modRes2; - } - - public ModularResultant call() - { - return ModularResultant.combineRho(modRes1, modRes2); - } - } -} diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/LongPolynomial2.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/LongPolynomial2.java deleted file mode 100644 index d71615a..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/LongPolynomial2.java +++ /dev/null @@ -1,255 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial; - -import org.bouncycastle.util.Arrays; - -/** - * A polynomial class that combines two coefficients into one <code>long</code> value for - * faster multiplication in 64 bit environments.<br> - * Coefficients can be between 0 and 2047 and are stored in pairs in the bits 0..10 and 24..34 of a <code>long</code> number. - */ -public class LongPolynomial2 -{ - private long[] coeffs; // each representing two coefficients in the original IntegerPolynomial - private int numCoeffs; - - /** - * Constructs a <code>LongPolynomial2</code> from a <code>IntegerPolynomial</code>. The two polynomials are independent of each other. - * - * @param p the original polynomial. Coefficients must be between 0 and 2047. - */ - public LongPolynomial2(IntegerPolynomial p) - { - numCoeffs = p.coeffs.length; - coeffs = new long[(numCoeffs + 1) / 2]; - int idx = 0; - for (int pIdx = 0; pIdx < numCoeffs; ) - { - int c0 = p.coeffs[pIdx++]; - while (c0 < 0) - { - c0 += 2048; - } - long c1 = pIdx < numCoeffs ? p.coeffs[pIdx++] : 0; - while (c1 < 0) - { - c1 += 2048; - } - coeffs[idx] = c0 + (c1 << 24); - idx++; - } - } - - private LongPolynomial2(long[] coeffs) - { - this.coeffs = coeffs; - } - - private LongPolynomial2(int N) - { - coeffs = new long[N]; - } - - /** - * Multiplies the polynomial with another, taking the indices mod N and the values mod 2048. - */ - public LongPolynomial2 mult(LongPolynomial2 poly2) - { - int N = coeffs.length; - if (poly2.coeffs.length != N || numCoeffs != poly2.numCoeffs) - { - throw new IllegalArgumentException("Number of coefficients must be the same"); - } - - LongPolynomial2 c = multRecursive(poly2); - - if (c.coeffs.length > N) - { - if (numCoeffs % 2 == 0) - { - for (int k = N; k < c.coeffs.length; k++) - { - c.coeffs[k - N] = (c.coeffs[k - N] + c.coeffs[k]) & 0x7FF0007FFL; - } - c.coeffs = Arrays.copyOf(c.coeffs, N); - } - else - { - for (int k = N; k < c.coeffs.length; k++) - { - c.coeffs[k - N] = c.coeffs[k - N] + (c.coeffs[k - 1] >> 24); - c.coeffs[k - N] = c.coeffs[k - N] + ((c.coeffs[k] & 2047) << 24); - c.coeffs[k - N] &= 0x7FF0007FFL; - } - c.coeffs = Arrays.copyOf(c.coeffs, N); - c.coeffs[c.coeffs.length - 1] &= 2047; - } - } - - c = new LongPolynomial2(c.coeffs); - c.numCoeffs = numCoeffs; - return c; - } - - public IntegerPolynomial toIntegerPolynomial() - { - int[] intCoeffs = new int[numCoeffs]; - int uIdx = 0; - for (int i = 0; i < coeffs.length; i++) - { - intCoeffs[uIdx++] = (int)(coeffs[i] & 2047); - if (uIdx < numCoeffs) - { - intCoeffs[uIdx++] = (int)((coeffs[i] >> 24) & 2047); - } - } - return new IntegerPolynomial(intCoeffs); - } - - /** - * Karazuba multiplication - */ - private LongPolynomial2 multRecursive(LongPolynomial2 poly2) - { - long[] a = coeffs; - long[] b = poly2.coeffs; - - int n = poly2.coeffs.length; - if (n <= 32) - { - int cn = 2 * n; - LongPolynomial2 c = new LongPolynomial2(new long[cn]); - for (int k = 0; k < cn; k++) - { - for (int i = Math.max(0, k - n + 1); i <= Math.min(k, n - 1); i++) - { - long c0 = a[k - i] * b[i]; - long cu = c0 & 0x7FF000000L + (c0 & 2047); - long co = (c0 >>> 48) & 2047; - - c.coeffs[k] = (c.coeffs[k] + cu) & 0x7FF0007FFL; - c.coeffs[k + 1] = (c.coeffs[k + 1] + co) & 0x7FF0007FFL; - } - } - return c; - } - else - { - int n1 = n / 2; - - LongPolynomial2 a1 = new LongPolynomial2(Arrays.copyOf(a, n1)); - LongPolynomial2 a2 = new LongPolynomial2(Arrays.copyOfRange(a, n1, n)); - LongPolynomial2 b1 = new LongPolynomial2(Arrays.copyOf(b, n1)); - LongPolynomial2 b2 = new LongPolynomial2(Arrays.copyOfRange(b, n1, n)); - - LongPolynomial2 A = (LongPolynomial2)a1.clone(); - A.add(a2); - LongPolynomial2 B = (LongPolynomial2)b1.clone(); - B.add(b2); - - LongPolynomial2 c1 = a1.multRecursive(b1); - LongPolynomial2 c2 = a2.multRecursive(b2); - LongPolynomial2 c3 = A.multRecursive(B); - c3.sub(c1); - c3.sub(c2); - - LongPolynomial2 c = new LongPolynomial2(2 * n); - for (int i = 0; i < c1.coeffs.length; i++) - { - c.coeffs[i] = c1.coeffs[i] & 0x7FF0007FFL; - } - for (int i = 0; i < c3.coeffs.length; i++) - { - c.coeffs[n1 + i] = (c.coeffs[n1 + i] + c3.coeffs[i]) & 0x7FF0007FFL; - } - for (int i = 0; i < c2.coeffs.length; i++) - { - c.coeffs[2 * n1 + i] = (c.coeffs[2 * n1 + i] + c2.coeffs[i]) & 0x7FF0007FFL; - } - return c; - } - } - - /** - * Adds another polynomial which can have a different number of coefficients. - * - * @param b another polynomial - */ - private void add(LongPolynomial2 b) - { - if (b.coeffs.length > coeffs.length) - { - coeffs = Arrays.copyOf(coeffs, b.coeffs.length); - } - for (int i = 0; i < b.coeffs.length; i++) - { - coeffs[i] = (coeffs[i] + b.coeffs[i]) & 0x7FF0007FFL; - } - } - - /** - * Subtracts another polynomial which can have a different number of coefficients. - * - * @param b another polynomial - */ - private void sub(LongPolynomial2 b) - { - if (b.coeffs.length > coeffs.length) - { - coeffs = Arrays.copyOf(coeffs, b.coeffs.length); - } - for (int i = 0; i < b.coeffs.length; i++) - { - coeffs[i] = (0x0800000800000L + coeffs[i] - b.coeffs[i]) & 0x7FF0007FFL; - } - } - - /** - * Subtracts another polynomial which must have the same number of coefficients, - * and applies an AND mask to the upper and lower halves of each coefficients. - * - * @param b another polynomial - * @param mask a bit mask less than 2048 to apply to each 11-bit coefficient - */ - public void subAnd(LongPolynomial2 b, int mask) - { - long longMask = (((long)mask) << 24) + mask; - for (int i = 0; i < b.coeffs.length; i++) - { - coeffs[i] = (0x0800000800000L + coeffs[i] - b.coeffs[i]) & longMask; - } - } - - /** - * Multiplies this polynomial by 2 and applies an AND mask to the upper and - * lower halves of each coefficients. - * - * @param mask a bit mask less than 2048 to apply to each 11-bit coefficient - */ - public void mult2And(int mask) - { - long longMask = (((long)mask) << 24) + mask; - for (int i = 0; i < coeffs.length; i++) - { - coeffs[i] = (coeffs[i] << 1) & longMask; - } - } - - public Object clone() - { - LongPolynomial2 p = new LongPolynomial2(coeffs.clone()); - p.numCoeffs = numCoeffs; - return p; - } - - public boolean equals(Object obj) - { - if (obj instanceof LongPolynomial2) - { - return Arrays.areEqual(coeffs, ((LongPolynomial2)obj).coeffs); - } - else - { - return false; - } - } -} diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/LongPolynomial5.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/LongPolynomial5.java deleted file mode 100644 index c804cc8..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/LongPolynomial5.java +++ /dev/null @@ -1,149 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial; - -import org.bouncycastle.util.Arrays; - -/** - * A polynomial class that combines five coefficients into one <code>long</code> value for - * faster multiplication by a ternary polynomial.<br> - * Coefficients can be between 0 and 2047 and are stored in bits 0..11, 12..23, ..., 48..59 of a <code>long</code> number. - */ -public class LongPolynomial5 -{ - private long[] coeffs; // groups of 5 coefficients - private int numCoeffs; - - /** - * Constructs a <code>LongPolynomial5</code> from a <code>IntegerPolynomial</code>. The two polynomials are independent of each other. - * - * @param p the original polynomial. Coefficients must be between 0 and 2047. - */ - public LongPolynomial5(IntegerPolynomial p) - { - numCoeffs = p.coeffs.length; - - coeffs = new long[(numCoeffs + 4) / 5]; - int cIdx = 0; - int shift = 0; - for (int i = 0; i < numCoeffs; i++) - { - coeffs[cIdx] |= ((long)p.coeffs[i]) << shift; - shift += 12; - if (shift >= 60) - { - shift = 0; - cIdx++; - } - } - } - - private LongPolynomial5(long[] coeffs, int numCoeffs) - { - this.coeffs = coeffs; - this.numCoeffs = numCoeffs; - } - - /** - * Multiplies the polynomial with a <code>TernaryPolynomial</code>, taking the indices mod N and the values mod 2048. - */ - public LongPolynomial5 mult(TernaryPolynomial poly2) - { - long[][] prod = new long[5][coeffs.length + (poly2.size() + 4) / 5 - 1]; // intermediate results, the subarrays are shifted by 0,...,4 coefficients - - // multiply ones - int[] ones = poly2.getOnes(); - for (int idx = 0; idx != ones.length; idx++) - { - int pIdx = ones[idx]; - int cIdx = pIdx / 5; - int m = pIdx - cIdx * 5; // m = pIdx % 5 - for (int i = 0; i < coeffs.length; i++) - { - prod[m][cIdx] = (prod[m][cIdx] + coeffs[i]) & 0x7FF7FF7FF7FF7FFL; - cIdx++; - } - } - - // multiply negative ones - int[] negOnes = poly2.getNegOnes(); - for (int idx = 0; idx != negOnes.length; idx++) - { - int pIdx = negOnes[idx]; - int cIdx = pIdx / 5; - int m = pIdx - cIdx * 5; // m = pIdx % 5 - for (int i = 0; i < coeffs.length; i++) - { - prod[m][cIdx] = (0x800800800800800L + prod[m][cIdx] - coeffs[i]) & 0x7FF7FF7FF7FF7FFL; - cIdx++; - } - } - - // combine shifted coefficients (5 arrays) into a single array of length prod[*].length+1 - long[] cCoeffs = Arrays.copyOf(prod[0], prod[0].length + 1); - for (int m = 1; m <= 4; m++) - { - int shift = m * 12; - int shift60 = 60 - shift; - long mask = (1L << shift60) - 1; - int pLen = prod[m].length; - for (int i = 0; i < pLen; i++) - { - long upper, lower; - upper = prod[m][i] >> shift60; - lower = prod[m][i] & mask; - - cCoeffs[i] = (cCoeffs[i] + (lower << shift)) & 0x7FF7FF7FF7FF7FFL; - int nextIdx = i + 1; - cCoeffs[nextIdx] = (cCoeffs[nextIdx] + upper) & 0x7FF7FF7FF7FF7FFL; - } - } - - // reduce indices of cCoeffs modulo numCoeffs - int shift = 12 * (numCoeffs % 5); - for (int cIdx = coeffs.length - 1; cIdx < cCoeffs.length; cIdx++) - { - long iCoeff; // coefficient to shift into the [0..numCoeffs-1] range - int newIdx; - if (cIdx == coeffs.length - 1) - { - iCoeff = numCoeffs == 5 ? 0 : cCoeffs[cIdx] >> shift; - newIdx = 0; - } - else - { - iCoeff = cCoeffs[cIdx]; - newIdx = cIdx * 5 - numCoeffs; - } - - int base = newIdx / 5; - int m = newIdx - base * 5; // m = newIdx % 5 - long lower = iCoeff << (12 * m); - long upper = iCoeff >> (12 * (5 - m)); - cCoeffs[base] = (cCoeffs[base] + lower) & 0x7FF7FF7FF7FF7FFL; - int base1 = base + 1; - if (base1 < coeffs.length) - { - cCoeffs[base1] = (cCoeffs[base1] + upper) & 0x7FF7FF7FF7FF7FFL; - } - } - - return new LongPolynomial5(cCoeffs, numCoeffs); - } - - public IntegerPolynomial toIntegerPolynomial() - { - int[] intCoeffs = new int[numCoeffs]; - int cIdx = 0; - int shift = 0; - for (int i = 0; i < numCoeffs; i++) - { - intCoeffs[i] = (int)((coeffs[cIdx] >> shift) & 2047); - shift += 12; - if (shift >= 60) - { - shift = 0; - cIdx++; - } - } - return new IntegerPolynomial(intCoeffs); - } -} diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/ModularResultant.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/ModularResultant.java deleted file mode 100644 index 5f77192..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/ModularResultant.java +++ /dev/null @@ -1,46 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial; - -import java.math.BigInteger; - -import org.bouncycastle.pqc.math.ntru.euclid.BigIntEuclidean; - -/** - * A resultant modulo a <code>BigInteger</code> - */ -public class ModularResultant - extends Resultant -{ - BigInteger modulus; - - ModularResultant(BigIntPolynomial rho, BigInteger res, BigInteger modulus) - { - super(rho, res); - this.modulus = modulus; - } - - /** - * Calculates a <code>rho</code> modulo <code>m1*m2</code> from - * two resultants whose <code>rho</code>s are modulo <code>m1</code> and <code>m2</code>.<br/> - * </code>res</code> is set to <code>null</code>. - * - * @param modRes1 - * @param modRes2 - * @return <code>rho</code> modulo <code>modRes1.modulus * modRes2.modulus</code>, and <code>null</code> for </code>res</code>. - */ - static ModularResultant combineRho(ModularResultant modRes1, ModularResultant modRes2) - { - BigInteger mod1 = modRes1.modulus; - BigInteger mod2 = modRes2.modulus; - BigInteger prod = mod1.multiply(mod2); - BigIntEuclidean er = BigIntEuclidean.calculate(mod2, mod1); - - BigIntPolynomial rho1 = (BigIntPolynomial)modRes1.rho.clone(); - rho1.mult(er.x.multiply(mod2)); - BigIntPolynomial rho2 = (BigIntPolynomial)modRes2.rho.clone(); - rho2.mult(er.y.multiply(mod1)); - rho1.add(rho2); - rho1.mod(prod); - - return new ModularResultant(rho1, null, prod); - } -} diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/Polynomial.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/Polynomial.java deleted file mode 100644 index 69193e3..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/Polynomial.java +++ /dev/null @@ -1,42 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial; - -public interface Polynomial -{ - - /** - * Multiplies the polynomial by an <code>IntegerPolynomial</code>, - * taking the indices mod <code>N</code>. - * - * @param poly2 a polynomial - * @return the product of the two polynomials - */ - IntegerPolynomial mult(IntegerPolynomial poly2); - - /** - * Multiplies the polynomial by an <code>IntegerPolynomial</code>, - * taking the coefficient values mod <code>modulus</code> and the indices mod <code>N</code>. - * - * @param poly2 a polynomial - * @param modulus a modulus to apply - * @return the product of the two polynomials - */ - IntegerPolynomial mult(IntegerPolynomial poly2, int modulus); - - /** - * Returns a polynomial that is equal to this polynomial (in the sense that {@link #mult(IntegerPolynomial, int)} - * returns equal <code>IntegerPolynomial</code>s). The new polynomial is guaranteed to be independent of the original. - * - * @return a new <code>IntegerPolynomial</code>. - */ - IntegerPolynomial toIntegerPolynomial(); - - /** - * Multiplies the polynomial by a <code>BigIntPolynomial</code>, taking the indices mod N. Does not - * change this polynomial but returns the result as a new polynomial.<br> - * Both polynomials must have the same number of coefficients. - * - * @param poly2 the polynomial to multiply by - * @return a new polynomial - */ - BigIntPolynomial mult(BigIntPolynomial poly2); -} diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/ProductFormPolynomial.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/ProductFormPolynomial.java deleted file mode 100644 index dd18902..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/ProductFormPolynomial.java +++ /dev/null @@ -1,153 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial; - -import java.io.ByteArrayInputStream; -import java.io.IOException; -import java.io.InputStream; -import java.security.SecureRandom; - -import org.bouncycastle.util.Arrays; - -/** - * A polynomial of the form <code>f1*f2+f3</code>, where - * <code>f1,f2,f3</code> are very sparsely populated ternary polynomials. - */ -public class ProductFormPolynomial - implements Polynomial -{ - private SparseTernaryPolynomial f1, f2, f3; - - public ProductFormPolynomial(SparseTernaryPolynomial f1, SparseTernaryPolynomial f2, SparseTernaryPolynomial f3) - { - this.f1 = f1; - this.f2 = f2; - this.f3 = f3; - } - - public static ProductFormPolynomial generateRandom(int N, int df1, int df2, int df3Ones, int df3NegOnes, SecureRandom random) - { - SparseTernaryPolynomial f1 = SparseTernaryPolynomial.generateRandom(N, df1, df1, random); - SparseTernaryPolynomial f2 = SparseTernaryPolynomial.generateRandom(N, df2, df2, random); - SparseTernaryPolynomial f3 = SparseTernaryPolynomial.generateRandom(N, df3Ones, df3NegOnes, random); - return new ProductFormPolynomial(f1, f2, f3); - } - - public static ProductFormPolynomial fromBinary(byte[] data, int N, int df1, int df2, int df3Ones, int df3NegOnes) - throws IOException - { - return fromBinary(new ByteArrayInputStream(data), N, df1, df2, df3Ones, df3NegOnes); - } - - public static ProductFormPolynomial fromBinary(InputStream is, int N, int df1, int df2, int df3Ones, int df3NegOnes) - throws IOException - { - SparseTernaryPolynomial f1; - - f1 = SparseTernaryPolynomial.fromBinary(is, N, df1, df1); - SparseTernaryPolynomial f2 = SparseTernaryPolynomial.fromBinary(is, N, df2, df2); - SparseTernaryPolynomial f3 = SparseTernaryPolynomial.fromBinary(is, N, df3Ones, df3NegOnes); - return new ProductFormPolynomial(f1, f2, f3); - } - - public byte[] toBinary() - { - byte[] f1Bin = f1.toBinary(); - byte[] f2Bin = f2.toBinary(); - byte[] f3Bin = f3.toBinary(); - - byte[] all = Arrays.copyOf(f1Bin, f1Bin.length + f2Bin.length + f3Bin.length); - System.arraycopy(f2Bin, 0, all, f1Bin.length, f2Bin.length); - System.arraycopy(f3Bin, 0, all, f1Bin.length + f2Bin.length, f3Bin.length); - return all; - } - - public IntegerPolynomial mult(IntegerPolynomial b) - { - IntegerPolynomial c = f1.mult(b); - c = f2.mult(c); - c.add(f3.mult(b)); - return c; - } - - public BigIntPolynomial mult(BigIntPolynomial b) - { - BigIntPolynomial c = f1.mult(b); - c = f2.mult(c); - c.add(f3.mult(b)); - return c; - } - - public IntegerPolynomial toIntegerPolynomial() - { - IntegerPolynomial i = f1.mult(f2.toIntegerPolynomial()); - i.add(f3.toIntegerPolynomial()); - return i; - } - - public IntegerPolynomial mult(IntegerPolynomial poly2, int modulus) - { - IntegerPolynomial c = mult(poly2); - c.mod(modulus); - return c; - } - - public int hashCode() - { - final int prime = 31; - int result = 1; - result = prime * result + ((f1 == null) ? 0 : f1.hashCode()); - result = prime * result + ((f2 == null) ? 0 : f2.hashCode()); - result = prime * result + ((f3 == null) ? 0 : f3.hashCode()); - return result; - } - - public boolean equals(Object obj) - { - if (this == obj) - { - return true; - } - if (obj == null) - { - return false; - } - if (getClass() != obj.getClass()) - { - return false; - } - ProductFormPolynomial other = (ProductFormPolynomial)obj; - if (f1 == null) - { - if (other.f1 != null) - { - return false; - } - } - else if (!f1.equals(other.f1)) - { - return false; - } - if (f2 == null) - { - if (other.f2 != null) - { - return false; - } - } - else if (!f2.equals(other.f2)) - { - return false; - } - if (f3 == null) - { - if (other.f3 != null) - { - return false; - } - } - else if (!f3.equals(other.f3)) - { - return false; - } - return true; - } -} diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/Resultant.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/Resultant.java deleted file mode 100644 index ec58577..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/Resultant.java +++ /dev/null @@ -1,28 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial; - -import java.math.BigInteger; - -/** - * Contains a resultant and a polynomial <code>rho</code> such that - * <code>res = rho*this + t*(x^n-1) for some integer t</code>. - * - * @see IntegerPolynomial#resultant() - * @see IntegerPolynomial#resultant(int) - */ -public class Resultant -{ - /** - * A polynomial such that <code>res = rho*this + t*(x^n-1) for some integer t</code> - */ - public BigIntPolynomial rho; - /** - * Resultant of a polynomial with <code>x^n-1</code> - */ - public BigInteger res; - - Resultant(BigIntPolynomial rho, BigInteger res) - { - this.rho = rho; - this.res = res; - } -} diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/SparseTernaryPolynomial.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/SparseTernaryPolynomial.java deleted file mode 100644 index 3c91339..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/SparseTernaryPolynomial.java +++ /dev/null @@ -1,320 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial; - -import java.io.IOException; -import java.io.InputStream; -import java.math.BigInteger; -import java.security.SecureRandom; - -import org.bouncycastle.pqc.math.ntru.util.ArrayEncoder; -import org.bouncycastle.pqc.math.ntru.util.Util; -import org.bouncycastle.util.Arrays; - -/** - * A <code>TernaryPolynomial</code> with a "low" number of nonzero coefficients. - */ -public class SparseTernaryPolynomial - implements TernaryPolynomial -{ - /** - * Number of bits to use for each coefficient. Determines the upper bound for <code>N</code>. - */ - private static final int BITS_PER_INDEX = 11; - - private int N; - private int[] ones; - private int[] negOnes; - - /** - * Constructs a new polynomial. - * - * @param N total number of coefficients including zeros - * @param ones indices of coefficients equal to 1 - * @param negOnes indices of coefficients equal to -1 - */ - SparseTernaryPolynomial(int N, int[] ones, int[] negOnes) - { - this.N = N; - this.ones = ones; - this.negOnes = negOnes; - } - - /** - * Constructs a <code>DenseTernaryPolynomial</code> from a <code>IntegerPolynomial</code>. The two polynomials are - * independent of each other. - * - * @param intPoly the original polynomial - */ - public SparseTernaryPolynomial(IntegerPolynomial intPoly) - { - this(intPoly.coeffs); - } - - /** - * Constructs a new <code>SparseTernaryPolynomial</code> with a given set of coefficients. - * - * @param coeffs the coefficients - */ - public SparseTernaryPolynomial(int[] coeffs) - { - N = coeffs.length; - ones = new int[N]; - negOnes = new int[N]; - int onesIdx = 0; - int negOnesIdx = 0; - for (int i = 0; i < N; i++) - { - int c = coeffs[i]; - switch (c) - { - case 1: - ones[onesIdx++] = i; - break; - case -1: - negOnes[negOnesIdx++] = i; - break; - case 0: - break; - default: - throw new IllegalArgumentException("Illegal value: " + c + ", must be one of {-1, 0, 1}"); - } - } - ones = Arrays.copyOf(ones, onesIdx); - negOnes = Arrays.copyOf(negOnes, negOnesIdx); - } - - /** - * Decodes a byte array encoded with {@link #toBinary()} to a ploynomial. - * - * @param is an input stream containing an encoded polynomial - * @param N number of coefficients including zeros - * @param numOnes number of coefficients equal to 1 - * @param numNegOnes number of coefficients equal to -1 - * @return the decoded polynomial - * @throws IOException - */ - public static SparseTernaryPolynomial fromBinary(InputStream is, int N, int numOnes, int numNegOnes) - throws IOException - { - int maxIndex = 1 << BITS_PER_INDEX; - int bitsPerIndex = 32 - Integer.numberOfLeadingZeros(maxIndex - 1); - - int data1Len = (numOnes * bitsPerIndex + 7) / 8; - byte[] data1 = Util.readFullLength(is, data1Len); - int[] ones = ArrayEncoder.decodeModQ(data1, numOnes, maxIndex); - - int data2Len = (numNegOnes * bitsPerIndex + 7) / 8; - byte[] data2 = Util.readFullLength(is, data2Len); - int[] negOnes = ArrayEncoder.decodeModQ(data2, numNegOnes, maxIndex); - - return new SparseTernaryPolynomial(N, ones, negOnes); - } - - /** - * Generates a random polynomial with <code>numOnes</code> coefficients equal to 1, - * <code>numNegOnes</code> coefficients equal to -1, and the rest equal to 0. - * - * @param N number of coefficients - * @param numOnes number of 1's - * @param numNegOnes number of -1's - */ - public static SparseTernaryPolynomial generateRandom(int N, int numOnes, int numNegOnes, SecureRandom random) - { - int[] coeffs = Util.generateRandomTernary(N, numOnes, numNegOnes, random); - return new SparseTernaryPolynomial(coeffs); - } - - public IntegerPolynomial mult(IntegerPolynomial poly2) - { - int[] b = poly2.coeffs; - if (b.length != N) - { - throw new IllegalArgumentException("Number of coefficients must be the same"); - } - - int[] c = new int[N]; - for (int idx = 0; idx != ones.length; idx++) - { - int i = ones[idx]; - int j = N - 1 - i; - for (int k = N - 1; k >= 0; k--) - { - c[k] += b[j]; - j--; - if (j < 0) - { - j = N - 1; - } - } - } - - for (int idx = 0; idx != negOnes.length; idx++) - { - int i = negOnes[idx]; - int j = N - 1 - i; - for (int k = N - 1; k >= 0; k--) - { - c[k] -= b[j]; - j--; - if (j < 0) - { - j = N - 1; - } - } - } - - return new IntegerPolynomial(c); - } - - public IntegerPolynomial mult(IntegerPolynomial poly2, int modulus) - { - IntegerPolynomial c = mult(poly2); - c.mod(modulus); - return c; - } - - public BigIntPolynomial mult(BigIntPolynomial poly2) - { - BigInteger[] b = poly2.coeffs; - if (b.length != N) - { - throw new IllegalArgumentException("Number of coefficients must be the same"); - } - - BigInteger[] c = new BigInteger[N]; - for (int i = 0; i < N; i++) - { - c[i] = BigInteger.ZERO; - } - - for (int idx = 0; idx != ones.length; idx++) - { - int i = ones[idx]; - int j = N - 1 - i; - for (int k = N - 1; k >= 0; k--) - { - c[k] = c[k].add(b[j]); - j--; - if (j < 0) - { - j = N - 1; - } - } - } - - for (int idx = 0; idx != negOnes.length; idx++) - { - int i = negOnes[idx]; - int j = N - 1 - i; - for (int k = N - 1; k >= 0; k--) - { - c[k] = c[k].subtract(b[j]); - j--; - if (j < 0) - { - j = N - 1; - } - } - } - - return new BigIntPolynomial(c); - } - - public int[] getOnes() - { - return ones; - } - - public int[] getNegOnes() - { - return negOnes; - } - - /** - * Encodes the polynomial to a byte array writing <code>BITS_PER_INDEX</code> bits for each coefficient. - * - * @return the encoded polynomial - */ - public byte[] toBinary() - { - int maxIndex = 1 << BITS_PER_INDEX; - byte[] bin1 = ArrayEncoder.encodeModQ(ones, maxIndex); - byte[] bin2 = ArrayEncoder.encodeModQ(negOnes, maxIndex); - - byte[] bin = Arrays.copyOf(bin1, bin1.length + bin2.length); - System.arraycopy(bin2, 0, bin, bin1.length, bin2.length); - return bin; - } - - public IntegerPolynomial toIntegerPolynomial() - { - int[] coeffs = new int[N]; - for (int idx = 0; idx != ones.length; idx++) - { - int i = ones[idx]; - coeffs[i] = 1; - } - for (int idx = 0; idx != negOnes.length; idx++) - { - int i = negOnes[idx]; - coeffs[i] = -1; - } - return new IntegerPolynomial(coeffs); - } - - public int size() - { - return N; - } - - public void clear() - { - for (int i = 0; i < ones.length; i++) - { - ones[i] = 0; - } - for (int i = 0; i < negOnes.length; i++) - { - negOnes[i] = 0; - } - } - - public int hashCode() - { - final int prime = 31; - int result = 1; - result = prime * result + N; - result = prime * result + Arrays.hashCode(negOnes); - result = prime * result + Arrays.hashCode(ones); - return result; - } - - public boolean equals(Object obj) - { - if (this == obj) - { - return true; - } - if (obj == null) - { - return false; - } - if (getClass() != obj.getClass()) - { - return false; - } - SparseTernaryPolynomial other = (SparseTernaryPolynomial)obj; - if (N != other.N) - { - return false; - } - if (!Arrays.areEqual(negOnes, other.negOnes)) - { - return false; - } - if (!Arrays.areEqual(ones, other.ones)) - { - return false; - } - return true; - } -} diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/TernaryPolynomial.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/TernaryPolynomial.java deleted file mode 100644 index 822b64b..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/TernaryPolynomial.java +++ /dev/null @@ -1,25 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial; - -/** - * A polynomial whose coefficients are all equal to -1, 0, or 1 - */ -public interface TernaryPolynomial - extends Polynomial -{ - - /** - * Multiplies the polynomial by an <code>IntegerPolynomial</code>, taking the indices mod N - */ - IntegerPolynomial mult(IntegerPolynomial poly2); - - int[] getOnes(); - - int[] getNegOnes(); - - /** - * Returns the maximum number of coefficients the polynomial can have - */ - int size(); - - void clear(); -} diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/AllTests.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/AllTests.java deleted file mode 100644 index 296a66e..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/AllTests.java +++ /dev/null @@ -1,29 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial.test; - -import junit.framework.Test; -import junit.framework.TestCase; -import junit.framework.TestSuite; - -public class AllTests - extends TestCase -{ - public static void main (String[] args) - { - junit.textui.TestRunner.run(suite()); - } - - public static Test suite() - { - TestSuite suite = new TestSuite("NTRU Polynomial Tests"); - - suite.addTestSuite(BigDecimalPolynomialTest.class); - suite.addTestSuite(BigIntPolynomialTest.class); - suite.addTestSuite(IntegerPolynomialTest.class); - suite.addTestSuite(LongPolynomial2Test.class); - suite.addTestSuite(LongPolynomial5Test.class); - suite.addTestSuite(ProductFormPolynomialTest.class); - suite.addTestSuite(SparseTernaryPolynomialTest.class); - - return suite; - } -} diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/BigDecimalPolynomialTest.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/BigDecimalPolynomialTest.java deleted file mode 100644 index 06e9e04..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/BigDecimalPolynomialTest.java +++ /dev/null @@ -1,47 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial.test; - -import java.math.BigDecimal; -import java.security.SecureRandom; - -import junit.framework.TestCase; -import org.bouncycastle.pqc.math.ntru.polynomial.BigDecimalPolynomial; -import org.bouncycastle.pqc.math.ntru.polynomial.BigIntPolynomial; -import org.bouncycastle.pqc.math.ntru.polynomial.DenseTernaryPolynomial; -import org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial; - -public class BigDecimalPolynomialTest - extends TestCase -{ - public void testMult() - { - BigDecimalPolynomial a = new BigDecimalPolynomial(new BigIntPolynomial(new IntegerPolynomial(new int[]{4, -1, 9, 2, 1, -5, 12, -7, 0, -9, 5}))); - BigDecimalPolynomial b = new BigDecimalPolynomial(new BigIntPolynomial(new IntegerPolynomial(new int[]{-6, 0, 0, 13, 3, -2, -4, 10, 11, 2, -1}))); - BigDecimalPolynomial c = a.mult(b); - BigDecimal[] expectedCoeffs = new BigDecimalPolynomial(new BigIntPolynomial(new IntegerPolynomial(new int[]{2, -189, 77, 124, -29, 0, -75, 124, -49, 267, 34}))).getCoeffs(); - - BigDecimal[] cCoeffs = c.getCoeffs(); - - assertEquals(expectedCoeffs.length, cCoeffs.length); - for (int i = 0; i != cCoeffs.length; i++) - { - assertEquals(expectedCoeffs[i], cCoeffs[i]); - } - - // multiply a polynomial by its inverse modulo 2048 and check that the result is 1 - SecureRandom random = new SecureRandom(); - IntegerPolynomial d, dInv; - do - { - d = DenseTernaryPolynomial.generateRandom(1001, 333, 334, random); - dInv = d.invertFq(2048); - } - while (dInv == null); - - d.mod(2048); - BigDecimalPolynomial e = new BigDecimalPolynomial(new BigIntPolynomial(d)); - BigIntPolynomial f = new BigIntPolynomial(dInv); - IntegerPolynomial g = new IntegerPolynomial(e.mult(f).round()); - g.modPositive(2048); - assertTrue(g.equalsOne()); - } -}
\ No newline at end of file diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/BigIntPolynomialTest.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/BigIntPolynomialTest.java deleted file mode 100644 index a6ad36e..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/BigIntPolynomialTest.java +++ /dev/null @@ -1,26 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial.test; - -import java.math.BigInteger; - -import junit.framework.TestCase; -import org.bouncycastle.pqc.math.ntru.polynomial.BigIntPolynomial; -import org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial; - -public class BigIntPolynomialTest - extends TestCase -{ - public void testMult() - { - BigIntPolynomial a = new BigIntPolynomial(new IntegerPolynomial(new int[]{4, -1, 9, 2, 1, -5, 12, -7, 0, -9, 5})); - BigIntPolynomial b = new BigIntPolynomial(new IntegerPolynomial(new int[]{-6, 0, 0, 13, 3, -2, -4, 10, 11, 2, -1})); - BigIntPolynomial c = a.mult(b); - BigInteger[] expectedCoeffs = new BigIntPolynomial(new IntegerPolynomial(new int[]{2, -189, 77, 124, -29, 0, -75, 124, -49, 267, 34})).getCoeffs(); - BigInteger[] cCoeffs = c.getCoeffs(); - - assertEquals(expectedCoeffs.length, cCoeffs.length); - for (int i = 0; i != cCoeffs.length; i++) - { - assertEquals(expectedCoeffs[i], cCoeffs[i]); - } - } -}
\ No newline at end of file diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/IntegerPolynomialTest.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/IntegerPolynomialTest.java deleted file mode 100644 index 8f6e489..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/IntegerPolynomialTest.java +++ /dev/null @@ -1,230 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial.test; - -import java.math.BigInteger; -import java.security.SecureRandom; - -import junit.framework.TestCase; -import org.bouncycastle.pqc.crypto.ntru.NTRUSigningKeyGenerationParameters; -import org.bouncycastle.pqc.math.ntru.polynomial.BigIntPolynomial; -import org.bouncycastle.pqc.math.ntru.polynomial.DenseTernaryPolynomial; -import org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial; -import org.bouncycastle.pqc.math.ntru.polynomial.Resultant; -import org.bouncycastle.util.Arrays; - - -public class IntegerPolynomialTest - extends TestCase -{ - public void testMult() - { - // multiplication modulo q - IntegerPolynomial a = new IntegerPolynomial(new int[]{-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1}); - IntegerPolynomial b = new IntegerPolynomial(new int[]{14, 11, 26, 24, 14, 16, 30, 7, 25, 6, 19}); - IntegerPolynomial c = a.mult(b, 32); - assertEqualsMod(new int[]{3, -7, -10, -11, 10, 7, 6, 7, 5, -3, -7}, c.coeffs, 32); - - a = new IntegerPolynomial(new int[]{15, 27, 18, 16, 12, 13, 16, 2, 28, 22, 26}); - b = new IntegerPolynomial(new int[]{-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1}); - c = a.mult(b, 32); - assertEqualsMod(new int[]{8, 25, 22, 20, 12, 24, 15, 19, 12, 19, 16}, c.coeffs, 32); - - // multiplication without a modulus - a = new IntegerPolynomial(new int[]{1, 1, 0, 0, -1, -1, 0, 0, -1, 0, 1}); - b = new IntegerPolynomial(new int[]{704, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}); - c = a.mult(b); - - // mult(p, modulus) should give the same result as mult(p) followed by modulus - a = new IntegerPolynomial(new int[]{1, 0, -1, 1, 0, 1, 1, 1, -1, 1, -1}); - b = new IntegerPolynomial(new int[]{0, 1, 1, 0, 0, -1, -1, 1, 1, -1, 1}); - c = a.mult(b); - c.modPositive(20); - IntegerPolynomial d = a.mult(b, 20); - d.modPositive(20); - assertTrue(Arrays.areEqual(c.coeffs, d.coeffs)); - } - - void assertEqualsMod(int[] arr1, int[] arr2, int m) - { - assertEquals(arr1.length, arr2.length); - for (int i = 0; i < arr1.length; i++) - { - assertEquals((arr1[i] + m) % m, (arr2[i] + m) % m); - } - } - - public void testInvertFq() - { - SecureRandom random = new SecureRandom(); - // Verify an example from the NTRU tutorial - IntegerPolynomial a = new IntegerPolynomial(new int[]{-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1}); - IntegerPolynomial b = a.invertFq(32); - assertEqualsMod(new int[]{5, 9, 6, 16, 4, 15, 16, 22, 20, 18, 30}, b.coeffs, 32); - verifyInverse(a, b, 32); - - // test 3 random polynomials - int numInvertible = 0; - while (numInvertible < 3) - { - a = DenseTernaryPolynomial.generateRandom(853, random); - b = a.invertFq(2048); - if (b != null) - { - numInvertible++; - verifyInverse(a, b, 2048); - } - } - - // test a non-invertible polynomial - a = new IntegerPolynomial(new int[]{-1, 0, 1, 1, 0, 0, -1, 0, -1, 0, 1}); - b = a.invertFq(32); - assertNull(b); - } - - public void testInvertF3() - { - IntegerPolynomial a = new IntegerPolynomial(new int[]{-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1}); - IntegerPolynomial b = a.invertF3(); - assertEqualsMod(new int[]{1, 2, 0, 2, 2, 1, 0, 2, 1, 2, 0}, b.coeffs, 3); - verifyInverse(a, b, 3); - - // test a non-invertible polynomial - a = new IntegerPolynomial(new int[]{0, 1, -1, 1, 0, 0, 0, 0, -1, 0, 0}); - b = a.invertF3(); - assertNull(b); - } - - // tests if a*b=1 (mod modulus) - private void verifyInverse(IntegerPolynomial a, IntegerPolynomial b, int modulus) - { - IntegerPolynomial c = a.mult(b, modulus); - for (int i = 1; i < c.coeffs.length; i++) - { - c.coeffs[i] %= modulus; - } - c.ensurePositive(modulus); - assertTrue(c.equalsOne()); - } - - public void testFromToBinary() - { - byte[] a = new byte[]{-44, -33, 30, -109, 101, -28, -6, -105, -45, 113, -72, 99, 101, 15, 9, 49, -80, -76, 58, 42, -57, -113, -89, -14, -125, 24, 125, -16, 37, -58, 10, -49, -77, -31, 120, 103, -29, 105, -56, -126, -92, 36, 125, 127, -90, 38, 9, 4, 104, 10, -78, -106, -88, -1, -1, -43, -19, 90, 41, 0, -43, 102, 118, -72, -122, 19, -76, 57, -59, -2, 35, 47, 83, 114, 86, -115, -125, 58, 75, 115, -29, -6, 108, 6, -77, -51, 127, -8, -8, -58, -30, -126, 110, -5, -35, -41, -37, 69, 22, -48, 26, 4, -120, -19, -32, -81, -77, 124, -7, -2, -46, -96, 38, -35, 88, 4, -5, 16, 101, 29, 7, 2, 88, 35, -64, 31, -66, -70, 120, -97, 76, -74, -97, -61, 52, -56, 87, -35, 5, 95, -93, -30, 10, 38, 17, -102, -25, 86, 7, -43, 44, -52, -108, 33, -18, -110, -9, -115, 66, -71, 66, 1, -90, -72, 90, -88, -38, 75, 47, -124, -120, -15, -49, -8, 85, 5, 17, -88, 76, 99, -4, 83, 16, -91, 82, 116, 112, -83, 56, -45, -26, 125, 13, -75, -115, 92, -12, -59, 3, -12, 14, -6, 43, -17, 121, 122, 22, 92, -74, 99, -59, -103, 113, 8, -103, 114, 99, -48, 92, -88, 77, 81, 5, 31, -4, -69, -24, 23, 94, 126, 71, 93, 20, 77, 82, -54, -14, 86, 45, -81, 0, 52, -63, -66, 48, 104, -54, 15, -73, -2, -52, 115, 76, 28, -5, -94, -63, 117, -69, 0, 61, 22, -1, 71, -115, 9, -73, -100, -128, -31, 106, -74, -61, -37, 98, -6, 11, -5, 6, -18, -53, -6, 11, -49, 62, 23, 6, -128, 38, -91, 89, -34, 18, -38, -110, -101, 43, 36, 62, 101, 112, 59, -91, 78, -81, 61, 126, -21, -42, -110, -38, -27, 69, 57, 9, 24, -50, -118, 31, -17, 42, 87, -54, 122, -16, 42, -47, -19, -80, 16, 54, -97, -89, 81, -22, -35, 45, 54, -46, 22, -122, -95, -17, 7, -127, 105, -100, -56, -98, -105, 101, -81, 104, 121, -7, 33, 126, 110, -125, -85, 111, -52, 123, -98, 41, -42, 88, -68, -17, 39, -19, -96, -10, -117, 13, -88, -75, -101, -16, -7, 73, 23, -12, 41, -116, -105, -64, -4, 103, 49, -15, -49, 60, 88, -25, -21, 42, 26, 95, -90, -83, -69, 64, -2, 50, -116, -64, 26, -29, -93, -120, -70, 32, -38, 39, -126, -19, 103, 127, 65, 54, 110, 94, 126, -82, -80, -18, 43, 45, 56, -118, 109, 36, -8, 10, 113, 69, 53, -122, -127, 92, -127, -73, 70, -19, -105, -80, -15, -5, 99, -109, -27, 119, -76, -57, -48, 42, -35, 23, 39, -126, 44, -107, -100, -125, 117, -50, 115, -79, -16, 104, 8, -102, 83, -73, 21, -85, 113, -87, -54, 93, 63, -108, -64, 109, -74, 15, 14, -119, -6, -68, 45, 37, -15, -97, -95, -55, 89, 25, -63, -92, -80, -27, -8, 55, 50, 96, -91, 40, -74, 110, -96, 94, 6, 85, 92, 0, 34, -122, 5, -126, 123, 37, -90, -94, 60, 14, 36, 49, -98, -23, 57, 75, 63, 106, -7, -36, -89, 84, 71, 60, -21, 104, -47, 90, -52, -66, 88, -91, -81, -3, 116, 23, 62, -47, -84, -118, 65, 31, 7, -103, 37, -29, 115, -114, 73, 12, -121, 96, -91, -7, 56, 10, -72, 27, -45, 122, -27, -38, 74, 64, 30, -60, 64, -21, 48, 101, 113, 126, -60, -103, 71, 100, -117, 124, -125, 116, 78, 114, -74, 42, -81, -54, 34, 33, -10, 19, 23, 24, 40, 0, -8, 78, 100, 73, -88, -95, -62, -115, -18, 47, 10, -14, -39, 82, 27, -9, -115, -70, 92, -6, 39, 45, -71, -109, -41, 94, -88, -63, 19, -58, -37, -31, 1, 127, -42, 125, -120, -57, 120, -86, -6, 17, -27, -37, 47, 55, -22, -11, -31, 38, -1, 29, 56, -34, -104, -66, -62, 72, -11, -30, -30, 61, -31, 10, -63, 116, -84, 118, -127, 6, 17, -36, 91, 123, 77, 35, 22, 110, 114, 107, -3, 52, 11, 86, 68, -56, 0, 119, -43, -73, 112, 89, -4, -122, -71, -26, 103, -118, -61, -112, -108, -44, -25, -22, 4, 24, 53, -5, -71, 9, -41, 84, -28, 22, 99, 39, -26, -2, -51, 68, 63, -15, 99, 66, -78, 46, -89, 21, -38, -114, -51, 100, -59, 84, -76, -105, 51, 28, 19, 74, 42, 91, -73, 12, -89, -128, 34, 38, -100, 121, -78, 114, -28, 127, -29, 50, 105, -6, 36, 98, -35, 79, -58, 5, -13, -86, -101, -108, -99, -70, 25, 103, 63, 57, 79, -12, -63, 125, -54, 61, 15, 6, -79, 90, 76, 103, -45, 7, 39, 93, 107, 58, 76, 80, 56, -108, 55, -22, 36, 125, -91, -65, 11, 69, 10, -19, -14, -4, -26, -36, 114, 124, 63, -31, 88, 92, 108, 33, -52, -22, 80, -65, 57, 126, 43, -13, 122, -8, 68, 72, 92, -50, 100, -91, 1, -81, 75, 95, -11, -99, 38, 121, -20, -70, 82, -125, -94, -18, 16, 59, 89, 18, -96, 91, -97, 62, -96, 127, 45, 70, 16, 84, -43, -75, -118, 81, 58, 84, -115, -120, -3, 41, -103, -70, 123, 26, 101, 33, 58, 13, -11, -73, -84, -47, -7, 81, -63, 60, -45, 30, 100, -51, -15, 73, 58, -119, -3, 62, -63, -17, -69, -44, 60, -54, -115, -59, 23, -59, 98, -89, -72, 20, -96, 27, 53, -89, 59, -85, -29, 120, 23, 62, 8, -86, 113, 87, -15, 102, 106, -104, 57, -57, 37, 110, 118, 109, 25, 64, 26, -20, -86, -2, 60, -70, -33, 67, 13, -28, -29, -63, -37, 67, 99, 84, 121, -126, -38, 45, 24, 122, 51, 11, -19, -80, 26, -106, -95, 82, 69, -2, -75, 62, 106, -120, 87, -107, 87, 17, 102, -52, -16, 22, 12, -86, -48, -95, -61, 109, 64, -29, 111, 40, -90, -35, 49, 88, -15, 122, 127, 87, 113, 116, 93, 100, 28, -70, -87, -40, -1, -126, -114, 7, 79, 16, 2, -47, -98, -102, 49, 58, 61, -32, 44, 18, -26, 37, 27, -123, -76, 56, 91, 51, -21, -48, -122, -33, 40, -8, -62, -56, -126, 91, -51, 76, -29, 127, -22, -18, -110, 27, 13, -111, 81, 51, -104, 70, 98, 12, 120, -7, 15, 104, -43, -104, 124, 46, 116, 7, -26, 21, 33, 105, 17, -99, -42, -106, 8, -85, 39, 8, 79, -54, -81, 109, 40, 25, 29, -18, -90, 22, 85, -12, -16, 61, 49, -31, 127, 64, 5, 25, 39, -65, -42, 13, -97, -92, 36, -126, -18, -4, -22, -14, 109, -93, -76, -5, 13, 74, 44, 103, 79, 110, 85, 58, 39, -24, 119, 120, 122, 120, 43, 110, 67, 21, 47, 39, -48, 7, 91, -51, 126, 100, -38, -124, 0, -97, 99, -123, 118, -27, 8, 102, -106, -23, -53, -4, -56, -9, -126, -85, 93, -4, -5, 4, 49, 29, 2, 63, 78, -32, -106, 118, 111, 52, 54, 74, 53, 106, 39, -95, -38, -18, 118, -5, 94, -83, -97, -27, 62, -56, -90, -36, 43, 43, -113, 119, -89, 44, -108, -46, 66, 28, 66, -38, 3, -62, -83, -35, -127, -2, 51, 104, 105, 40, 76, -10, -124, -95, 52, 11, 101, -32, -122, -73, -17, 37, -126, 68, -126, 55, 112, -126, 38, 99, -63, 123, -74, -31, 58, 8, 93, -68, 111, -22, -24, -23, 9, -87, -25, -115, 81, -116, -91, 60, 96, -102, -1, -7, 73, 99, 46, -78, 62, 48, -116, -52, -44, -5, 82, -45, 5, -55, -101, 101, 65, -109, -108, 26, 98, -55, 11, -86, 57, 30, 92, -58, 20, 82, 65, 103, 27, -64, 76, 123, -56, -16, -111, -83, 125, 65, 111, 9, 123, 14, 119, 126, -80, 79, 94, -19, 66, -25, 35, 112, -64, 10, -66, -86, 51, 56, -78, 103, 92, -116, 8, 75, 41, -49, -79, -53, 125, -32, -76, -27, 59, -8, -4, -94, -104, -15, 79, -7, -124, 32, -87, -104, 85, -118, -36, 125, 65, 111, -105, 5, -105, 40, -50, 2, 118, 123, -54, 59, -22, 94, 20, 99, -87, -27, 28, -30, -109, 72, -19, 92, 60, 19, 115, 47, 96, -96, 10, -74, 60, 96, -86, 101, 101, 68, -44, -72, 9, -36, 126, 96, -45, -12, 9, 14, -15, 79, -79, -48, 8, -107, -81, 47, 35, -36, -107, -120, -36, -124, 37, 103, -60, -35, -74, 100, -38, -88, -99, -99, -94, -107, 79, 115, 108, 54, 119, 73, 84, 110, -74, 92, 57, 108, 80, 47, -36, -119, -115, 58, -62, -4, -97, 43, -98, 5, 112, 47, 59, -89, 82, -69, -103, 39, -29, 75, -9, -94, -72, 99, -64, 22, -10, 21, 89, 101, 21, 94, -30, -17, 73, -36, -68, -89, -91, -94, 99, -106, 119, -116, 123, -19, 54, -99, 64, -119, 82, 120, -106, -99, 80, 69, 29, -48, 77, 28, 13, 92, -107, -77, 94, -116, 108, 89, -115, 96, -41, 25, 99, -65, 118, -5, -16, 48, -122, 5, 50, -123, -115, 13, 24, 7, 15, -103, -62, -71, 92, -82, -5, -70, 49, -6, -51, -17, -47, 12, 46, -86, 30, 93, 84, -101, 43, -92, -87, -118, -110, -32, 52, 115, -4, 36, -2, -79, -69, -46, -110, 70, -82, 6, 21, -27, -11, 94, 42, -81, -96, 116, -102, -38, 36, 32, 91, 28, 80, -45, 116, -94, -33, -5, -102, 64, -96, 27, -2, 100, -126, 59, -71, 33, -36, -124, 123, 99, -76, 108, 127, -11, -24, -19, 84, -6, 19, 105, -19, -18, 120, -14, 23, 39, 54, 87, 105, 58, -95, -15, 127, -65, 114, 49, 4, -66, 32, -7, 84, 43, -103, 76, 11, 36, -68, -3, -98, -5, -43, 35, -48, 20, -40, -33, -123, 1, -54, -44, 99, -68, 8, -100, 97, -49, -10, 110, 49, 84, 46, -85, 98, -103, -58, -4, 104, -100, -40, -79, 67, -20, -95, 85, 51, 73, 10, -25, 102, 68, -97, -83, -39, 35, 2, -111, 71, 62, -89, 20, 25, -126, 17, -81, -29, 39, -27, -55, 55, -122, 97, 23, -99, 55, 86, 33, -9, 8, 55, -40, -84, 39, 38, 37, -29, 87, 113, -118, -26, 123, -95, 24, -126, 119, -94, 17, 83, -43, 10, 63, -98, 72, 8, 16, -95, -96, 119, -91, 6, 71, -60, 1, -77, 4, 53, -121, 55, 7, 36, -86, -49, -118, -121, 56, 84, -49, -57, -99, 3, -68, 37, -108, -72, 114, -74, 120, 3, 121, -28, -106, 54, -20, 63, -121, -85, -59, -111, 32, 13, -69, 122, 90, 5, 40, 88, 15, -90, 125, -28, 89, 95, 73, 96, 60, -60, -51, 102, 7, 57, 91, 59, 15, 92, -76, -34, -23, -77, 90, 45, 91, 77, -63, 94, -127, 74, -97, -44, 50, -87, -94, -25, -71, 112, 127, -117, 6, 32, -113, 54, 83, -31, 111, -73, 53, 34, -32, -98, 125, -39, 63, 15, 72, -69, 87, -118, 108, 17, 84, 15, 61, -47, 54, -24, -79, 91, 28, -28, 66, 53, 22, 9, -28, -12, 38, 64, 75, -122, 96, -59, -45, 4, -19, 47, -30, 75, -94, 62, -64, 76, -49, 19, -66, -34, 3, 84, -2, -54, 13, -84, 86, -117, 94, -27, 89, 16, 96, 52, -77, -36, -116, 27, -52, -33, -50, 14, -59, 77, 93, -109, 8, -89, 81, -114, -29, -94, 73, -119, -56, -19, 88, -17, -33, 125, -18, -68, 113, 40, -128, -112, -119, -106, -106, -30, 23, -77, 49, 3, 98, -101, 99, -107, -121, -12, -112, 24, -74, -74, 79, -17, 96, 65, -52, 86, -63, 45, 84, 119, -42, 61, -91, 29, -87, 65, -85, 99, -14, 71, 33, -41, -48, -2, -121, 78, -38, 41, -7, -37, 48, 122, 61, -124, 42, -22, 24, 2, -49, 74, -81, -88, -89, -107, 109, 53, -68, 90, -117, 123, -109, -28, 12, 80, 120, 26, -104, 73, 70, -36, 34, -80, -104, 23, 16, 14, -96, -5, 27, 71, 25, -8, -125, 58, 88, -52, -97, -97, -93, 11, -44, 116, 42, -102, -100, -31, -86, 71, 84, 70, 27, 117, -67, 92, -84, -13, 54, -102, 34, 5, 19, -76, 71, 89, 22, -49, -34, -29}; - IntegerPolynomial poly = IntegerPolynomial.fromBinary(a, 1499, 2048); - byte[] b = poly.toBinary(2048); - // verify that bytes 0..2047 match, ignore non-relevant bits of byte 2048 - assertTrue(Arrays.areEqual(copyOf(a, 2047), copyOf(b, 2047))); - assertEquals((a[a.length - 1] & 1) >> (7 - (1499 * 11) % 8), (b[b.length - 1] & 1) >> (7 - (1499 * 11) % 8)); - } - - public void testFromToBinary3Sves() - { - byte[] a = new byte[]{-112, -78, 19, 15, 99, -65, -56, -90, 44, -93, -109, 104, 40, 90, -84, -21, -124, 51, -33, 4, -51, -106, 33, 86, -76, 42, 41, -17, 47, 79, 81, -29, 15, 116, 101, 120, 116, 32, 116, 111, 32, 101, 110, 99, 114, 121, 112, 116, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; - IntegerPolynomial poly = IntegerPolynomial.fromBinary3Sves(a, 1499); - byte[] b = poly.toBinary3Sves(); - assertTrue(Arrays.areEqual(a, b)); - } - - public void testFromToBinary3Tight() - { - int[] c = new int[]{0, 0, 0, 0, 0, 0, 0, 1, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1, 0, 1, 0, 1, 0, -1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1, -1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 1, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0}; - IntegerPolynomial poly1 = new IntegerPolynomial(c); - IntegerPolynomial poly2 = IntegerPolynomial.fromBinary3Tight(poly1.toBinary3Tight(), c.length); - assertTrue(Arrays.areEqual(poly1.coeffs, poly2.coeffs)); - - IntegerPolynomial poly3 = new IntegerPolynomial(new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, -1, -1, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, -1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0}); - byte[] arr = poly3.toBinary3Tight(); - IntegerPolynomial poly4 = IntegerPolynomial.fromBinary3Tight(arr, 1499); - assertTrue(Arrays.areEqual(poly3.coeffs, poly4.coeffs)); - - IntegerPolynomial poly5 = new IntegerPolynomial(new int[]{0, 0, 0, 1, -1, -1, -1}); - arr = poly5.toBinary3Tight(); - IntegerPolynomial poly6 = IntegerPolynomial.fromBinary3Tight(arr, 7); - assertTrue(Arrays.areEqual(poly5.coeffs, poly6.coeffs)); - - SecureRandom random = new SecureRandom(); - - for (int i = 0; i < 100; i++) - { - IntegerPolynomial poly7 = DenseTernaryPolynomial.generateRandom(157, random); - arr = poly7.toBinary3Tight(); - IntegerPolynomial poly8 = IntegerPolynomial.fromBinary3Tight(arr, 157); - assertTrue(Arrays.areEqual(poly7.coeffs, poly8.coeffs)); - } - } - - public void testResultant() - { - SecureRandom random = new SecureRandom(); - NTRUSigningKeyGenerationParameters params = NTRUSigningKeyGenerationParameters.APR2011_439; - IntegerPolynomial a = DenseTernaryPolynomial.generateRandom(params.N, params.d, params.d, random); - verifyResultant(a, a.resultant()); - - a = new IntegerPolynomial(new int[]{0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 1, -1, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, -1, -1, 0, -1, 1, -1, 0, -1, 0, -1, -1, -1, 0, 0, 0, 1, 1, -1, -1, -1, 0, -1, -1, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 1, 0, 0, 1, 1, -1, 0, 1, -1, 0, 1, 0, 1, 0, -1, -1, 0, 1, 0, -1, 1, 1, 1, 1, 0, 0, -1, -1, 1, 0, 0, -1, -1, 0, -1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, -1, 0, 0, 0, 0, -1, 0, 0, 0, 1, 0, 1, 0, 1, -1, 0, 0, 1, 1, 1, 0, 0, 0, -1, 0, 0, 0, 0, 1, 0, 1, 0, -1, -1, 0, -1, -1, -1, 0, -1, -1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, -1, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, -1, -1, 0, -1, -1, 1, 1, 0, 0, -1, 1, 0, 0, 0, -1, 1, -1, 0, -1, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 1, 1, 0, 0, -1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, -1, 0, 1, 0, -1, -1, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 1, -1, 1, -1, -1, 1, -1, 0, 1, 0, 0, 0, 1, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1, 0, -1, 0, 1, -1, 0, 0, 1, 1, 0, 0, 1, 1, 0, -1, 0, -1, 1, -1, -1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, -1, 0, 0, 1, -1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, -1, -1, 0, 0, -1, 0, 1, 1, -1, 1, -1, 0, 0, 0, 1}); - verifyResultant(a, a.resultant()); - } - - // verifies that res=rho*a mod x^n-1 - private void verifyResultant(IntegerPolynomial a, Resultant r) - { - BigIntPolynomial b = new BigIntPolynomial(a).mult(r.rho); - BigInteger[] bCoeffs = b.getCoeffs(); - - for (int j = 1; j < bCoeffs.length - 1; j++) - { - assertEquals(BigInteger.ZERO, bCoeffs[j]); - } - if (r.res.equals(BigInteger.ZERO)) - { - assertEquals(BigInteger.ZERO, bCoeffs[0].subtract(bCoeffs[bCoeffs.length - 1])); - } - else - { - assertEquals(BigInteger.ZERO, (bCoeffs[0].subtract(bCoeffs[bCoeffs.length - 1]).mod(r.res))); - } - assertEquals(bCoeffs[0].subtract(r.res), bCoeffs[bCoeffs.length - 1].negate()); - } - - public void testResultantMod() - { - int p = 46337; // prime; must be less than sqrt(2^31) or integer overflows will occur - - IntegerPolynomial a = new IntegerPolynomial(new int[]{0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 1, -1, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, -1, -1, 0, -1, 1, -1, 0, -1, 0, -1, -1, -1, 0, 0, 0, 1, 1, -1, -1, -1, 0, -1, -1, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 1, 0, 0, 1, 1, -1, 0, 1, -1, 0, 1, 0, 1, 0, -1, -1, 0, 1, 0, -1, 1, 1, 1, 1, 0, 0, -1, -1, 1, 0, 0, -1, -1, 0, -1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, -1, 0, 0, 0, 0, -1, 0, 0, 0, 1, 0, 1, 0, 1, -1, 0, 0, 1, 1, 1, 0, 0, 0, -1, 0, 0, 0, 0, 1, 0, 1, 0, -1, -1, 0, -1, -1, -1, 0, -1, -1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, -1, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, -1, -1, 0, -1, -1, 1, 1, 0, 0, -1, 1, 0, 0, 0, -1, 1, -1, 0, -1, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 1, 1, 0, 0, -1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, -1, 0, 1, 0, -1, -1, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 1, -1, 1, -1, -1, 1, -1, 0, 1, 0, 0, 0, 1, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1, 0, -1, 0, 1, -1, 0, 0, 1, 1, 0, 0, 1, 1, 0, -1, 0, -1, 1, -1, -1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, -1, 0, 0, 1, -1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, -1, -1, 0, 0, -1, 0, 1, 1, -1, 1, -1, 0, 0, 0, 1}); - verifyResultant(a, a.resultant(p), p); - - SecureRandom random = new SecureRandom(); - - for (int i = 0; i < 10; i++) - { - a = DenseTernaryPolynomial.generateRandom(853, random); - verifyResultant(a, a.resultant(p), p); - } - } - - // verifies that res=rho*a mod x^n-1 mod p - private void verifyResultant(IntegerPolynomial a, Resultant r, int p) - { - BigIntPolynomial b = new BigIntPolynomial(a).mult(r.rho); - b.mod(BigInteger.valueOf(p)); - BigInteger[] bCoeffs = b.getCoeffs(); - - for (int j = 1; j < bCoeffs.length - 1; j++) - { - assertEquals(BigInteger.ZERO, bCoeffs[j]); - } - if (r.res.equals(BigInteger.ZERO)) - { - assertEquals(BigInteger.ZERO, bCoeffs[0].subtract(bCoeffs[bCoeffs.length - 1])); - } - else - { - assertEquals(BigInteger.ZERO, (bCoeffs[0].subtract(bCoeffs[bCoeffs.length - 1]).subtract(r.res).mod(BigInteger.valueOf(p)))); - } - assertEquals(BigInteger.ZERO, bCoeffs[0].subtract(r.res).subtract(bCoeffs[bCoeffs.length - 1].negate()).mod(BigInteger.valueOf(p))); - } - - private byte[] copyOf(byte[] src, int length) - { - byte[] tmp = new byte[length]; - System.arraycopy(src, 0, tmp, 0, tmp.length); - return tmp; - } -}
\ No newline at end of file diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/LongPolynomial2Test.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/LongPolynomial2Test.java deleted file mode 100644 index c842064..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/LongPolynomial2Test.java +++ /dev/null @@ -1,60 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial.test; - -import java.util.Random; - -import junit.framework.TestCase; -import org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial; -import org.bouncycastle.pqc.math.ntru.polynomial.LongPolynomial2; -import org.bouncycastle.util.Arrays; - -public class LongPolynomial2Test - extends TestCase -{ - public void testMult() - { - IntegerPolynomial i1 = new IntegerPolynomial(new int[]{1368, 2047, 672, 871, 1662, 1352, 1099, 1608}); - IntegerPolynomial i2 = new IntegerPolynomial(new int[]{1729, 1924, 806, 179, 1530, 1381, 1695, 60}); - LongPolynomial2 a = new LongPolynomial2(i1); - LongPolynomial2 b = new LongPolynomial2(i2); - IntegerPolynomial c1 = i1.mult(i2, 2048); - IntegerPolynomial c2 = a.mult(b).toIntegerPolynomial(); - assertTrue(Arrays.areEqual(c1.coeffs, c2.coeffs)); - - // test 10 random polynomials - Random rng = new Random(); - for (int i = 0; i < 10; i++) - { - int N = 2 + rng.nextInt(2000); - i1 = PolynomialGenerator.generateRandom(N, 2048); - i2 = PolynomialGenerator.generateRandom(N, 2048); - a = new LongPolynomial2(i1); - b = new LongPolynomial2(i2); - c1 = i1.mult(i2); - c1.modPositive(2048); - c2 = a.mult(b).toIntegerPolynomial(); - assertTrue(Arrays.areEqual(c1.coeffs, c2.coeffs)); - } - } - - public void testSubAnd() - { - IntegerPolynomial i1 = new IntegerPolynomial(new int[]{1368, 2047, 672, 871, 1662, 1352, 1099, 1608}); - IntegerPolynomial i2 = new IntegerPolynomial(new int[]{1729, 1924, 806, 179, 1530, 1381, 1695, 60}); - LongPolynomial2 a = new LongPolynomial2(i1); - LongPolynomial2 b = new LongPolynomial2(i2); - a.subAnd(b, 2047); - i1.sub(i2); - i1.modPositive(2048); - assertTrue(Arrays.areEqual(a.toIntegerPolynomial().coeffs, i1.coeffs)); - } - - public void testMult2And() - { - IntegerPolynomial i1 = new IntegerPolynomial(new int[]{1368, 2047, 672, 871, 1662, 1352, 1099, 1608}); - LongPolynomial2 i2 = new LongPolynomial2(i1); - i2.mult2And(2047); - i1.mult(2); - i1.modPositive(2048); - assertTrue(Arrays.areEqual(i1.coeffs, i2.toIntegerPolynomial().coeffs)); - } -}
\ No newline at end of file diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/LongPolynomial5Test.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/LongPolynomial5Test.java deleted file mode 100644 index cf91ac2..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/LongPolynomial5Test.java +++ /dev/null @@ -1,62 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial.test; - -import java.security.SecureRandom; - -import junit.framework.TestCase; -import org.bouncycastle.pqc.math.ntru.polynomial.DenseTernaryPolynomial; -import org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial; -import org.bouncycastle.pqc.math.ntru.polynomial.LongPolynomial5; -import org.bouncycastle.util.Arrays; - -public class LongPolynomial5Test - extends TestCase -{ - public void testMult() - { - testMult(new int[]{2}, new int[]{-1}); - testMult(new int[]{2, 0}, new int[]{-1, 0}); - testMult(new int[]{2, 0, 3}, new int[]{-1, 0, 1}); - testMult(new int[]{2, 0, 3, 1}, new int[]{-1, 0, 1, 1}); - testMult(new int[]{2, 0, 3, 1, 2}, new int[]{-1, 0, 1, 1, 0}); - testMult(new int[]{2, 0, 3, 1, 1, 5}, new int[]{1, -1, 1, 1, 0, 1}); - testMult(new int[]{2, 0, 3, 1, 1, 5, 1, 4}, new int[]{1, 0, 1, 1, -1, 1, 0, -1}); - testMult(new int[]{1368, 2047, 672, 871, 1662, 1352, 1099, 1608}, new int[]{1, 0, 1, 1, -1, 1, 0, -1}); - - // test random polynomials - SecureRandom rng = new SecureRandom(); - for (int i = 0; i < 10; i++) - { - int[] coeffs1 = new int[rng.nextInt(2000) + 1]; - int[] coeffs2 = DenseTernaryPolynomial.generateRandom(coeffs1.length, rng).coeffs; - testMult(coeffs1, coeffs2); - } - } - - private void testMult(int[] coeffs1, int[] coeffs2) - { - IntegerPolynomial i1 = new IntegerPolynomial(coeffs1); - IntegerPolynomial i2 = new IntegerPolynomial(coeffs2); - - LongPolynomial5 a = new LongPolynomial5(i1); - DenseTernaryPolynomial b = new DenseTernaryPolynomial(i2); - IntegerPolynomial c1 = i1.mult(i2, 2048); - IntegerPolynomial c2 = a.mult(b).toIntegerPolynomial(); - assertEqualsMod(c1.coeffs, c2.coeffs, 2048); - } - - private void assertEqualsMod(int[] arr1, int[] arr2, int m) - { - assertEquals(arr1.length, arr2.length); - for (int i = 0; i < arr1.length; i++) - { - assertEquals((arr1[i] + m) % m, (arr2[i] + m) % m); - } - } - - public void testToIntegerPolynomial() - { - int[] coeffs = new int[]{2, 0, 3, 1, 1, 5, 1, 4}; - LongPolynomial5 p = new LongPolynomial5(new IntegerPolynomial(coeffs)); - assertTrue(Arrays.areEqual(coeffs, p.toIntegerPolynomial().coeffs)); - } -}
\ No newline at end of file diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/PolynomialGenerator.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/PolynomialGenerator.java deleted file mode 100644 index 8f931d7..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/PolynomialGenerator.java +++ /dev/null @@ -1,27 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial.test; - -import java.util.Random; - -import org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial; - -public class PolynomialGenerator -{ - /** - * Creates a random polynomial with <code>N</code> coefficients - * between <code>0</code> and <code>q-1</code>. - * - * @param N length of the polynomial - * @param q coefficients will all be below this number - * @return a random polynomial - */ - public static IntegerPolynomial generateRandom(int N, int q) - { - Random rng = new Random(); - int[] coeffs = new int[N]; - for (int i = 0; i < N; i++) - { - coeffs[i] = rng.nextInt(q); - } - return new IntegerPolynomial(coeffs); - } -}
\ No newline at end of file diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/ProductFormPolynomialTest.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/ProductFormPolynomialTest.java deleted file mode 100644 index 9fbbb98..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/ProductFormPolynomialTest.java +++ /dev/null @@ -1,47 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial.test; - -import java.security.SecureRandom; - -import junit.framework.TestCase; -import org.bouncycastle.pqc.crypto.ntru.NTRUEncryptionKeyGenerationParameters; -import org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial; -import org.bouncycastle.pqc.math.ntru.polynomial.ProductFormPolynomial; - -public class ProductFormPolynomialTest - extends TestCase -{ - private NTRUEncryptionKeyGenerationParameters params; - private int N; - private int df1; - private int df2; - private int df3; - private int q; - - public void setUp() - { - params = NTRUEncryptionKeyGenerationParameters.APR2011_439_FAST; - N = params.N; - df1 = params.df1; - df2 = params.df2; - df3 = params.df3; - q = params.q; - } - - public void testFromToBinary() - throws Exception - { - ProductFormPolynomial p1 = ProductFormPolynomial.generateRandom(N, df1, df2, df3, df3 - 1, new SecureRandom()); - byte[] bin1 = p1.toBinary(); - ProductFormPolynomial p2 = ProductFormPolynomial.fromBinary(bin1, N, df1, df2, df3, df3 - 1); - assertEquals(p1, p2); - } - - public void testMult() - { - ProductFormPolynomial p1 = ProductFormPolynomial.generateRandom(N, df1, df2, df3, df3 - 1, new SecureRandom()); - IntegerPolynomial p2 = PolynomialGenerator.generateRandom(N, q); - IntegerPolynomial p3 = p1.mult(p2); - IntegerPolynomial p4 = p1.toIntegerPolynomial().mult(p2); - assertEquals(p3, p4); - } -}
\ No newline at end of file diff --git a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/SparseTernaryPolynomialTest.java b/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/SparseTernaryPolynomialTest.java deleted file mode 100644 index 3d434c6..0000000 --- a/bcprov/src/main/java/org/bouncycastle/pqc/math/ntru/polynomial/test/SparseTernaryPolynomialTest.java +++ /dev/null @@ -1,45 +0,0 @@ -package org.bouncycastle.pqc.math.ntru.polynomial.test; - -import java.io.ByteArrayInputStream; -import java.io.IOException; -import java.security.SecureRandom; - -import junit.framework.TestCase; -import org.bouncycastle.pqc.math.ntru.polynomial.BigIntPolynomial; -import org.bouncycastle.pqc.math.ntru.polynomial.DenseTernaryPolynomial; -import org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial; -import org.bouncycastle.pqc.math.ntru.polynomial.SparseTernaryPolynomial; - -public class SparseTernaryPolynomialTest - extends TestCase -{ - - /** - * tests mult(IntegerPolynomial) and mult(BigIntPolynomial) - */ - public void testMult() - { - SecureRandom random = new SecureRandom(); - SparseTernaryPolynomial p1 = SparseTernaryPolynomial.generateRandom(1000, 500, 500, random); - IntegerPolynomial p2 = DenseTernaryPolynomial.generateRandom(1000, random); - - IntegerPolynomial prod1 = p1.mult(p2); - IntegerPolynomial prod2 = p1.mult(p2); - assertEquals(prod1, prod2); - - BigIntPolynomial p3 = new BigIntPolynomial(p2); - BigIntPolynomial prod3 = p1.mult(p3); - - assertEquals(new BigIntPolynomial(prod1), prod3); - } - - public void testFromToBinary() - throws IOException - { - SecureRandom random = new SecureRandom(); - SparseTernaryPolynomial poly1 = SparseTernaryPolynomial.generateRandom(1000, 100, 101, random); - ByteArrayInputStream poly1Stream = new ByteArrayInputStream(poly1.toBinary()); - SparseTernaryPolynomial poly2 = SparseTernaryPolynomial.fromBinary(poly1Stream, 1000, 100, 101); - assertEquals(poly1, poly2); - } -}
\ No newline at end of file |