## `Factored` -- the domain of objects kept in factored form

#### Introduction

`Factored` is the domain of objects kept in factored form, such as prime factorization of integers, square-free factorization of polynomials, or the factorization of polynomials in irreducible factors.

#### Creating Elements

`Factored(list <, type> <, ring>)`
`Factored(f <, type> <, ring>)`

#### Parameters

`list` | - | a list of odd length
`f` | - | an arithmetical expression
`type` | - | a string (default: `"unknown"`)
`ring` | - | a domain of category `Cat::IntegralDomain` (default: `Dom::ExpressionField()`)

#### Details

- The argument `list` must be a list of odd length and of the form `[u, f1, e1, f2, e2, ..., fr, er]`, where the entries u and fi are elements of the domain `ring`, or can be converted into such elements. The ei must be integers. Here, i ranges from 1 to r.

  See section ``Operands'' below for the meaning of the entries of that list.

  An error message is reported, if one of the list entries is of wrong type.

- An arithmetical expression `f` given as the first argument is the same as giving the list `[ring::one, f, 1]`.

  See section ``Operands'' below for the meaning of the entries of that list.

  `f` must be an element of the domain `ring`, or must be convertible into such an element, otherwise an error message would be given.

- The argument `type` indicates what is known about the factorization. Currently, the following types are known:
  - `"unknown"` - nothing is known about the factorization.
  - `"irreducible"` - the fi are irreducible over the domain `ring`.
  - `"squarefree"` - the fi are square-free over the domain `ring`.

  If this argument is missing, then the type of the created factored object is set to `"unknown"`.

  The type of factorization is known to any element of `Factored`. Use the methods `"getType"` and `"setType"` (see below) to read and set the type of factorization of a given factored object.

- The argument `ring` is the ring of factorization. It must be an integral domain, i.e., a domain of category `Cat::IntegralDomain`.

  If this argument is missing, then the domain `Dom::ExpressionField()` is used.

  The ring of factorization is known to any element of `Factored`. Use the methods `"getRing"` and `"setRing"` (see below) to read and set the ring of factorization of a given factored object.

- You can use the index operator `[ ]` to extract the operands of an element `f` of the domain `Factored`, i.e., `f[1] = u, f[2] = f1, f[3] = e1, ...`.

  For example, to extract all factors fi, enter `f[2*i] $ i = 1..nops(f) div 2`. To extract all exponents ei, enter `f[2*i + 1] $ i = 1..nops(f) div 2`.

  You can also use the methods `"factors"` and `"exponents"` (see below) to access the operands, i.e., the call `Factored::factors(f)` returns a list of the factors fi, and `Factored::exponents(g)` returns a list of the exponents ei (1<=i<=r).

- The system functions `ifactor`, `factor` and `polylib::sqrfree` are the main application of this domain, they return their result in form of such factored objects (see their help pages for information about the type and ring of factorization).

  There may be no need to explicitly create factored objects, but to work with the results of the mentioned system functions.

- Note that an element of `Factored` is printed like an expression and behaves like that. As an example, the result of `f := factor(x^2 + 2*x + 1)` is an element of `Factored` and printed as `(x + 1)^2`. The call `type(f)` returns `"_power"` as the expression type of `f`.
- For an element `f` of `Factored`, the call `Factored::convert(f, DOM_LIST)` gives a list of all operands of `f`.

#### Operands

An element f of `Factored` consists of the r+1 operands u, f1, e1, f2, e2,..., fr, er, such that f = u * f1^e1 * f2^e2 * ... * fr^er.

The first operand u and the factors fi are elements of the domain `ring`. The exponents ei are integers.

#### Important Operations

You can apply (almost) each function to factored objects, functions that mainly expect arithmetical expressions as their input.

For example, one may add or multiply those objects, or apply functions such as `expand` and `diff` to them. But the result of such an operation then is usually not any longer of the domain `Factored`, as the factored form could be lost due to the operation (see examples below).

Call `expr(f)` to convert the factored object `f` into an arithmetical expression (as an element of a kernel domain).

