$SPAD/src/input cyfactor.input

Timothy Daly December 3, 2016

Abstract

Contents

2

1 License

— license —

--Copyright The Numerical Algorithms Group Limited 1991.

———-

— * —

)set break resume
)spool cyfactor.output
)set message test on
)set message auto off
)clear all

———-

Special case tests of factoring code for cyclotomic polynomials ±x^{n} − 1(neven) — * —

--S 1 of 10
factor(x**84 - 1)
--R
--R
--R   (1)
--R                     2           2       2           4    2
--R     (x - 1)(x + 1)(x  - x + 1)(x  + 1)(x  + x + 1)(x  - x  + 1)
--R  *
--R       6    5    4    3    2           6    5    4    3    2
--R     (x  - x  + x  - x  + x  - x + 1)(x  + x  + x  + x  + x  + x + 1)
--R  *
--R       12    11    9    8    6    4    3
--R     (x   - x   + x  - x  + x  - x  + x  - x + 1)
--R  *
--R       12    10    8    6    4    2
--R     (x   - x   + x  - x  + x  - x  + 1)
--R  *
--R       12    11    9    8    6    4    3
--R     (x   + x   - x  - x  + x  - x  - x  + x + 1)
--R  *
--R       24    22    18    16    12    8    6    2
--R     (x   + x   - x   - x   + x   - x  - x  + x  + 1)
--R                                          Type: Factored(Polynomial(Integer))
--E 1
--S 2 of 10
factor(-(x**68 -1))
--R
--R

--R   (2)
--R   -
--R                        2
--R        (x - 1)(x + 1)(x  + 1)
--R     *
--R           16    15    14    13    12    11    10    9    8    7    6    5    4
--R          x   - x   + x   - x   + x   - x   + x   - x  + x  - x  + x  - x  + x
--R        +
--R             3    2
--R          - x  + x  - x + 1
--R     *
--R           16    15    14    13    12    11    10    9    8    7    6    5    4
--R          x   + x   + x   + x   + x   + x   + x   + x  + x  + x  + x  + x  + x
--R        +
--R           3    2
--R          x  + x  + x + 1
--R     *
--R           32    30    28    26    24    22    20    18    16    14    12    10
--R          x   - x   + x   - x   + x   - x   + x   - x   + x   - x   + x   - x
--R        +
--R           8    6    4    2
--R          x  - x  + x  - x  + 1
--R                                          Type: Factored(Polynomial(Integer))
--E 2

———-

±x^{n} + 1 (n odd)

— * —

--S 3 of 10
factor(x**99 + 1)
--R
--R
--R   (3)
--R              2           6    3
--R     (x + 1)(x  - x + 1)(x  - x  + 1)
--R  *
--R       10    9    8    7    6    5    4    3    2
--R     (x   - x  + x  - x  + x  - x  + x  - x  + x  - x + 1)
--R  *
--R        20    19    17    16    14    13    11    10    9    7    6    4    3
--R       x   + x   - x   - x   + x   + x   - x   - x   - x  + x  + x  - x  - x
--R     +
--R       x + 1
--R  *
--R        60    57    51    48    42    39    33    30    27    21    18    12
--R       x   + x   - x   - x   + x   + x   - x   - x   - x   + x   + x   - x
--R     +
--R          9    3

--R       - x  + x  + 1
--R                                          Type: Factored(Polynomial(Integer))
--E 3
--S 4 of 10
factor(-(x**77 +1))
--R
--R
--R   (4)
--R   -
--R                 6    5    4    3    2
--R        (x + 1)(x  - x  + x  - x  + x  - x + 1)
--R     *
--R          10    9    8    7    6    5    4    3    2
--R        (x   - x  + x  - x  + x  - x  + x  - x  + x  - x + 1)
--R     *
--R           60    59    53    52    49    48    46    45    42    41    39    37
--R          x   + x   - x   - x   - x   - x   + x   + x   + x   + x   - x   + x
--R        +
--R             35    34    32    30    28    26    25    23    21    19    18
--R          - x   - x   + x   - x   + x   - x   - x   + x   - x   + x   + x
--R        +
--R           15    14    12    11    8    7
--R          x   + x   - x   - x   - x  - x  + x + 1
--R                                          Type: Factored(Polynomial(Integer))
--E 4

———-

±x^{(}2^{k}) + 1 — * —

--S 5 of 10
ind := 2**6
--R
--R
--R   (5)  64
--R                                                        Type: PositiveInteger
--E 5
--S 6 of 10
factor(x**ind + 1)
--R
--R
--R         64
--R   (6)  x   + 1
--R                                          Type: Factored(Polynomial(Integer))
--E 6
--S 7 of 10

ind := 2**7
--R
--R
--R   (7)  128
--R                                                        Type: PositiveInteger
--E 7
--S 8 of 10
factor(-(x**ind + 1))
--R
--R
--R            128
--R   (8)  - (x    + 1)
--R                                          Type: Factored(Polynomial(Integer))
--E 8

———-

This takes a lot longer than it should. It will improve when the cyclotomic code improves. — * —

--S 9 of 10
factor(x**84 + 1)
--R
--R
--R   (9)
--R       4       8    4       24    20    16    12    8    4
--R     (x  + 1)(x  - x  + 1)(x   - x   + x   - x   + x  - x  + 1)
--R  *
--R       48    44    36    32    24    16    12    4
--R     (x   + x   - x   - x   + x   - x   - x   + x  + 1)
--R                                          Type: Factored(Polynomial(Integer))
--E 9
--S 10 of 10
D
--R
--R
--R   (10)  D
--R                                                            Type: Variable(D)
--E 10
)spool
)lisp (bye)

———-

References^{[1] nothing}

7