133 lines
4.5 KiB
Java
133 lines
4.5 KiB
Java
import java.math.BigInteger;
|
|
import java.util.ArrayList;
|
|
import java.util.Arrays;
|
|
import java.util.List;
|
|
|
|
public class CyclotomicPolynomials {
|
|
|
|
public static void main(String[] args) {
|
|
System.out.println("Task 1: Cyclotomic polynomials for n <= 30:");
|
|
for ( int cpIndex = 1; cpIndex <= 30; cpIndex++ ) {
|
|
System.out.println("CP[" + cpIndex + "] = " + toString(cyclotomicPolynomial(cpIndex)));
|
|
}
|
|
|
|
System.out.println();
|
|
System.out.println("Task 2: Smallest cyclotomic polynomial with n or -n as a coefficient:");
|
|
System.out.println("CP[1] has a coefficient with magnitude 1");
|
|
int cpIndex = 2;
|
|
for ( int coefficient = 2; coefficient <= 10; coefficient++ ) {
|
|
while ( BigInteger.valueOf(cpIndex).isProbablePrime(PRIME_CERTAINTY)
|
|
|| ! hasHeight(cyclotomicPolynomial(cpIndex), coefficient) ) {
|
|
cpIndex += 1;
|
|
}
|
|
System.out.println("CP[" + cpIndex + "] has a coefficient with magnitude " + coefficient);
|
|
}
|
|
}
|
|
|
|
// Return the Cyclotomic Polynomial of order 'cpIndex' as an array of coefficients,
|
|
// where, for example, the polynomial 3x^2 - 1 is represented by the array [3, 0, -1].
|
|
private static int[] cyclotomicPolynomial(int cpIndex) {
|
|
int[] polynomial = new int[] { 1, -1 };
|
|
if ( cpIndex == 1 ) {
|
|
return polynomial;
|
|
}
|
|
|
|
if ( BigInteger.valueOf(cpIndex).isProbablePrime(PRIME_CERTAINTY) ) {
|
|
int[] result = new int[cpIndex];
|
|
Arrays.fill(result, 1);
|
|
return result;
|
|
}
|
|
|
|
List<Integer> primes = distinctPrimeFactors(cpIndex);
|
|
int product = 1;
|
|
for ( int prime : primes ) {
|
|
int[] numerator = substituteExponent(polynomial, prime);
|
|
polynomial = exactDivision(numerator, polynomial);
|
|
product *= prime;
|
|
}
|
|
|
|
polynomial = substituteExponent(polynomial, cpIndex / product);
|
|
return polynomial;
|
|
}
|
|
|
|
// Return the Cyclotomic Polynomial obtained from 'polynomial' by replacing x with x^'exponent'.
|
|
private static int[] substituteExponent(int[] polynomial, int exponent) {
|
|
int[] result = new int[exponent * ( polynomial.length - 1 ) + 1];
|
|
for ( int i = polynomial.length - 1; i >= 0; i-- ) {
|
|
result[i * exponent] = polynomial[i];
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
// Return the Cyclotomic Polynomial equal to 'dividend' / 'divisor'. The division is always exact.
|
|
private static int[] exactDivision(int[] dividend, int[] divisor) {
|
|
int[] result = Arrays.copyOf(dividend, dividend.length);
|
|
for ( int i = 0; i < dividend.length - divisor.length + 1; i++ ) {
|
|
if ( result[i] != 0 ) {
|
|
for ( int j = 1; j < divisor.length; j ++ ) {
|
|
result[i + j] += -divisor[j] * result[i];
|
|
}
|
|
}
|
|
}
|
|
|
|
result = Arrays.copyOf(result, result.length - divisor.length + 1);
|
|
return result;
|
|
}
|
|
|
|
// Return whether 'polynomial' has a coefficient of equal magnitude to 'coefficient'.
|
|
private static boolean hasHeight(int[] polynomial, int coefficient) {
|
|
for ( int i = 0; i <= ( polynomial.length + 1 ) / 2; i++ ) {
|
|
if ( Math.abs(polynomial[i]) == coefficient ) {
|
|
return true;
|
|
}
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
// Return a string representation of 'polynomial'.
|
|
private static String toString(int[] polynomial) {
|
|
StringBuilder text = new StringBuilder();
|
|
for ( int i = 0; i < polynomial.length; i++ ) {
|
|
if ( polynomial[i] == 0 ) {
|
|
continue;
|
|
}
|
|
|
|
text.append(( polynomial[i] < 0 ) ? ( ( i == 0 ) ? "-" : " - " ) : ( ( i == 0 ) ? "" : " + " ));
|
|
|
|
final int exponent = polynomial.length - 1 - i;
|
|
if ( exponent > 0 && Math.abs(polynomial[i]) > 1 ) {
|
|
text.append(Math.abs(polynomial[i]));
|
|
}
|
|
|
|
text.append(( exponent > 1 ) ?
|
|
( "x^" + String.valueOf(exponent) ) : ( ( exponent == 1 ) ? "x" : Math.abs(polynomial[i]) ));
|
|
}
|
|
|
|
return text.toString();
|
|
}
|
|
|
|
// Return a list of the distinct prime factors of 'number'.
|
|
private static List<Integer> distinctPrimeFactors(int number) {
|
|
List<Integer> primeFactors = new ArrayList<Integer>();
|
|
for ( int divisor = 2; divisor * divisor <= number; divisor++ ) {
|
|
if ( number % divisor == 0 ) {
|
|
primeFactors.add(divisor);
|
|
}
|
|
while ( number % divisor == 0 ) {
|
|
number = number / divisor;
|
|
}
|
|
}
|
|
|
|
if ( number > 1 ) {
|
|
primeFactors.add(number);
|
|
}
|
|
|
|
return primeFactors;
|
|
}
|
|
|
|
private static final int PRIME_CERTAINTY = 15;
|
|
|
|
}
|