Cyclotomic polynomial: Difference between revisions

</pre>

===Alternative Version===

An alternative example using the algorithm from "Matters Computational" by Jorg Arndt, pages 704 - 705.

It completes the task in less than 2 seconds.

<syntaxhighlight lang="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;

}

</syntaxhighlight>

<pre>

Task 1: Cyclotomic polynomials for n <= 30:

CP[1] = x - 1

CP[2] = x + 1

CP[3] = x^2 + x + 1

CP[4] = x^2 + 1

CP[5] = x^4 + x^3 + x^2 + x + 1

CP[6] = x^2 - x + 1

CP[7] = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1

CP[8] = x^4 + 1

CP[9] = x^6 + x^3 + 1

CP[10] = x^4 - x^3 + x^2 - x + 1

CP[11] = x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1

CP[12] = x^4 - x^2 + 1

CP[13] = x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1

CP[14] = x^6 - x^5 + x^4 - x^3 + x^2 - x + 1

CP[15] = x^8 - x^7 + x^5 - x^4 + x^3 - x + 1

CP[16] = x^8 + 1

CP[17] = x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1

CP[18] = x^6 - x^3 + 1

CP[19] = x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1

CP[20] = x^8 - x^6 + x^4 - x^2 + 1

CP[21] = x^12 - x^11 + x^9 - x^8 + x^6 - x^4 + x^3 - x + 1

CP[22] = x^10 - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1

CP[23] = x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1

CP[24] = x^8 - x^4 + 1

CP[25] = x^20 + x^15 + x^10 + x^5 + 1

CP[26] = x^12 - x^11 + x^10 - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1

CP[27] = x^18 + x^9 + 1

CP[28] = x^12 - x^10 + x^8 - x^6 + x^4 - x^2 + 1

CP[29] = x^28 + x^27 + x^26 + x^25 + x^24 + x^23 + x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1

CP[30] = x^8 + x^7 - x^5 - x^4 - x^3 + x + 1

Task 2: Smallest cyclotomic polynomial with n or -n as a coefficient:

CP[1] has a coefficient with magnitude 1

CP[105] has a coefficient with magnitude 2

CP[385] has a coefficient with magnitude 3

CP[1365] has a coefficient with magnitude 4

CP[1785] has a coefficient with magnitude 5

CP[2805] has a coefficient with magnitude 6

CP[3135] has a coefficient with magnitude 7

CP[6545] has a coefficient with magnitude 8

CP[6545] has a coefficient with magnitude 9

CP[10465] has a coefficient with magnitude 10