 NAME
 VERSION
 SYNOPSIS
 DESCRIPTION
 DIAGNOSTICS
 DEPENDENCIES
 ROADMAP
 BUGS AND LIMITATIONS
 SEE ALSO
 AUTHOR
 CONTRIBUTING
 LICENSE AND COPYRIGHT
 DISCLAIMER OF WARRANTY
NAME
Math::Polynomial::Cyclotomic  cyclotomic polynomials generator
VERSION
This documentation refers to Version 0.002 of Math::Polynomial::Cyclotomic.
SYNOPSIS
use Math::Polynomial::Cyclotomic qw(
cyclo_poly cyclo_factors cyclo_poly_iterate cyclo_factors_iterate );
use Math::Polynomial::Cyclotomic qw(:all);
$p6 = cyclo_poly(6); # x^2x+1
# complete factorization of x^61
@f6 = cyclo_factors(6); # x1, x+1, x^2+x+1, x^2x+1
# iterator generating consecutive cyclotomic polynomials
$it = cyclo_poly_iterate(1);
$p1 = $it>(); # x1
$p2 = $it>(); # x+1
$p3 = $it>(); # x^2+x+1
# iterator generating factors of consecutive binomials x^n1
$it = cyclo_factors_iterate(3);
@f3 = $it>(); # x1, x^2+x+1
@f4 = $it>(); # x1, x+1, x^2+1
# constructors for a given coefficient type, such as Math::AnyNum
$poly = Math::Polynomial>new(Math::AnyNum>new(0));
$p6 = $poly>cyclotomic(6); # x^2x+1
@fs = $poly>cyclo_factors(6); # x1, x+1, x^2+x+1, x^2x+1
$it = $poly>cyclo_poly_iterate(1); # as above
$it = $poly>cyclo_factors_iterate(3); # as above
# optional argument: hashref of readwrite polynomial index
%table = ();
@f6 = cyclo_factors(6, \%table);
$p3 = $table{3}; # already done
$p18 = cyclo_poly(18, \%table); # faster
DESCRIPTION
This small extension of Math::Polynomial adds a constructor for cyclotomic polynomials and a factoring algorithm for rational polynomials of the form x^n1. Cyclotomic polynomials are monic irreducible polynomials with integer coefficients that are a divisor of some binomial x^n1 but not of any other binomial x^k1 with k < n.
 cyclo_poly

If
$n
is a positive integer number,cyclo_poly($n)
calculates the nth cyclotomic polynomial.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. The table must not contain other stuff, nor should it be used for more than one coefficient type. To be safe, start with an empty hash but reuse it for similar calculations.  Math::Polynomial::cyclotomic

If
$poly
is a Math::Polynomial object and Math::Polynomial::Cyclotomic has been loaded,$poly>cyclotomic($n)
is essentially equivalent tocyclo_poly($n)
, but returns a polynomial sharing the coefficient type of$poly
.With an optional hashref argument for memoization,
$poly>cyclotomic($n, \%table)
will work similar tocyclo_poly($n, \%table)
.  cyclo_factors

If
$n
is a positive integer number,cyclo_factors($n)
calculates a complete factorization of x^n1 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.Like "cyclo_poly", cyclo_factors can be called with an optional hashref argument for memoization. It will store individual cyclotomic polynomials, not complete factorizations, and can thus be used with cyclo_poly and cyclo_factors interchangeably.
 Math::Polynomial::cyclo_factors

If
$poly
is a Math::Polynomial object and Math::Polynomial::Cyclotomic has been loaded,$poly>cyclo_factors($n)
is essentially equivalent tocyclo_factors($n)
, but returns a list of polynomials sharing the coefficient type of$poly
.With an optional hashref argument for memoization,
$poly>cyclo_factors($n, \%table)
will work similar tocyclo_factors($n, \%table)
.  cyclo_poly_iterate

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 timeefficient than repetitive calls of cyclo_poly, as intermediate results that would otherwise be recalculated later are memoized in the state of the closure. Reassigning or undefining the coderef will free the memory used for that.Alternatively, an external memoization table can be used, if supplied as optional hashref argument, as in
cyclo_poly_iterate($n, \%table)
.  Math::Polynomial::cyclo_poly_iterate

If
$poly
is a Math::Polynomial object and Math::Polynomial::Cyclotomic has been loaded,$poly>cyclo_poly_iterate($n)
is essentially equivalent tocyclo_poly_iterate($n)
, but the polynomials returned by the iterator will share the coefficient type of$poly
.With an optional hashref argument for memoization,
$poly>cyclo_poly_iterate($n, \%table)
will work similar tocyclo_poly_iterate($n, \%table)
.  cyclo_factors_iterate

If
$n
is a positive integer number,cyclo_factors_iterate($n)
returns a coderef that, repeatedly called, returns factorizations of consecutive binomials x^k1 starting with k = n. If$n
is omitted it defaults to 1. Iterating this way is more timeefficient than repetitive calls of cyclo_factors, as intermediate results that would otherwise be recalculated later are memoized in the state of the closure. Reassigning or undefining the coderef will free the memory used for that.Alternatively, an external memoization table can be used, if supplied as optional hashref argument, as in
cyclo_factors_iterate($n, \%table)
. It will store individual cyclotomic polynomials, not complete factorizations, and can thus be used with cyclo_poly_iterate and cyclo_factors_iterate, as well as cyclo_poly and cyclo_factors, interchangeably.  Math::Polynomial::cyclo_factors_iterate

If
$poly
is a Math::Polynomial object and Math::Polynomial::Cyclotomic has been loaded,$poly>cyclo_factors_iterate($n)
is essentially equivalent tocyclo_factors_iterate($n)
, but the polynomials returned by the iterator will share the coefficient type of$poly
.With an optional hashref argument for memoization,
$poly>cyclo_factors_iterate($n, \%table)
will work similar tocyclo_factors_iterate($n, \%table)
.
DIAGNOSTICS
While this library doesn't have specific diagnostic messages, some exceptions from Math::Polynomial or Math::Prime::Util may indicate inappropriate arguments.
exponent too large

The integer argument n, which necessitates operations on polynomials up to degree 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.
DEPENDENCIES
This library uses Math::Polynomial (version 1.001 and up) for polynomial arithmetic and Math::Prime::Util (version 0.36 and up) for factoring integers. The minimal required perl version is 5.6.
ROADMAP
While cyclotomic polynomials are irreducible over the integers in general, they can be further factorized with algebraic methods when restricted to particular integer values. We intend to add aurifeuillean factorization in an upcoming release.
It will be not very hard to extend the interface to factor not just x^n1 but, more generally, x^n±y^n, too. We might add this feature just for that reason.
Other improvements should address performance with large degrees, eventually. This is, however, not a priority so far.
BUGS AND LIMITATIONS
This implementation is optimized for n ≤ 10000. 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 memoryefficient 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.
Currently, our algorithms do not always avoid factoring integer numbers more than once. Doing so more rigorously might speed up calculations for very large n.
Bug reports and suggestions are always welcome — please submit them through the CPAN RT, http://rt.cpan.org/NoAuth/Bugs.html?Dist=MathPolynomialCyclotomic.
SEE ALSO
AUTHOR
Martin Becker, <beckercpanmp (at) cozap.com>
CONTRIBUTING
Contributions to this library are welcome (see the CONTRIBUTING file).
LICENSE AND COPYRIGHT
Copyright (c) 2019 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).
DISCLAIMER OF WARRANTY
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.