NAME
Math::Polynomial::Cyclotomic - cyclotomic polynomials generator
VERSION
This documentation refers to Version 0.001 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^2-x+1
# complete factorization of x^6-1
@f6 = cyclo_factors(6); # x-1, x+1, x^2+x+1, x^2-x+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
# iterator generating factors of consecutive binomials x^n-1
$it = cyclo_factors_iterate(3);
@f3 = $it->(); # x-1, x^2+x+1
@f4 = $it->(); # x-1, 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^2-x+1
@fs = $poly->cyclo_factors(6); # x-1, x+1, x^2+x+1, x^2-x+1
$it = $poly->cyclo_poly_iterate(1); # as above
$it = $poly->cyclo_factors_iterate(3); # as aboveDESCRIPTION
This small extension of Math::Polynomial adds a constructor for cyclotomic polynomials and a factoring algorithm for rational polynomials of the form 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.
- cyclo_poly
-
If
$nis a positive integer number,cyclo_poly($n)calculates the nth cyclotomic polynomial. - Math::Polynomial::cyclotomic
-
If
$polyis 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. - cyclo_factors
-
If
$nis 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. - Math::Polynomial::cyclo_factors
-
If
$polyis 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. - cyclo_poly_iterate
-
If
$nis a positive integer number,cyclo_poly_iterate($n)returns a coderef that, repeatedly called, returns consecutive cyclotomic polynomials starting with index n. If$nis 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. - Math::Polynomial::cyclo_poly_iterate
-
If
$polyis 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. - cyclo_factors_iterate
-
If
$nis a positive integer number,cyclo_factors_iterate($n)returns a coderef that, repeatedly called, returns factorizations of consecutive binomials x^k-1 starting with k = n. If$nis omitted it defaults to 1. Iterating this way is more time-efficient than repetitive calls of cyclo_factors, 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. - Math::Polynomial::cyclo_factors_iterate
-
If
$polyis 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.
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.
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 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.
Currently, our algorithm does not avoid factoring integer numbers more than once. Doing so would 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=Math-Polynomial-Cyclotomic.
SEE ALSO
AUTHOR
Martin Becker, <becker-cpan-mp (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.