The call `coerce(f, DOM_LIST)` returns a list of operands of the factored object `f` (see method `"convert_to"` below).

#### Result of Evaluation

Evaluating an object of type `Factored` returns itself.

#### Function Call

Calling a factored object as a function yields the object itself, regardless of the arguments. The arguments are not evaluated.

#### Method _mult: multiply factored objects

- `_mult(Factored f, any g...)`
- - Computes the product f*g*....
  - Suppose that `g` is an element of the domain `ring` (or can be converted into such an element).

    If `g` is a unit of `ring` or a factor of `f`, then the result is a factored object of the same factorization type as `f`. Otherwise, the result is an element of `Factored` with the factorization type `"unknown"`.

  - If both `f` and `g` are factored objects with factorization type `"irreducible"`, then the result is again a factored object of this type, i.e., the result is still in factored form.
  - Otherwise, the factored form of `f` is lost, and the result of this method is an element of `ring`.
  - This method overloads the function `_mult` for factored objects, i.e., one may use it in the form `f*g*...`, or in functional notation: `_mult(f, g...)`.

#### Method _power: raise a factored object to a certain power

- `_power(Factored f, any n)`
- - Computes f^n.
  - If `n` is a positive integer and `f` a factored object with factorization type `"irreducible"` or `"squarefree"`, then the result is still a factored object of this type.
  - Otherwise, the factored form of `f` is lost, and the result of this method is an element of `ring`.
  - This method overloads the function `_power` for factored objects, i.e., one may use it in the form `f^n`, or in functional notation: `_power(f, n)`.

#### Method expand: expand a factored object

- `expand(Factored f)`
- - Returns `f` in expanded form. The result of this method is an element of `ring`.

#### Method exponents: get the exponents of a factored object

- `exponents(Factored f)`
- - Returns a list of the exponents ei (1<=i<=r) of `f`.

#### Method factor: factorize a factored object

- `factor(Factored f)`
- - Factorizes `f` into irreducible factors.
  - If `f` already is of the factorization type `"irreducible"`, then this method just return `f`.

    Otherwise, this method converts `f` into an element of the domain `ring` and calls the method `"factor"` of `ring`.

    This method returns a factored object of the domain `Factored` with factorization type `"irreducible"`, if the factorization of `f` can be computed (otherwise, `FAIL` is returned).

  - This method overloads the function `factor` for factored objects, i.e., one may use it in the form `factor(f)`.

#### Method factors: get the factors of a factored object

- `factors(Factored f)`
- - Returns a list of the factors fi (1<=i<=r) of `f`.

#### Method irreducible: test if a factored object is irreducible

- `irreducible(Factored f)`
- - Returns `TRUE`, if `f` is irreducible over the integral domain `ring`, otherwise `FALSE`.
  - The test on irreducible is trivial, if `f` has the factorization type `"irreducible"`.

    Otherwise, this method converts `f` into an element of `ring` and calls the method `"irreducible"` of `ring`. The value `FAIL` is returned, if the domain `ring` cannot test if `f` is irreducible.

#### Method iszero: test on zero for factored objects

- `iszero(Factored f)`
- - Returns `TRUE` if `f` is zero, and `FALSE` otherwise.
  - This method overloads the function `iszero` for factored objects, i.e., one may use it in the form `iszero(f)`.

#### Method sqrfree: compute a square-free factorization of a factored object

- `sqrfree(Factored f)`
- - Factorizes `f` into square-free factors.
  - If `f` already is of the factorization type `"squarefree"`, then this method just return `f`.

    Otherwise, this method converts `f` into an element of the domain `ring` and calls the method `"squarefree"` of `ring`.

    This method returns a factored object of the domain `Factored` with factorization type `"squarefree"`, if the square-free factorization of `f` can be computed (otherwise, `FAIL` is returned).

  - This method overloads the function `polylib::sqrfree` for factored objects, i.e., one may use it in the form `polylib::sqrfree(f)`.

#### Method _index: extract an operand of a factored object

