Math::Polynomial::Cyclotomic - cyclotomic polynomials generator
This documentation refers to Version 0.004 of Math::Polynomial::Cyclotomic. The fall 2021 releases of this library are dedicated to the memory of Andrzej Schinzel.
use Math::Polynomial::Cyclotomic qw( cyclo_poly cyclo_factors cyclo_plusfactors cyclo_poly_iterate cyclo_lucas_cd cyclo_int_factors cyclo_int_plusfactors ); use Math::Polynomial::Cyclotomic qw(:all); $p6 = cyclo_poly(6); # x^2-x+1 # complete factorization of x^6-1 @fs = cyclo_factors(6); # x-1, x+1, x^2+x+1, x^2-x+1 # complete factorization of x^6+1 @fp = cyclo_plusfactors(6); # x^2+1, x^4-x^2+1 # iterator generating consecutive cyclotomic polynomials $it = cyclo_poly_iterate(1); $p1 = $it->(); # x-1 $p2 = $it->(); # x+1 $p3 = $it->(); # x^2+x+1 # generate C, D so that C^2 - 7*x*D^2 is a cyclotomic polynomial ($c, $d) = cyclo_lucas_cd(7); # x^3+3x^2+3x+1, x^2+x+1 ($c, $d) = cyclo_schinzel_cd(14, 7); # the same # constructors for a given coefficient type, such as Math::AnyNum $poly = Math::Polynomial->new(Math::AnyNum->new(0)); $p6 = $poly->cyclotomic(6); # x^2-x+1 @fs = $poly->cyclo_factors(6); # x-1, x+1, x^2+x+1, x^2-x+1 @fp = $poly->cyclo_plusfactors(6); # x^2+1, x^4-x^2+1 $it = $poly->cyclo_poly_iterate(1); # like sub cyclo_poly_iterate @cd = $poly->cyclo_lucas_cd(7); # x^3+3x^2+3x+1, x^2+x+1 @cd = $poly->cyclo_schinzel_cd(12, 2); # x^2+x+1, x+1 # partial factorization of 5^15-1 @fs = cyclo_int_factors(5, 15); # 4, 31, 11, 71, 181, 1741 # partial factorization of 7^21+1 @fs = cyclo_int_plusfactors(7, 21); # 8, 43, 113, 911, 51031, 309079 # optional argument: hashref of read-write polynomial index %table = (); @f6 = cyclo_factors(6, \%table); $p18 = cyclo_poly(18, \%table); # faster now @cd12 = cyclo_lucas_cd(6, \%table); @cd36 = cyclo_schinzel_cd(36, 6, \%table); # faster now
This extension of Math::Polynomial adds a constructor for cyclotomic polynomials and a factoring algorithm for rational polynomials of the form x^n-1 and x^n+1. Cyclotomic polynomials are monic irreducible polynomials with integer coefficients that are a divisor of some binomial x^n-1 but not of any other binomial x^k-1 with k < n.
This module works best with coefficient spaces allowing arbitrary precision integer arithmetic, like Math::BigInt, or Math::BigRat, or Math::AnyNum. Integer arguments may be given as perl integers, strings of decimal digits, or elements of the coefficient space then, and will be converted accordingly. By contrast, Perl built-in numerical values as coefficients will introduce rounding errors in all but the most trivial cases and thus produce mostly nonsense.
If $n is a positive integer number, cyclo_poly($n) calculates the nth cyclotomic polynomial over Math::BigInt numbers.
$n
cyclo_poly($n)
If %table is a dictionary mapping indexes to previously computed cyclotomic polynomials, cyclo_poly($n, \%table) will do the same, but use the table to store and look up intermediate results that also happen to be cyclotomic polynomials. This can speed up subsequent calculations considerably. The table may only contain entries created by this module and with matching coefficient types. To be safe, start with an empty hash but re-use it for similar calculations.
%table
cyclo_poly($n, \%table)
If $poly is a Math::Polynomial object and Math::Polynomial::Cyclotomic has been loaded, $poly->cyclotomic($n) is essentially equivalent to cyclo_poly($n), but returns a polynomial sharing the coefficient type of $poly.
$poly
$poly->cyclotomic($n)
With an optional hashref argument for memoization, $poly->cyclotomic($n, \%table) will work similar to cyclo_poly($n, \%table).
$poly->cyclotomic($n, \%table)
If $n is a positive integer number, cyclo_factors($n) calculates a complete factorization of x^n-1 over the field of rational numbers. These are precisely the cyclotomic polynomials with index k, k running through all positive integer divisors of n. The factors are ordered by increasing index, so that the nth cyclotomic polynomial will be the last element of the list returned.
cyclo_factors($n)
Like all calculation methods, this function takes an optional hashref argument for memoization, as in cyclo_factors($n, \%table).
cyclo_factors($n, \%table)
If $poly is a Math::Polynomial object and Math::Polynomial::Cyclotomic has been loaded, $poly->cyclo_factors($n) is essentially equivalent to cyclo_factors($n), but returns a list of polynomials sharing the coefficient type of $poly.
$poly->cyclo_factors($n)
With an optional hashref argument for memoization, $poly->cyclo_factors($n, \%table) will work similar to cyclo_factors($n, \%table).
$poly->cyclo_factors($n, \%table)
If $n is a positive integer number, cyclo_plusfactors($n) calculates a complete factorization of x^n+1 over the field of rational numbers. These are precisely the cyclotomic polynomial factors of x^(2n)-1 that are not also factors of x^n-1. The factors are ordered by increasing index, so that the 2nth cyclotomic polynomial will be the last element of the list returned.
cyclo_plusfactors($n)
Like all calculation methods, this function takes an optional hashref argument for memoization, as in cyclo_plusfactors($n, \%table).
cyclo_plusfactors($n, \%table)
If $poly is a Math::Polynomial object and Math::Polynomial::Cyclotomic has been loaded, $poly->cyclo_plusfactors($n) is essentially equivalent to cyclo_plusfactors($n), but returns a list of polynomials sharing the coefficient type of $poly.
$poly->cyclo_plusfactors($n)
With an optional hashref argument for memoization, $poly->cyclo_plusfactors($n, \%table) will work similar to cyclo_plusfactors($n, \%table).
$poly->cyclo_plusfactors($n, \%table)
If $n is a positive integer number, cyclo_poly_iterate($n) returns a coderef that, repeatedly called, returns consecutive cyclotomic polynomials starting with index n. If $n is omitted it defaults to 1. Iterating this way is more time-efficient than repetitive calls of cyclo_poly, as intermediate results that would otherwise be re-calculated later are memoized in the state of the closure. Re-assigning or undefining the coderef will free the memory used for that.
cyclo_poly_iterate($n)
Alternatively, an external memoization table can be used, if supplied as optional hashref argument, as in cyclo_poly_iterate($n, \%table).
cyclo_poly_iterate($n, \%table)
If $poly is a Math::Polynomial object and Math::Polynomial::Cyclotomic has been loaded, $poly->cyclo_poly_iterate($n) is essentially equivalent to cyclo_poly_iterate($n), but the polynomials returned by the iterator will share the coefficient type of $poly.
$poly->cyclo_poly_iterate($n)
With an optional hashref argument for memoization, $poly->cyclo_poly_iterate($n, \%table) will work similar to cyclo_poly_iterate($n, \%table).
$poly->cyclo_poly_iterate($n, \%table)
Cyclotomic polynomials are irreducible over the integers and rationals, but when restricted to particular integer values they may have an algebraic factorization.
For example, since cyclo_poly(4) = x^2 + 1 = (x + 1 - sqrt(2*x)) * (x + 1 + sqrt(2*x)), cyclo_poly(4) has integer factors for values of x where the square root is an integer, i.e. where x is twice a square.
Such factorizations are called Aurifeuillean after Léon-François-Antoine Aurifeuille (1822-1882), who found our example algebraically explaining Fortuné Landry's famous factorization of 2^58+1 in 1871.
Richard Peirce Brent (b. 1946) gave a calculation method for the identity of Aurifeuille, Henri Le Lasseur (1821-1894) and Édouard Lucas (1842-1891), yielding Polynomials C and D with the property that C^2 - n*x*D^2 with square-free n > 1 is equal to one of the cyclotomic polynomials cyclo_poly(n) or cyclo_poly(2*n). This method can be generalized to odd multiples of n or 2*n, satisfying the identities of N.G.W.H. Beeger (1884-1965) and Andrzej Schinzel (1937-2021). We do so here and name these polynomials Schinzel C,D polynomials. This is not an official name so far, but seems quite appropriate, honoring Schinzel's work on the subject and commemorating his recent demise.
If $n is a square-free integer greater than one, ($C, $D) = cyclo_lucas_cd($n) returns two polynomials C and D with the property that Φ = C^2 - n*x*D^2, where Φ is cyclo_poly(n) if n ≡ 1 (mod 4), otherwise cyclo_poly(2*n). This can be used to derive Aurifeuillean factors C ± D * sqrt(n*x) of Φ(x) where x is n times a square number.
($C, $D) = cyclo_lucas_cd($n)
Like all calculation methods, this function takes an optional hashref argument for memoization, as in cyclo_lucas_cd($n, \%table).
cyclo_lucas_cd($n, \%table)
If $poly is a Math::Polynomial object and Math::Polynomial::Cyclotomic has been loaded, $poly->cyclo_lucas_cd($n) is essentially equivalent to cyclo_lucas_cd($n), but the polynomials returned will share the coefficient type of $poly.
$poly->cyclo_lucas_cd($n)
cyclo_lucas_cd($n)
With an optional hashref argument for memoization, $poly->cyclo_lucas_cd($n, \%table) will work similar to cyclo_lucas_cd($n, \%table).
$poly->cyclo_lucas_cd($n, \%table)
If $k is a square-free integer greater than one, and $k1 = ($k % 4 == 1)? $k: 2*$k, and $n is an odd multiple of $k1, ($C, $D) = cyclo_schinzel_cd($n, $k) returns two polynomials C and D with the property that cyclo_poly(n) = C^2 - k*x*D^2. This can be used to derive Aurifeuillean factors C ± D * sqrt(k*x) of cyclo_poly(n) where x is k times a square number. cyclo_schinzel_cd($k1, $k) is equivalent to cyclo_lucas_cd($k).
$k
$k1 = ($k % 4 == 1)? $k: 2*$k
$k1
($C, $D) = cyclo_schinzel_cd($n, $k)
cyclo_schinzel_cd($k1, $k)
cyclo_lucas_cd($k)
Like all calculation methods, this function takes an optional hashref argument for memoization, as in cyclo_schinzel_cd($n, $k, \%table).
cyclo_schinzel_cd($n, $k, \%table)
If $poly is a Math::Polynomial object and Math::Polynomial::Cyclotomic has been loaded, $poly->cyclo_schinzel_cd($n, $k) is essentially equivalent to cyclo_schinzel_cd($n, $k), but the polynomials returned will share the coefficient type of $poly.
$poly->cyclo_schinzel_cd($n, $k)
cyclo_schinzel_cd($n, $k)
With an optional hashref argument for memoization, $poly->cyclo_schinzel_cd($n, $k, \%table) will work similar to cyclo_schinzel_cd($n, $k, \%table).
$poly->cyclo_schinzel_cd($n, $k, \%table)
If $x and $n are positive integers, cyclo_int_factors($x, $n) returns a partial factorization of $x ** $n - 1, using cyclotomic and Aurifeuillean factors where possible, as a list of Math::BigInt objects.
$x
cyclo_int_factors($x, $n)
$x ** $n - 1
Like all calculation methods, this function takes an optional hashref argument for memoization, as in cyclo_int_factors($x, $n, \%table).
cyclo_int_factors($x, $n, \%table)
If $poly is a Math::Polynomial object and Math::Polynomial::Cyclotomic has been loaded, $poly->cyclo_int_factors($x, $n) is essentially equivalent to cyclo_int_factors($x, $n), but the numbers returned will have the coefficient type of $poly.
$poly->cyclo_int_factors($x, $n)
With an optional hashref argument for memoization, $poly->cyclo_int_factors($x, $n, \%table) will work similar to cyclo_int_factors($x, $n, \%table).
$poly->cyclo_int_factors($x, $n, \%table)
If $x and $n are positive integers, cyclo_int_plusfactors($x, $n) returns a partial factorization of $x ** $n + 1, using cyclotomic and Aurifeuillean factors where possible, as a list of Math::BigInt objects.
cyclo_int_plusfactors($x, $n)
$x ** $n + 1
Like all calculation methods, this function takes an optional hashref argument for memoization, as in cyclo_int_plusfactors($x, $n, \%table).
cyclo_int_plusfactors($x, $n, \%table)
If $poly is a Math::Polynomial object and Math::Polynomial::Cyclotomic has been loaded, $poly->cyclo_int_plusfactors($x, $n) is essentially equivalent to cyclo_int_plusfactors($x, $n), but the numbers returned will have the coefficient type of $poly.
$poly->cyclo_int_plusfactors($x, $n)
With an optional hashref argument for memoization, $poly->cyclo_int_plusfactors($x, $n, \%table) will work similar to cyclo_int_plusfactors($x, $n, \%table).
$poly->cyclo_int_plusfactors($x, $n, \%table)
This distribution has an examples directory with scripts generating cyclotomic polynomials and demonstrating Aurifeuillean factorization.
cyclo_poly n with positive integer n prints the nth cyclotomic polynomial.
cyclo_poly n
cyclo_poly min max with positive integers min and max prints cyclotomic polynomials with orders n ranging from min to max.
cyclo_poly min max
Option -f as in cyclo_poly -f 12 switches to printing a complete factorization of x^n - 1 into cyclotomic polynomials.
-f
cyclo_poly -f 12
Option -F as in cyclo_poly -F 9 switches to printing a complete factorization of x^n + 1 into cyclotomic polynomials.
-F
cyclo_poly -F 9
lucas_cd n with square-free integer n > 1 prints Lucas C,D polynomials with parameter n.
lucas_cd n
The output is a data structure [n1,n,C,D] suitable to be parsed by Pari/GP, with the order of the cyclotomic polynomial n1, the parameter n, and the coefficients of the polynomials C and D, starting with the leading coefficient.
[n1,n,C,D]
schinzel_cd n k with square-free integer k > 1 and suitable n (see equally named method above) prints Schinzel C,D polynomials with parameters n and k.
schinzel_cd n k
The output is a data structure [n,k,C,D] suitable to be parsed by Pari/GP, with the order of the cylotomic polynomial n, the parameter k, and the coefficients of the polynomials C and D, starting with the leading coefficient.
[n,k,C,D]
int_factors x n with positive integers x and n calculates a partial factorization of x^n - 1 using cyclotomic and Aurifeuillean factors.
int_factors x n
int_plusfactors x n with positive integers x and n calculates a partial factorization of x^n + 1 using cyclotomic and Aurifeuillean factors.
int_plusfactors x n
In addition to this library's specific diagnostic messages, some exceptions from Math::Polynomial or Math::Prime::Util may indicate inappropriate arguments.
%d: not a square-free integer greater than one
An integer argument of cyclo_lucas_cd or cyclo_schinzel_cd should be square-free and greater than one, but was not.
%d: n is not an odd multiple of k
%d: n is not an odd multiple of 2*k
cyclo_schinzel_cd was called with arguments n and k no Schinzel polynomials are defined for. n has to be an odd multiple of k if k ≡ 1 (mod 4) or of 2·k otherwise.
exponent too large
The integer argument n, which necessitates operations on polynomials up to degree 2*n, was too large for current Math::Polynomial limitations.
Parameter '%s' must be a positive integer
The argument n should have been a positive integer number but was not.
This library uses Math::BigInt as default type for coefficients, Math::Polynomial (version 1.014 and up) for polynomial arithmetic, and Math::Prime::Util (version 0.47 and up) for factoring integers. The minimal required perl version is 5.6. For better performance, Math::BigInt::GMP and Math::Prime::Util::GMP are also recommended. Other supported coefficient types are Math::BigRat and Math::AnyNum.
It will be not very hard to extend the interface to factor not just x^n±1 but, more generally, x^n±y^n, too. We consider adding this feature in an upcoming release.
Functions like poliscyclo and poliscycloprod in Pari/GP, for finding out whether a given polynomial is cyclotomic or a product of cyclotomic polynomials, would also fit into the scope of this library.
Other improvements should address performance with large degrees, eventually. This is, however, not a priority so far.
One way to achieve better time efficiency could be adding precomputed data. As this would imply a space penalty, it would have to be kept in a separately installable module, like Math::Polynomial::Cyclotomic::Data. An experimental version with Cyclotomic and Schinzel polynomials for n up to 10000 took about 1 GB of disk storage.
For calculating Schinzel polynomials, intermediate steps operating in quadratic fields ℚ[√n] are currently implemented employing a rather costly parameter substitution x → n·t². An efficient implementation of quadratic field arithmetic might speed that up.
The optional arguments for memoization are considered somewhat inelegant. Exposing them is intended as a way to avoid memory leaks, and to avoid mixing different coefficient spaces in some global cache. We are still looking for better ways to achieve both.
This implementation is optimized for n ≤ 5000. It assumes that factoring numbers up to n is cheap, and it employs polynomial division via Math::Polynomial, using pure Perl to operate on arrays of coefficients.
For larger n, $Math::Polynomial::max_degree must be raised or undefined. For very large n, a memory-efficient polynomial type and an arbitrary precision coefficient type should be used. Note that although Math::BigInt is not in general a coefficient type suitable for polynomial division, in this case it would be sufficent, as all of our divisions in the coefficient space have integer results.
$Math::Polynomial::max_degree
Currently, our algorithms do not always avoid factoring integer numbers more than once. Doing so more rigorously, or establishing access to pre-computed factorization data, could speed up calculations for very large n.
In order to avoid overflow, most calculations are carried out with Math::BigInt objects or in the given coefficient space, even when the numbers are small enough to fit into native integers. Distinguishing these cases, in a similar way Math::Prime::Util does, could speed up calculations for very small n.
Finally, there are faster algorithms for calculating single cyclotomic polynomials. Our recursive algorithm employing polynomial division can take profit from polynomials calculated earlier, but may compare unfavorably in a single-run situation. We also leave out some advantages that could be taken from recognizing more special cases.
Bug reports and suggestions are always welcome. Please submit them through the github issue tracker, https://github.com/mhasch/perl-Math-Polynomial-Cyclotomic/issues.
Math::Polynomial
Math::Prime::Util
Cyclotomic polynomial in Wikipedia, https://en.wikipedia.org/wiki/Cyclotomic_polynomial
Richard P. Brent, On computing factors of cyclotomic polynomials, in: Mathematics of Computation 61 (1993), https://maths-people.anu.edu.au/~brent/pub/pub135.html
Bill Allombert & Karim Belabas, Practical Aurifeuillian Factorization (2008), in: Journal de Théorie des Nombres de Bordeaux 20, 10.5802/jtnb.641, https://www.researchgate.net/publication/267478352_Practical_Aurifeuillian_Factorization
Andrzej Schinzel in Wikipedia, https://en.wikipedia.org/wiki/Andrzej_Schinzel
Martin Becker, Blaubeuren, <becker-cpan-mp (at) cozap.com>
Thanks go to Slaven Rezić for pointing out a dependency issue, and for CPAN smoketesting in general. Good work!
Contributions to this library are welcome (see the CONTRIBUTING file).
Copyright (c) 2019-2021 by Martin Becker, Blaubeuren.
This library is free software; you can distribute it and/or modify it under the terms of the Artistic License 2.0 (see the LICENSE file).
This library is distributed in the hope that it will be useful, but without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose.
To install Math::Polynomial::Cyclotomic, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::Polynomial::Cyclotomic
CPAN shell
perl -MCPAN -e shell install Math::Polynomial::Cyclotomic
For more information on module installation, please visit the detailed CPAN module installation guide.