@Test public void testAutomaticConvolution() { BigInteger[] actual = BigNumberTheoreticTransform.circularConvolve( bigintArray(4, 1, 4, 2, 1, 3, 5, 6), bigintArray(6, 1, 8, 0, 3, 3, 9, 8)); BigInteger[] expect = bigintArray(123, 120, 106, 92, 139, 144, 140, 124); assertArrayEquals(expect, actual); }
public static BigInteger[] circularConvolve(BigInteger[] vec0, BigInteger[] vec1) { if (vec0.length == 0 || vec0.length != vec1.length) throw new IllegalArgumentException(); BigInteger maxval = Collections.max(Arrays.asList(vec0)); maxval = Collections.max(Arrays.asList(vec1)).max(maxval); BigInteger minmod = maxval.pow(2).multiply(BigInteger.valueOf(vec0.length)).add(ONE); BigInteger mod = findModulus(vec0.length, minmod); BigInteger root = findPrimitiveRoot(BigInteger.valueOf(vec0.length), mod.subtract(ONE), mod); BigInteger[] temp0 = transform(vec0, root, mod); BigInteger[] temp1 = transform(vec1, root, mod); BigInteger[] temp2 = new BigInteger[temp0.length]; for (int i = 0; i < temp0.length; i++) temp2[i] = temp0[i].multiply(temp1[i]).mod(mod); return inverseTransform(temp2, root, mod); }
BigNumberTheoreticTransform { public static BigInteger[] circularConvolve(BigInteger[] vec0, BigInteger[] vec1) { if (vec0.length == 0 || vec0.length != vec1.length) throw new IllegalArgumentException(); BigInteger maxval = Collections.max(Arrays.asList(vec0)); maxval = Collections.max(Arrays.asList(vec1)).max(maxval); BigInteger minmod = maxval.pow(2).multiply(BigInteger.valueOf(vec0.length)).add(ONE); BigInteger mod = findModulus(vec0.length, minmod); BigInteger root = findPrimitiveRoot(BigInteger.valueOf(vec0.length), mod.subtract(ONE), mod); BigInteger[] temp0 = transform(vec0, root, mod); BigInteger[] temp1 = transform(vec1, root, mod); BigInteger[] temp2 = new BigInteger[temp0.length]; for (int i = 0; i < temp0.length; i++) temp2[i] = temp0[i].multiply(temp1[i]).mod(mod); return inverseTransform(temp2, root, mod); } }
BigNumberTheoreticTransform { public static BigInteger[] circularConvolve(BigInteger[] vec0, BigInteger[] vec1) { if (vec0.length == 0 || vec0.length != vec1.length) throw new IllegalArgumentException(); BigInteger maxval = Collections.max(Arrays.asList(vec0)); maxval = Collections.max(Arrays.asList(vec1)).max(maxval); BigInteger minmod = maxval.pow(2).multiply(BigInteger.valueOf(vec0.length)).add(ONE); BigInteger mod = findModulus(vec0.length, minmod); BigInteger root = findPrimitiveRoot(BigInteger.valueOf(vec0.length), mod.subtract(ONE), mod); BigInteger[] temp0 = transform(vec0, root, mod); BigInteger[] temp1 = transform(vec1, root, mod); BigInteger[] temp2 = new BigInteger[temp0.length]; for (int i = 0; i < temp0.length; i++) temp2[i] = temp0[i].multiply(temp1[i]).mod(mod); return inverseTransform(temp2, root, mod); }  }
BigNumberTheoreticTransform { public static BigInteger[] circularConvolve(BigInteger[] vec0, BigInteger[] vec1) { if (vec0.length == 0 || vec0.length != vec1.length) throw new IllegalArgumentException(); BigInteger maxval = Collections.max(Arrays.asList(vec0)); maxval = Collections.max(Arrays.asList(vec1)).max(maxval); BigInteger minmod = maxval.pow(2).multiply(BigInteger.valueOf(vec0.length)).add(ONE); BigInteger mod = findModulus(vec0.length, minmod); BigInteger root = findPrimitiveRoot(BigInteger.valueOf(vec0.length), mod.subtract(ONE), mod); BigInteger[] temp0 = transform(vec0, root, mod); BigInteger[] temp1 = transform(vec1, root, mod); BigInteger[] temp2 = new BigInteger[temp0.length]; for (int i = 0; i < temp0.length; i++) temp2[i] = temp0[i].multiply(temp1[i]).mod(mod); return inverseTransform(temp2, root, mod); }  static BigInteger[] transform(BigInteger[] invec, BigInteger root, BigInteger mod); static BigInteger[] inverseTransform(BigInteger[] invec, BigInteger root, BigInteger mod); static void transformRadix2(BigInteger[] vector, BigInteger root, BigInteger mod); static BigInteger[] circularConvolve(BigInteger[] vec0, BigInteger[] vec1); static BigInteger findModulus(int vecLen, BigInteger minimum); static BigInteger findGenerator(BigInteger totient, BigInteger mod); static BigInteger findPrimitiveRoot(BigInteger degree, BigInteger totient, BigInteger mod); static boolean isGenerator(BigInteger val, BigInteger totient, BigInteger mod); static boolean isPrimitiveRoot(BigInteger val, BigInteger degree, BigInteger mod); static List<BigInteger> uniquePrimeFactors(BigInteger n); static boolean isPrime(BigInteger n); static BigInteger sqrt(BigInteger x); }
BigNumberTheoreticTransform { public static BigInteger[] circularConvolve(BigInteger[] vec0, BigInteger[] vec1) { if (vec0.length == 0 || vec0.length != vec1.length) throw new IllegalArgumentException(); BigInteger maxval = Collections.max(Arrays.asList(vec0)); maxval = Collections.max(Arrays.asList(vec1)).max(maxval); BigInteger minmod = maxval.pow(2).multiply(BigInteger.valueOf(vec0.length)).add(ONE); BigInteger mod = findModulus(vec0.length, minmod); BigInteger root = findPrimitiveRoot(BigInteger.valueOf(vec0.length), mod.subtract(ONE), mod); BigInteger[] temp0 = transform(vec0, root, mod); BigInteger[] temp1 = transform(vec1, root, mod); BigInteger[] temp2 = new BigInteger[temp0.length]; for (int i = 0; i < temp0.length; i++) temp2[i] = temp0[i].multiply(temp1[i]).mod(mod); return inverseTransform(temp2, root, mod); }  static BigInteger[] transform(BigInteger[] invec, BigInteger root, BigInteger mod); static BigInteger[] inverseTransform(BigInteger[] invec, BigInteger root, BigInteger mod); static void transformRadix2(BigInteger[] vector, BigInteger root, BigInteger mod); static BigInteger[] circularConvolve(BigInteger[] vec0, BigInteger[] vec1); static BigInteger findModulus(int vecLen, BigInteger minimum); static BigInteger findGenerator(BigInteger totient, BigInteger mod); static BigInteger findPrimitiveRoot(BigInteger degree, BigInteger totient, BigInteger mod); static boolean isGenerator(BigInteger val, BigInteger totient, BigInteger mod); static boolean isPrimitiveRoot(BigInteger val, BigInteger degree, BigInteger mod); static List<BigInteger> uniquePrimeFactors(BigInteger n); static boolean isPrime(BigInteger n); static BigInteger sqrt(BigInteger x);  }