- `_index(Factored f, positive integer i)`
- - Returns the `i`-th operand of `f` (see above for a description of the operands of such elements).
  - Responds with an error message, if `i` is greater than the number of operands of `f`.
  - This method overloads the index operator `[ ]` for factored objects, i.e., one may use it in the form `f[i]`.

#### Method getRing: get the ring of factorization

- `getRing(Factored f)`
- - Returns the domain `ring` of `f`.

#### Method getType: get the type of factorization

- `getType(Factored f)`
- - Returns the factorization type `type` of `f`.

#### Method has: existence of an object in a factored object

- `has(Factored f, any x...)`
- - Test whether an operand of `f` contains `x`. See the system function `has` for a detailed description of the parameters.
  - This method overloads the function `has` for factored objects, i.e., one may use it in the form `has(f, x...)`.

#### Method map: map a function to the operands of factored objects

- `map(Factored f, function func...)`
- - This method first converts `f` into the unevaluated expression `u*f1^e1*f2^e2*...*fr^er`, where `u, f1, e1, ...` are the operands of `f`. Then the function `func` is mapped to that expression.

    Note that the result of this method is not longer an object of `Factored`!

  - See the system function `map` for details.
  - This method overloads the function `map` for factored objects, i.e., one may use it in the form `map(f, function func...)`.

#### Method nops: the number of operands of a factored object

- `nops(Factored f)`
- - Returns the number of operands of `f` (see above for a description of the operands of such elements).
  - This method overloads the function `nops` for factored objects, i.e., one may use it in the form `nops(f)`.

#### Method op: extract an operand of a factored object

- `op(Factored f, positive integer i)`
- - Returns the `i`-th operand of `f` (see above for a description of the operands of such elements).
  - Returns `FAIL`, if `i` is greater than the number of operands of `f`.
  - This method overloads the function `op` for factored objects, i.e., one may use it in the form `op(f, i)`.

#### Method select: select operands of a factored object

- `select(Factored f, function func...)`
- - Select all operands of `f` with respect to the decision function `func`. See the system function `select` for a detailed description of the parameters.
  - This method overloads the function `select` for factored objects, i.e., one may use it in the form `select(f, func...)`.

#### Method set_index: set an operand of a factored object

- `set_index(Factored f, positive integer i, any x)`
- - Sets the `i`-th operand of `f` to the value of `x` (see above for a description of the operands of such elements).

    The factorization type of `f` is set to `"unknown"`.

  - Responds with an error message, if `i` is greater than the number of operands of `f`.

    Make sure that `x` either is an element of the domain `ring`, or an integer.

  - This method overloads the index operator `[ ]` for factored objects, i.e., one may use it in the form `f[i]`.

#### Method setRing: set the ring of factorization

- `setRing(Factored f, domain ring)`
- - Sets the factorization ring of `f` to the domain `ring`.

  - Use this method with caution! Make sure that the factorization of `f` is still valid over the new ring, and that the operands of `f` have the correct domain type.

    `ring` must be a domain of category `Cat::IntegralDomain`, which is not checked by this method.

#### Method setType: set the type of factorization

- `setType(Factored f, string type)`
- - Sets the factorization type of `f` to `type`.

  - Use this method with caution! Make sure that the factorization type corresponds with the factorization of `f`.

#### Method subs: substitute subexpressions in the operands of a factored object

- `subs(Factored f, equation x = a...)`
- - Substitute subexpressions in the operands of `f`. See the system function `subs` for a detailed description of the parameters.
  - This method overloads the function `subs` for factored objects, i.e., one may use it in the form `subs(f, equation x = a...)`.

#### Method subsop: substitute operands of a factored object

- `subsop(Factored f, equation i = a...)`
- - Substitute the `i`-th operand of `f` by `a`. See the system function `subsop` for a detailed description of the parameters.
  - This method overloads the function `subsop` for factored objects, i.e., one may use it in the form `subsop(f, equation i = a...)`.

#### Method type: expression type of factored objects

- `type(Factored f)`
- - This method converts `f` into the unevaluated expression `u*f1^e1*f2^e2*...*fr^er` and returns its expression type that is either `"_power"`, `"_mult"`, or the type of an element of the domain `ring`.

