579 lines
21 KiB
Java
579 lines
21 KiB
Java
|
package org.bouncycastle.pqc.math.linearalgebra;
|
||
|
|
|
||
|
|
import com.google.common.primitives.UnsignedBytes;
|
||
|
|
import java.security.SecureRandom;
|
||
|
|
|
||
|
|
/* loaded from: classes6.dex */
|
||
|
|
public class PolynomialGF2mSmallM {
|
||
|
|
public static final char RANDOM_IRREDUCIBLE_POLYNOMIAL = 'I';
|
||
|
|
private int[] coefficients;
|
||
|
|
private int degree;
|
||
|
|
private GF2mField field;
|
||
|
|
|
||
|
|
public String toString() {
|
||
|
|
StringBuilder sb = new StringBuilder(" Polynomial over ");
|
||
|
|
sb.append(this.field.toString());
|
||
|
|
sb.append(": \n");
|
||
|
|
String obj = sb.toString();
|
||
|
|
for (int i = 0; i < this.coefficients.length; i++) {
|
||
|
|
StringBuilder sb2 = new StringBuilder();
|
||
|
|
sb2.append(obj);
|
||
|
|
sb2.append(this.field.elementToStr(this.coefficients[i]));
|
||
|
|
sb2.append("Y^");
|
||
|
|
sb2.append(i);
|
||
|
|
sb2.append("+");
|
||
|
|
obj = sb2.toString();
|
||
|
|
}
|
||
|
|
StringBuilder sb3 = new StringBuilder();
|
||
|
|
sb3.append(obj);
|
||
|
|
sb3.append(";");
|
||
|
|
return sb3.toString();
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM multiply(PolynomialGF2mSmallM polynomialGF2mSmallM) {
|
||
|
|
return new PolynomialGF2mSmallM(this.field, multiply(this.coefficients, polynomialGF2mSmallM.coefficients));
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM multWithMonomial(int i) {
|
||
|
|
return new PolynomialGF2mSmallM(this.field, multWithMonomial(this.coefficients, i));
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM multWithElement(int i) {
|
||
|
|
if (!this.field.isElementOfThisField(i)) {
|
||
|
|
throw new ArithmeticException("Not an element of the finite field this polynomial is defined over.");
|
||
|
|
}
|
||
|
|
return new PolynomialGF2mSmallM(this.field, multWithElement(this.coefficients, i));
|
||
|
|
}
|
||
|
|
|
||
|
|
public void multThisWithElement(int i) {
|
||
|
|
if (!this.field.isElementOfThisField(i)) {
|
||
|
|
throw new ArithmeticException("Not an element of the finite field this polynomial is defined over.");
|
||
|
|
}
|
||
|
|
this.coefficients = multWithElement(this.coefficients, i);
|
||
|
|
computeDegree();
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM modSquareRootMatrix(PolynomialGF2mSmallM[] polynomialGF2mSmallMArr) {
|
||
|
|
int length = polynomialGF2mSmallMArr.length;
|
||
|
|
int[] iArr = new int[length];
|
||
|
|
for (int i = 0; i < length; i++) {
|
||
|
|
for (int i2 = 0; i2 < length; i2++) {
|
||
|
|
int[] iArr2 = polynomialGF2mSmallMArr[i2].coefficients;
|
||
|
|
if (i < iArr2.length) {
|
||
|
|
int[] iArr3 = this.coefficients;
|
||
|
|
if (i2 < iArr3.length) {
|
||
|
|
iArr[i] = this.field.add(iArr[i], this.field.mult(iArr2[i], iArr3[i2]));
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
for (int i3 = 0; i3 < length; i3++) {
|
||
|
|
iArr[i3] = this.field.sqRoot(iArr[i3]);
|
||
|
|
}
|
||
|
|
return new PolynomialGF2mSmallM(this.field, iArr);
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM modSquareRoot(PolynomialGF2mSmallM polynomialGF2mSmallM) {
|
||
|
|
int[] clone = IntUtils.clone(this.coefficients);
|
||
|
|
int[] modMultiply = modMultiply(clone, clone, polynomialGF2mSmallM.coefficients);
|
||
|
|
while (!isEqual(modMultiply, this.coefficients)) {
|
||
|
|
clone = normalForm(modMultiply);
|
||
|
|
modMultiply = modMultiply(clone, clone, polynomialGF2mSmallM.coefficients);
|
||
|
|
}
|
||
|
|
return new PolynomialGF2mSmallM(this.field, clone);
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM modSquareMatrix(PolynomialGF2mSmallM[] polynomialGF2mSmallMArr) {
|
||
|
|
int length = polynomialGF2mSmallMArr.length;
|
||
|
|
int[] iArr = new int[length];
|
||
|
|
int[] iArr2 = new int[length];
|
||
|
|
int i = 0;
|
||
|
|
while (true) {
|
||
|
|
int[] iArr3 = this.coefficients;
|
||
|
|
if (i >= iArr3.length) {
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
GF2mField gF2mField = this.field;
|
||
|
|
int i2 = iArr3[i];
|
||
|
|
iArr2[i] = gF2mField.mult(i2, i2);
|
||
|
|
i++;
|
||
|
|
}
|
||
|
|
for (int i3 = 0; i3 < length; i3++) {
|
||
|
|
for (int i4 = 0; i4 < length; i4++) {
|
||
|
|
int[] iArr4 = polynomialGF2mSmallMArr[i4].coefficients;
|
||
|
|
if (i3 < iArr4.length) {
|
||
|
|
iArr[i3] = this.field.add(iArr[i3], this.field.mult(iArr4[i3], iArr2[i4]));
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return new PolynomialGF2mSmallM(this.field, iArr);
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM[] modPolynomialToFracton(PolynomialGF2mSmallM polynomialGF2mSmallM) {
|
||
|
|
int i = polynomialGF2mSmallM.degree;
|
||
|
|
int[] normalForm = normalForm(polynomialGF2mSmallM.coefficients);
|
||
|
|
int[] iArr = normalForm;
|
||
|
|
int[] mod = mod(this.coefficients, polynomialGF2mSmallM.coefficients);
|
||
|
|
int[] iArr2 = {0};
|
||
|
|
int[] iArr3 = {1};
|
||
|
|
while (computeDegree(mod) > (i >> 1)) {
|
||
|
|
int[][] div = div(iArr, mod);
|
||
|
|
int[] iArr4 = div[1];
|
||
|
|
int[] add = add(iArr2, modMultiply(div[0], iArr3, polynomialGF2mSmallM.coefficients));
|
||
|
|
iArr2 = iArr3;
|
||
|
|
iArr3 = add;
|
||
|
|
iArr = mod;
|
||
|
|
mod = iArr4;
|
||
|
|
}
|
||
|
|
return new PolynomialGF2mSmallM[]{new PolynomialGF2mSmallM(this.field, mod), new PolynomialGF2mSmallM(this.field, iArr3)};
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM modMultiply(PolynomialGF2mSmallM polynomialGF2mSmallM, PolynomialGF2mSmallM polynomialGF2mSmallM2) {
|
||
|
|
return new PolynomialGF2mSmallM(this.field, modMultiply(this.coefficients, polynomialGF2mSmallM.coefficients, polynomialGF2mSmallM2.coefficients));
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM modInverse(PolynomialGF2mSmallM polynomialGF2mSmallM) {
|
||
|
|
return new PolynomialGF2mSmallM(this.field, modDiv(new int[]{1}, this.coefficients, polynomialGF2mSmallM.coefficients));
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM modDiv(PolynomialGF2mSmallM polynomialGF2mSmallM, PolynomialGF2mSmallM polynomialGF2mSmallM2) {
|
||
|
|
return new PolynomialGF2mSmallM(this.field, modDiv(this.coefficients, polynomialGF2mSmallM.coefficients, polynomialGF2mSmallM2.coefficients));
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM mod(PolynomialGF2mSmallM polynomialGF2mSmallM) {
|
||
|
|
return new PolynomialGF2mSmallM(this.field, mod(this.coefficients, polynomialGF2mSmallM.coefficients));
|
||
|
|
}
|
||
|
|
|
||
|
|
public int hashCode() {
|
||
|
|
int hashCode = this.field.hashCode();
|
||
|
|
int i = 0;
|
||
|
|
while (true) {
|
||
|
|
int[] iArr = this.coefficients;
|
||
|
|
if (i >= iArr.length) {
|
||
|
|
return hashCode;
|
||
|
|
}
|
||
|
|
hashCode = (hashCode * 31) + iArr[i];
|
||
|
|
i++;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
public int getHeadCoefficient() {
|
||
|
|
int i = this.degree;
|
||
|
|
if (i == -1) {
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
return this.coefficients[i];
|
||
|
|
}
|
||
|
|
|
||
|
|
public byte[] getEncoded() {
|
||
|
|
int i = 8;
|
||
|
|
int i2 = 1;
|
||
|
|
while (this.field.getDegree() > i) {
|
||
|
|
i2++;
|
||
|
|
i += 8;
|
||
|
|
}
|
||
|
|
byte[] bArr = new byte[this.coefficients.length * i2];
|
||
|
|
int i3 = 0;
|
||
|
|
for (int i4 = 0; i4 < this.coefficients.length; i4++) {
|
||
|
|
int i5 = 0;
|
||
|
|
while (i5 < i) {
|
||
|
|
bArr[i3] = (byte) (this.coefficients[i4] >>> i5);
|
||
|
|
i5 += 8;
|
||
|
|
i3++;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return bArr;
|
||
|
|
}
|
||
|
|
|
||
|
|
public int getDegree() {
|
||
|
|
int[] iArr = this.coefficients;
|
||
|
|
int length = iArr.length - 1;
|
||
|
|
if (iArr[length] == 0) {
|
||
|
|
return -1;
|
||
|
|
}
|
||
|
|
return length;
|
||
|
|
}
|
||
|
|
|
||
|
|
public int getCoefficient(int i) {
|
||
|
|
if (i < 0 || i > this.degree) {
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
return this.coefficients[i];
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM gcd(PolynomialGF2mSmallM polynomialGF2mSmallM) {
|
||
|
|
return new PolynomialGF2mSmallM(this.field, gcd(this.coefficients, polynomialGF2mSmallM.coefficients));
|
||
|
|
}
|
||
|
|
|
||
|
|
public int evaluateAt(int i) {
|
||
|
|
int[] iArr = this.coefficients;
|
||
|
|
int i2 = this.degree;
|
||
|
|
int i3 = iArr[i2];
|
||
|
|
while (true) {
|
||
|
|
i2--;
|
||
|
|
if (i2 < 0) {
|
||
|
|
return i3;
|
||
|
|
}
|
||
|
|
i3 = this.field.mult(i3, i) ^ this.coefficients[i2];
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
public boolean equals(Object obj) {
|
||
|
|
if (obj == null || !(obj instanceof PolynomialGF2mSmallM)) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
PolynomialGF2mSmallM polynomialGF2mSmallM = (PolynomialGF2mSmallM) obj;
|
||
|
|
return this.field.equals(polynomialGF2mSmallM.field) && this.degree == polynomialGF2mSmallM.degree && isEqual(this.coefficients, polynomialGF2mSmallM.coefficients);
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM[] div(PolynomialGF2mSmallM polynomialGF2mSmallM) {
|
||
|
|
int[][] div = div(this.coefficients, polynomialGF2mSmallM.coefficients);
|
||
|
|
return new PolynomialGF2mSmallM[]{new PolynomialGF2mSmallM(this.field, div[0]), new PolynomialGF2mSmallM(this.field, div[1])};
|
||
|
|
}
|
||
|
|
|
||
|
|
public void addToThis(PolynomialGF2mSmallM polynomialGF2mSmallM) {
|
||
|
|
this.coefficients = add(this.coefficients, polynomialGF2mSmallM.coefficients);
|
||
|
|
computeDegree();
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM addMonomial(int i) {
|
||
|
|
int[] iArr = new int[i + 1];
|
||
|
|
iArr[i] = 1;
|
||
|
|
return new PolynomialGF2mSmallM(this.field, add(this.coefficients, iArr));
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM add(PolynomialGF2mSmallM polynomialGF2mSmallM) {
|
||
|
|
return new PolynomialGF2mSmallM(this.field, add(this.coefficients, polynomialGF2mSmallM.coefficients));
|
||
|
|
}
|
||
|
|
|
||
|
|
private static int[] normalForm(int[] iArr) {
|
||
|
|
int computeDegree = computeDegree(iArr);
|
||
|
|
if (computeDegree == -1) {
|
||
|
|
return new int[1];
|
||
|
|
}
|
||
|
|
int i = computeDegree + 1;
|
||
|
|
if (iArr.length == i) {
|
||
|
|
return IntUtils.clone(iArr);
|
||
|
|
}
|
||
|
|
int[] iArr2 = new int[i];
|
||
|
|
System.arraycopy(iArr, 0, iArr2, 0, i);
|
||
|
|
return iArr2;
|
||
|
|
}
|
||
|
|
|
||
|
|
private int[] multiply(int[] iArr, int[] iArr2) {
|
||
|
|
if (computeDegree(iArr) < computeDegree(iArr2)) {
|
||
|
|
iArr2 = iArr;
|
||
|
|
iArr = iArr2;
|
||
|
|
}
|
||
|
|
int[] normalForm = normalForm(iArr);
|
||
|
|
int[] normalForm2 = normalForm(iArr2);
|
||
|
|
if (normalForm2.length == 1) {
|
||
|
|
return multWithElement(normalForm, normalForm2[0]);
|
||
|
|
}
|
||
|
|
int length = normalForm.length;
|
||
|
|
int length2 = normalForm2.length;
|
||
|
|
int[] iArr3 = new int[(length + length2) - 1];
|
||
|
|
if (length2 != length) {
|
||
|
|
int[] iArr4 = new int[length2];
|
||
|
|
int i = length - length2;
|
||
|
|
int[] iArr5 = new int[i];
|
||
|
|
System.arraycopy(normalForm, 0, iArr4, 0, length2);
|
||
|
|
System.arraycopy(normalForm, length2, iArr5, 0, i);
|
||
|
|
return add(multiply(iArr4, normalForm2), multWithMonomial(multiply(iArr5, normalForm2), length2));
|
||
|
|
}
|
||
|
|
int i2 = (length + 1) >>> 1;
|
||
|
|
int i3 = length - i2;
|
||
|
|
int[] iArr6 = new int[i2];
|
||
|
|
int[] iArr7 = new int[i2];
|
||
|
|
int[] iArr8 = new int[i3];
|
||
|
|
int[] iArr9 = new int[i3];
|
||
|
|
System.arraycopy(normalForm, 0, iArr6, 0, i2);
|
||
|
|
System.arraycopy(normalForm, i2, iArr8, 0, i3);
|
||
|
|
System.arraycopy(normalForm2, 0, iArr7, 0, i2);
|
||
|
|
System.arraycopy(normalForm2, i2, iArr9, 0, i3);
|
||
|
|
int[] add = add(iArr6, iArr8);
|
||
|
|
int[] add2 = add(iArr7, iArr9);
|
||
|
|
int[] multiply = multiply(iArr6, iArr7);
|
||
|
|
int[] multiply2 = multiply(add, add2);
|
||
|
|
int[] multiply3 = multiply(iArr8, iArr9);
|
||
|
|
return add(multWithMonomial(add(add(add(multiply2, multiply), multiply3), multWithMonomial(multiply3, i2)), i2), multiply);
|
||
|
|
}
|
||
|
|
|
||
|
|
private static int[] multWithMonomial(int[] iArr, int i) {
|
||
|
|
int computeDegree = computeDegree(iArr);
|
||
|
|
if (computeDegree == -1) {
|
||
|
|
return new int[1];
|
||
|
|
}
|
||
|
|
int[] iArr2 = new int[computeDegree + i + 1];
|
||
|
|
System.arraycopy(iArr, 0, iArr2, i, computeDegree + 1);
|
||
|
|
return iArr2;
|
||
|
|
}
|
||
|
|
|
||
|
|
private int[] multWithElement(int[] iArr, int i) {
|
||
|
|
int computeDegree = computeDegree(iArr);
|
||
|
|
if (computeDegree == -1 || i == 0) {
|
||
|
|
return new int[1];
|
||
|
|
}
|
||
|
|
if (i == 1) {
|
||
|
|
return IntUtils.clone(iArr);
|
||
|
|
}
|
||
|
|
int[] iArr2 = new int[computeDegree + 1];
|
||
|
|
while (computeDegree >= 0) {
|
||
|
|
iArr2[computeDegree] = this.field.mult(iArr[computeDegree], i);
|
||
|
|
computeDegree--;
|
||
|
|
}
|
||
|
|
return iArr2;
|
||
|
|
}
|
||
|
|
|
||
|
|
private int[] modMultiply(int[] iArr, int[] iArr2, int[] iArr3) {
|
||
|
|
return mod(multiply(iArr, iArr2), iArr3);
|
||
|
|
}
|
||
|
|
|
||
|
|
private int[] modDiv(int[] iArr, int[] iArr2, int[] iArr3) {
|
||
|
|
int[] normalForm = normalForm(iArr3);
|
||
|
|
int[] mod = mod(iArr2, iArr3);
|
||
|
|
int[] iArr4 = {0};
|
||
|
|
int[] mod2 = mod(iArr, iArr3);
|
||
|
|
while (computeDegree(mod) != -1) {
|
||
|
|
int[][] div = div(normalForm, mod);
|
||
|
|
int[] normalForm2 = normalForm(mod);
|
||
|
|
int[] normalForm3 = normalForm(div[1]);
|
||
|
|
int[] add = add(iArr4, modMultiply(div[0], mod2, iArr3));
|
||
|
|
iArr4 = normalForm(mod2);
|
||
|
|
mod2 = normalForm(add);
|
||
|
|
normalForm = normalForm2;
|
||
|
|
mod = normalForm3;
|
||
|
|
}
|
||
|
|
return multWithElement(iArr4, this.field.inverse(headCoefficient(normalForm)));
|
||
|
|
}
|
||
|
|
|
||
|
|
private int[] mod(int[] iArr, int[] iArr2) {
|
||
|
|
int computeDegree = computeDegree(iArr2);
|
||
|
|
if (computeDegree == -1) {
|
||
|
|
throw new ArithmeticException("Division by zero");
|
||
|
|
}
|
||
|
|
int length = iArr.length;
|
||
|
|
int[] iArr3 = new int[length];
|
||
|
|
int inverse = this.field.inverse(headCoefficient(iArr2));
|
||
|
|
System.arraycopy(iArr, 0, iArr3, 0, length);
|
||
|
|
while (computeDegree <= computeDegree(iArr3)) {
|
||
|
|
iArr3 = add(multWithElement(multWithMonomial(iArr2, computeDegree(iArr3) - computeDegree), this.field.mult(headCoefficient(iArr3), inverse)), iArr3);
|
||
|
|
}
|
||
|
|
return iArr3;
|
||
|
|
}
|
||
|
|
|
||
|
|
private boolean isIrreducible(int[] iArr) {
|
||
|
|
if (iArr[0] == 0) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
int computeDegree = computeDegree(iArr);
|
||
|
|
int[] iArr2 = {0, 1};
|
||
|
|
int[] iArr3 = {0, 1};
|
||
|
|
int degree = this.field.getDegree();
|
||
|
|
for (int i = 0; i < (computeDegree >> 1); i++) {
|
||
|
|
for (int i2 = degree - 1; i2 >= 0; i2--) {
|
||
|
|
iArr2 = modMultiply(iArr2, iArr2, iArr);
|
||
|
|
}
|
||
|
|
iArr2 = normalForm(iArr2);
|
||
|
|
if (computeDegree(gcd(add(iArr2, iArr3), iArr)) != 0) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
|
||
|
|
private static boolean isEqual(int[] iArr, int[] iArr2) {
|
||
|
|
int computeDegree = computeDegree(iArr);
|
||
|
|
if (computeDegree != computeDegree(iArr2)) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
for (int i = 0; i <= computeDegree; i++) {
|
||
|
|
if (iArr[i] != iArr2[i]) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
|
||
|
|
private static int headCoefficient(int[] iArr) {
|
||
|
|
int computeDegree = computeDegree(iArr);
|
||
|
|
if (computeDegree == -1) {
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
return iArr[computeDegree];
|
||
|
|
}
|
||
|
|
|
||
|
|
private int[] gcd(int[] iArr, int[] iArr2) {
|
||
|
|
if (computeDegree(iArr) == -1) {
|
||
|
|
return iArr2;
|
||
|
|
}
|
||
|
|
while (computeDegree(iArr2) != -1) {
|
||
|
|
int[] mod = mod(iArr, iArr2);
|
||
|
|
int length = iArr2.length;
|
||
|
|
int[] iArr3 = new int[length];
|
||
|
|
System.arraycopy(iArr2, 0, iArr3, 0, length);
|
||
|
|
int length2 = mod.length;
|
||
|
|
int[] iArr4 = new int[length2];
|
||
|
|
System.arraycopy(mod, 0, iArr4, 0, length2);
|
||
|
|
iArr2 = iArr4;
|
||
|
|
iArr = iArr3;
|
||
|
|
}
|
||
|
|
return multWithElement(iArr, this.field.inverse(headCoefficient(iArr)));
|
||
|
|
}
|
||
|
|
|
||
|
|
private int[][] div(int[] iArr, int[] iArr2) {
|
||
|
|
int computeDegree = computeDegree(iArr2);
|
||
|
|
int computeDegree2 = computeDegree(iArr);
|
||
|
|
if (computeDegree == -1) {
|
||
|
|
throw new ArithmeticException("Division by zero.");
|
||
|
|
}
|
||
|
|
int[][] iArr3 = {new int[1], new int[computeDegree2 + 1]};
|
||
|
|
int inverse = this.field.inverse(headCoefficient(iArr2));
|
||
|
|
iArr3[0][0] = 0;
|
||
|
|
int[] iArr4 = iArr3[1];
|
||
|
|
System.arraycopy(iArr, 0, iArr4, 0, iArr4.length);
|
||
|
|
while (computeDegree <= computeDegree(iArr3[1])) {
|
||
|
|
int[] iArr5 = {this.field.mult(headCoefficient(iArr3[1]), inverse)};
|
||
|
|
int[] multWithElement = multWithElement(iArr2, iArr5[0]);
|
||
|
|
int computeDegree3 = computeDegree(iArr3[1]) - computeDegree;
|
||
|
|
int[] multWithMonomial = multWithMonomial(multWithElement, computeDegree3);
|
||
|
|
iArr3[0] = add(multWithMonomial(iArr5, computeDegree3), iArr3[0]);
|
||
|
|
iArr3[1] = add(multWithMonomial, iArr3[1]);
|
||
|
|
}
|
||
|
|
return iArr3;
|
||
|
|
}
|
||
|
|
|
||
|
|
private int[] createRandomIrreduciblePolynomial(int i, SecureRandom secureRandom) {
|
||
|
|
int[] iArr = new int[i + 1];
|
||
|
|
iArr[i] = 1;
|
||
|
|
iArr[0] = this.field.getRandomNonZeroElement(secureRandom);
|
||
|
|
for (int i2 = 1; i2 < i; i2++) {
|
||
|
|
iArr[i2] = this.field.getRandomElement(secureRandom);
|
||
|
|
}
|
||
|
|
while (!isIrreducible(iArr)) {
|
||
|
|
int nextInt = RandUtils.nextInt(secureRandom, i);
|
||
|
|
if (nextInt == 0) {
|
||
|
|
iArr[0] = this.field.getRandomNonZeroElement(secureRandom);
|
||
|
|
} else {
|
||
|
|
iArr[nextInt] = this.field.getRandomElement(secureRandom);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return iArr;
|
||
|
|
}
|
||
|
|
|
||
|
|
private void computeDegree() {
|
||
|
|
int length = this.coefficients.length;
|
||
|
|
do {
|
||
|
|
length--;
|
||
|
|
this.degree = length;
|
||
|
|
if (length < 0) {
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
} while (this.coefficients[length] == 0);
|
||
|
|
}
|
||
|
|
|
||
|
|
private static int computeDegree(int[] iArr) {
|
||
|
|
int length = iArr.length - 1;
|
||
|
|
while (length >= 0 && iArr[length] == 0) {
|
||
|
|
length--;
|
||
|
|
}
|
||
|
|
return length;
|
||
|
|
}
|
||
|
|
|
||
|
|
private int[] add(int[] iArr, int[] iArr2) {
|
||
|
|
int[] iArr3;
|
||
|
|
if (iArr.length < iArr2.length) {
|
||
|
|
iArr3 = new int[iArr2.length];
|
||
|
|
System.arraycopy(iArr2, 0, iArr3, 0, iArr2.length);
|
||
|
|
} else {
|
||
|
|
iArr3 = new int[iArr.length];
|
||
|
|
System.arraycopy(iArr, 0, iArr3, 0, iArr.length);
|
||
|
|
iArr = iArr2;
|
||
|
|
}
|
||
|
|
for (int length = iArr.length - 1; length >= 0; length--) {
|
||
|
|
iArr3[length] = this.field.add(iArr3[length], iArr[length]);
|
||
|
|
}
|
||
|
|
return iArr3;
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM(PolynomialGF2mSmallM polynomialGF2mSmallM) {
|
||
|
|
this.field = polynomialGF2mSmallM.field;
|
||
|
|
this.degree = polynomialGF2mSmallM.degree;
|
||
|
|
this.coefficients = IntUtils.clone(polynomialGF2mSmallM.coefficients);
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM(GF2mVector gF2mVector) {
|
||
|
|
this(gF2mVector.getField(), gF2mVector.getIntArrayForm());
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM(GF2mField gF2mField, int[] iArr) {
|
||
|
|
this.field = gF2mField;
|
||
|
|
this.coefficients = normalForm(iArr);
|
||
|
|
computeDegree();
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM(GF2mField gF2mField, byte[] bArr) {
|
||
|
|
this.field = gF2mField;
|
||
|
|
int i = 8;
|
||
|
|
int i2 = 1;
|
||
|
|
while (gF2mField.getDegree() > i) {
|
||
|
|
i2++;
|
||
|
|
i += 8;
|
||
|
|
}
|
||
|
|
if (bArr.length % i2 != 0) {
|
||
|
|
throw new IllegalArgumentException(" Error: byte array is not encoded polynomial over given finite field GF2m");
|
||
|
|
}
|
||
|
|
this.coefficients = new int[bArr.length / i2];
|
||
|
|
int i3 = 0;
|
||
|
|
int i4 = 0;
|
||
|
|
while (true) {
|
||
|
|
int[] iArr = this.coefficients;
|
||
|
|
if (i3 >= iArr.length) {
|
||
|
|
if (iArr.length != 1 && iArr[iArr.length - 1] == 0) {
|
||
|
|
throw new IllegalArgumentException(" Error: byte array is not encoded polynomial over given finite field GF2m");
|
||
|
|
}
|
||
|
|
computeDegree();
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
int i5 = 0;
|
||
|
|
while (i5 < i) {
|
||
|
|
int[] iArr2 = this.coefficients;
|
||
|
|
iArr2[i3] = iArr2[i3] ^ ((bArr[i4] & UnsignedBytes.MAX_VALUE) << i5);
|
||
|
|
i5 += 8;
|
||
|
|
i4++;
|
||
|
|
}
|
||
|
|
if (!this.field.isElementOfThisField(this.coefficients[i3])) {
|
||
|
|
throw new IllegalArgumentException(" Error: byte array is not encoded polynomial over given finite field GF2m");
|
||
|
|
}
|
||
|
|
i3++;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM(GF2mField gF2mField, int i, char c, SecureRandom secureRandom) {
|
||
|
|
this.field = gF2mField;
|
||
|
|
if (c == 'I') {
|
||
|
|
this.coefficients = createRandomIrreduciblePolynomial(i, secureRandom);
|
||
|
|
computeDegree();
|
||
|
|
} else {
|
||
|
|
StringBuilder sb = new StringBuilder(" Error: type ");
|
||
|
|
sb.append(c);
|
||
|
|
sb.append(" is not defined for GF2smallmPolynomial");
|
||
|
|
throw new IllegalArgumentException(sb.toString());
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM(GF2mField gF2mField, int i) {
|
||
|
|
this.field = gF2mField;
|
||
|
|
this.degree = i;
|
||
|
|
int[] iArr = new int[i + 1];
|
||
|
|
this.coefficients = iArr;
|
||
|
|
iArr[i] = 1;
|
||
|
|
}
|
||
|
|
|
||
|
|
public PolynomialGF2mSmallM(GF2mField gF2mField) {
|
||
|
|
this.field = gF2mField;
|
||
|
|
this.degree = -1;
|
||
|
|
this.coefficients = new int[1];
|
||
|
|
}
|
||
|
|
}
|