## Some Perl Code In Memory of a Great Scientist

On August 21, 2021, famous Polish mathematician Andrzej Schinzel passed away at the age of 84. He was one of the great minds behind modern number theory. May he rest in peace. I have extended one of my CPAN modules relating to his work and dedicated the release to his memory.

I'll outline one of the insights credited to Beeger (1884-1965) and Schinzel. Suppose we want to factor an integer number of the form *k ^{n} ± 1*. We can use classical Algebra to factor rational polynomials

*x*. For example,

^{n}± 1*x*. These factors always have integer coefficients, are called cyclotomic polynomials, and are "easy" to obtain. Evaluating these polynomials at

^{21}+ 1 = (x + 1)(x^{2}- x + 1)(x^{6}- x^{5}+ x^{4}- x^{3}+ x^{2}- x + 1)(x^{12}+ x^{11}- x^{9}- x^{8}+ x^{6}- x^{4}- x^{3}+ x +1)*x = k*yields us a first partial factorization of our number.

To continue our example, we see that *2 ^{21} + 1 = 3·3·43·5419*,

*3*, etc. Can we do better? Enter Aurifeuillean factorization. Aurifeuille, Le Lasseur and Lucas observed that some cyclotomic polynomials can be written in the form

^{21}+ 1 = 4·7·547·682969*C*where

^{2}- n·x·D^{2}= (C - √(n·x)D)(C + √(n·x)D)*n*is a positive integer and

*C*and

*D*are again polynomials with integer coefficients. In algebraic terms, while irreducible over the field of Rationals ℚ, cyclotomic polynomials may be reducible over some extension field ℚ[√n]. Now if the square root of

*n·x*happens to be an integer, that is when

*x*is

*n*times a square number, the formula above gets all integer, splitting a cyclotomic factor into two smaller integer factors. In short, Aurifeuille & Co. improve our factorization for some, but not all combinations of

*n*and

*k*.

For square-free *n > 1*, meaning *n* without square divisors, *Lucas C,D* polynomials can split one cyclotomic factor of *n ^{n} - 1* if

*n ≡ 1 (mod 4)*, or of

*n*otherwise, into two smaller factors. Note that the base and the exponent are equal.

^{n}+ 1It turns out that these are special cases of something more profound. Beeger and Schinzel found the best currently known generalization. Essentially, they give us *C,D* polynomials covering more cases. To illustrate their range, let's compare some factorizations of 21st powers plus one. We leave out perfect powers, as *k ^{n21}* can be better treated as an

*n*

^{21}st power of

*k*than as a 21st power of

*k*.

^{n}+-----+------------+-----------------------------------------+ | n | kind | factors of n^21+1 | +-----+------------+-----------------------------------------+ | +------------+-----------------------------------------+ | 2 | cyclotomic | 3 3 43 5419 | | +------------+-----------------------------------------+ | | complete | 3 3 43 5419 | +-----+------------+-----------------------------------------+ | +------------+-----------------------------------------+ | 3 | cyclotomic | 4 7 547 682969 | | +------------+-----------------------------------------+ | | Lucas | 4 1 7 547 682969 | | +------------+-----------------------------------------+ | | Schinzel | 4 1 7 547 301 2269 | | +------------+-----------------------------------------+ | | complete | 2 2 7 547 7 43 2269 | +-----+------------+-----------------------------------------+ | +------------+-----------------------------------------+ | 5 | cyclotomic | 6 21 13021 290639881 | | +------------+-----------------------------------------+ | | complete | 2 3 3 7 29 449 7 43 127 7603 | +-----+------------+-----------------------------------------+ | +------------+-----------------------------------------+ | 6 | cyclotomic | 6 21 13021 290639881 | | +------------+-----------------------------------------+ | | complete | 2 3 3 7 29 449 7 43 127 7603 | +-----+------------+-----------------------------------------+ | +------------+-----------------------------------------+ | 7 | cyclotomic | 8 43 102943 15772610449 | | +------------+-----------------------------------------+ | | Lucas | 8 43 113 911 15772610449 | | +------------+-----------------------------------------+ | | Schinzel | 8 43 113 911 51031 309079 | | +------------+-----------------------------------------+ | | complete | 2 2 2 43 113 911 51031 309079 | +-----+------------+-----------------------------------------+

As we can see, "Schinzel" polynomials, as I like to call them, help us with many large cyclotomic factors Lucas polynomials leave aside.

As I wanted to include Aurifeuillean factorization in my CPAN module Math::Polynomial::Cyclotomic for quite some time, I finally took the opportunity to do that. I implemented Lucas and "Schinzel" polynomials there as well as methods applying these to find algebraic factors of integer numbers of the form *k ^{n} ± 1*.
Factoring large numbers can be hard—crypto-algorithms like RSA rely on that—, and a partial factorization can be the crucial step to reduce the problem to a feasible magnitude. Curiously,

*Lucas C,D*polynomials seem to be rare in computer algebra libraries and Schinzel's results even rarer. At least CPAN now has some of these. I intend to add a Raku version later. A treasure trove of other number-theoretic functions can be found in Dana Jacobsen's Math::Prime::Util, including some that are used in M::P::Cyclotomic.

Andrzej Schinzel published more than 200 research papers and was **the** expert for number-theoretic aspects of polynomials. I dedicate the latest release of Math::Polynomial::Cyclotomic to his memory.

## References

- Math::Polynomial::Cyclotomic on CPAN
- Math::Prime::Util on CPAN
- The Cunningham Project, a project dedicated to collect integer factors of high powers of small integers ± 1
- Cyclotomic polynomial in Wikipedia
- The paper by Richard Brent my implementation of Aurifeuillean factorization of cyclotomic polynomials is based on
- Andrzej Schinzel in Wikipedia

## Leave a comment