#### Method convert: convert an object into a factored object

- `convert(any x)`
- - This method tries to convert `x` into an element of the domain type `Factored`.
  - If the conversion fails, then `FAIL` is returned.
  - `x` may either be a list of the form `[u, f1, e1, ..., fr, er]` of odd length (where `u, f1, ..., fr` are of the domain type `ring`, or can be converted into such elements, and `e1, ..., er` are integers), or an element that can be converted into the domain `ring`. The latter case corresponds to the list `[ring::one,x,1]`.

#### Method convert_to: convert factored objects into other domains

- `convert_to(Factored f, any T)`
- - This method tries to convert the factored object `f` into an element of domain type `T`, or, if `T` is not a domain, to the domain type of `T`.
  - If the conversion fails, then `FAIL` is returned.
  - If `T` is the domain `DOM_LIST`, then the list of operands of `f` is returned.

    If `T` is the domain `DOM_EXPR`, then the unevaluated expression `u*f1^e1*f2^e2*...*fr^er` is returned, where `u, f1, e1, ...` are the operands of `f`.

    Otherwise, the method `"convert"` of the domain `T` is called to convert `f` into an element of the domain `T` (which could return `FAIL`).

  - Use the function `expr` to convert `f` into an object of a kernel domain (see below).

#### Method create: create simple and fast a factored objects

- `create(list list)`
- - This method creates a new factored object in the usual way, assuming, that `list` have the correct form and type of elements (see the description of the operands of a factored object).
- `create(ring x)`
- - This method creates a new factored object with the operands `ring::one, x, 1`.

#### Method expr: convert a factored object into a kernel domain

- `expr(Factored f)`
- - This method converts `f` into an object of a kernel domain, applying the method `"expr"` of the domain `ring` to each factor of `f`.

  - Note that the factored form of `f` may be lost due to this conversion.

#### Method expr2text: convert a factored object into a string

- `expr2text(Factored f)`
- - Converts `f` to a string.

#### Method testtype: type testing for factored objects

- `testtype(Factored f, domain T)`
- - Checks, if `f` can be converted into an element of the domain `T`, and returns `TRUE` or `FAIL`, respectively.

    This method uses the method `"convert"` (see above) into check, if a conversion is possible.

  - This method is called from the system function `testtype`.

#### Method TeX: LaTeX formatting of a factored object

- `TeX(Factored f)`
- - Returns a LaTeX-formatted string for the factored object `f`.
  - The method `"TeX"` of the domain `ring` is used to get the LaTeX-representation of the corresponding operands of `f`.
  - This method is called from the system function `generate::TeX`.

#### Method _concat: concatenate operands of factored objects

- `_concat(Factored f, Factored g)`
- - Returns a new factored object by appending the factors and exponents of `g` to the operands of `f`. The first operand of the new factored object is the first operand of `f` multiplied by the first operand of `g`.

    The factorization type of the new factored object is set to `"unknown"`.

  - `f` and `g` must have the same factorization type and factorization ring, otherwise an error message is given.

#### Method maprec: allow recursive mapping for factored objects

- `maprec(Factored f, any x...)`
- - This method is called from the function `misc::maprec` and allows recursive mapping for factored objects. See the corresponding help page of this function for details.
  - First `f` is converted into the unevaluated expression `u*f1^e1*f2^e2*...*fr^er`, where `u, f1, e1, ...` are the operands of `f`. Then the function `misc::maprec` is called with this expression as its first parameter.

    Note that the result of this method is not longer an object of `Factored`!

#### Method print: pretty-print routine for factored objects

- `print(Factored f)`
- - Pretty-print of the factored object `f`. This method is used from the system function `print` for printing factored objects to the screen.

#### Method unapply: create a procedure from a factored object

- `unapply(Factored f <, identifier x>)`
- - This method converts `f` into an expression `e` using the method `"expr"` (see above) and interprets this expression as a function in `x`.... It returns a procedure computing the expression `e`.
  - This method overloads the function `fp::unapply` for factored objects, i.e., one may use it in the form `fp::unapply(f)`. See `fp::unapply` for details.

#### Example 1

The following computes the prime factorization of the integer 20:

    >> f := ifactor(20)

                                        2
                                       2  5

The result is an element of the domain `Factored`:

    >> domtype(f)

                                     Factored

which consists of the following five operands:

    >> op(f)

                                   1, 2, 2, 5, 1

They represent the integer 20 in the following form: 20 = 1 * 2^2 * 5^1. The factors are prime numbers and can be extracted in two different ways:

    >> Factored::factors(f), f[2*i] $ i = 1..nops(f) div 2

                                   [2, 5], 2, 5

`ifactor` kept the information, that the factorization ring is the ring of integers (represented by the domain `Dom::Integer`), and that the factors of `f` are prime (and therefore irreducible, because Z is an integral domain):

    >> Factored::getRing(f), Factored::getType(f)

                            Dom::Integer, "irreducible"

We can convert such an object into different forms, such as into a list of its operands:

    >> Factored::convert_to(f, DOM_LIST)

                                  [1, 2, 2, 5, 1]

or into an unevaluated expression, keeping the factored form:

    >> Factored::convert_to(f, DOM_EXPR)

                                        2
                                       2  5

or back into an integer:

    >> Factored::convert_to(f, Dom::Integer)

                                        20

You may also use the system function `convert` here, which has the same effect.

#### Example 2

We compute the factorization of the integers 108 and 512:

    >> n1 := ifactor(108); n2 := ifactor(512)

                                        2  3
                                       2  3

                                         9
                                        2

The multiplication of these two integers gives the prime factorization of 55296 = 108 * 512:

    >> n1*n2

                                       11  3
                                      2   3

Note that the most operations on such objects lead to an un-factored form, such as adding these two integers:

    >> n1 + n2

                                        620

You may apply the function `ifactor` to the result, if you are interested in its prime factorization:

    >> ifactor(%)

                                       2
                                      2  5 31

You an apply (almost) each function to factored objects, functions that mainly expect arithmetical expressions as their input. Note that, before the operation is applied, the factored object is converted into an arithmetical expression in un-factored form:

    >> Re(n1)

                                        108

#### Example 3

The second system function which deals with elements of `Factored`, is `factor`, which computes all irreducible factors of a polynomial.

For example, if we define the following polynomial of Zmod(101):

    >> p := poly(x^12 + x + 1, [x], Dom::IntegerMod(101)):

and compute its factorization into irreducible factors, we get:

    >> f := factor(p)

                2
          poly(x  + 73 x + 29, [x], Dom::IntegerMod(101)) poly(

              5       4       3       2
             x  + 62 x  + 64 x  + 63 x  + 58 x + 100, [x],

                                         5       4       3        2
             Dom::IntegerMod(101)) poly(x  + 67 x  + 72 x  + 100 x  +

             33 x + 94, [x], Dom::IntegerMod(101))

If we multiply the factored object with an element that can be converted into an element of the ring of factorization, then we get a new factored object, which then is of the factorization type `"unknown"`:

    >> x*f

                2
          poly(x  + 73 x + 29, [x], Dom::IntegerMod(101)) poly(

              5       4       3       2
             x  + 62 x  + 64 x  + 63 x  + 58 x + 100, [x],

                                         5       4       3        2
             Dom::IntegerMod(101)) poly(x  + 67 x  + 72 x  + 100 x  +

             33 x + 94, [x], Dom::IntegerMod(101)) x

    >> Factored::getType(%)

                                     "unknown"

You may use the function `expand` which returns the factored object in expanded form as an element of the factorization ring:

    >> expand(f)

                         12
                   poly(x   + x + 1, [x], Dom::IntegerMod(101))

#### Example 4

The third system function which return elements of `Factored` is `polylib::sqrfree`, which computes the square-free factorization of polynomials. For example:

    >> f := polylib::sqrfree(x^2 + 2*x + 1)

                                            2
                                     (x + 1)

The factorization type, of course, is `"squarefree"`:

    >> Factored::getType(f)

                                   "squarefree"

#### Changes

- new function

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000