## `ifactor` -- factor an integer into primes

#### Introduction

`ifactor(`n`)` computes the prime factorization n = s * p1^^e1 * ... * pr^er of the integer n, where s is the sign of n, p1,...,pr are the distinct positive prime divisors of n, and e1,...,er are positive integers.

#### Call(s)

`ifactor(n <, UsePrimeTab>)`
`ifactor(PrimeLimit)`

#### Parameters

`n` | - | an arithmetical expression representing an integer

#### Options

`UsePrimeTab` | - | look only for those prime factors that are stored in the internal prime table of the system
`PrimeLimit` | - | return the bound on the largest prime number in the prime table

#### Returns

an object of domain type `Factored`, or a symbolic `ifactor` call.

#### Related Functions

`content`, `factor`, `Factored`, `icontent`, `igcd`, `ilcm`, `isprime`, `ithprime`, `nextprime`, `numlib::divisors`, `numlib::ecm`, `numlib::mpqs`, `numlib::pollard`, `numlib::prevprime`, `numlib::primedivisors`

#### Details

- The result of `ifactor` is an object of domain type `Factored`. Let `f:=ifactor(n)` be such an object. Internally, it is represented by the list `[s, p1, e1, ..., pr, er]` of odd length 2r+1, where r is the number of distinct prime divisors of n. The pi are not necessarily sorted by magnitude.

  You may extract the sign s, the primes pi, as well as the exponents ei by means of the index operator `[ ]`, so that `f[1] = s, f[2] = p1, f[3] = e1, ...`.

  For example, the command `f[2*i] $ i = 1..nops(f) div 2` returns all distinct prime divisors of n. The call `Factored::factors(f)` yields the same result, and `Factored::exponents(f)` returns a list of the exponents ei for 1 <= i <= r.

  The factorization of 0, 1, and -1 yields the single factor 0, 1, and -1, respectively. In these cases, the internal representation is the list `[0]`, `[1]`, and `[-1]`, respectively.

  The call `coerce(f,DOM_LIST)` returns the internal representation of a factored object, i.e., the list as described above.

  Note that the result of `ifactor` is printed as an expression, and it is implicitly converted into an expression whenever it is processed further by other MuPAD functions. For example, the result of `ifactor(`12`)` is printed as `2^2*3`, which is an expression of type `"_mult"`.

  See example 1 for illustrations, and the help page of `Factored` for more details.

- If you do not need the prime factorization of `n`, but only want to know whether it is composite or prime, use `isprime` instead, which is much faster.
- `ifactor` returns an error when the argument is a number but not an integer. A symbolic `ifactor` call is returned if the argument is not a number.

#### Option: UsePrimeTab

- Internally, MuPAD has stored a pre-computed table of all prime numbers up to a certain bound. `ifactor(`n, UsePrimeTab`)` looks only for prime factors that are stored in this internal prime number table, extracts them from `n`, and returns the undecomposed product of all other prime factors as a single factor. This is usually much faster than without the option UsePrimeTab, but it does not necessarily yield the complete prime factorization of `n`. See example 2.

#### Option: PrimeLimit

- `ifactor(`PrimeLimit`)` returns an integer, namely the bound on the largest prime number in the internal prime number table. The table contains all primes below this bound. The default values are: 1 000 000 on UNIX systems, and 300 000 on MacOS and Windows platforms.

  On UNIX platforms, the size of this table can be changed via the MuPAD command line flag `-L`.

#### Example 1

To get the prime factorization of 120, enter:

    >> f := ifactor(120)

                                       3
                                      2  3 5

You can access the internal representation of this factorization using the index operator:

    >> f[1];                            // the sign
       f[2*i]     $ i=1..nops(f) div 2; // the factors
       f[2*i + 1] $ i=1..nops(f) div 2; // the exponents

                                         1

                                      2, 3, 5

                                      3, 1, 1

The internal representation of `f`, namely the list as described above, is returned by the following command:

    >> coerce(f, DOM_LIST)

                               [1, 2, 3, 3, 1, 5, 1]

The result of `ifactor` is an object of domain type `Factored`:

    >> domtype(f)

                                     Factored

This domain implements some features for handling such objects. Some of them are described below.

You may extract the factors and exponents of the factorization also in the following way:

    >> Factored::factors(f), Factored::exponents(f)

                               [2, 3, 5], [3, 1, 1]

You can ask for the type of the factorization:

    >> Factored::getType(f)

                                   "irreducible"

This output means that all pi are prime. Other possible types are `"squarefree"` (see `polylib::sqrfree`) or `"unknown"`.

Multiplying factored objects preserves the factored form:

    >> f2 := ifactor(12)

                                        2
                                       2  3

    >> f*f2

                                       5  2
                                      2  3  5

It is important to note that you can apply nearly any function operating on arithmetical expressions to an object of domain type `Factored`. The result is usually not of this domain type:

    >> expand(f);
       domtype(%)

                                        120

                                      DOM_INT

The function `type` implicitly converts an object of domain type `Factored` into an expression:

    >> type(f)

                                      "_mult"

For a detailed description of these objects, please refer to the help page of the domain `Factored`.

#### Example 2

The factorizations of `0`, `1`, and `-1` each have exactly one factor:

    >> ifactor(0), ifactor(1), ifactor(-1)

                                     0, 1, -1

    >> map(%, coerce, DOM_LIST)

                                  [0], [1], [-1]

The internal representation of the factorization of a prime number `p` is the list `[1, p, 1]`:

    >> coerce(ifactor(5), DOM_LIST)

                                     [1, 5, 1]

#### Example 3

The bound on the prime number table is:

    >> ifactor(PrimeLimit)

                                      1000000

We assign a large prime number to `p`:

    >> p := nextprime(10^12)

                                   1000000000039

Completely factoring the `36` digit number `6*p^3` takes some time; the second output line shows the time in seconds:

    >> t := time():
       f := ifactor(6*p^3);
       (time() - t)/1000.0

                                                 3
                                2 3 1000000000039

                                       12.34

    >> Factored::getType(f)

                                   "irreducible"

Extracting only the prime factors in the prime table is much faster, but it does not yield the complete factorization; the factor p^3 remains undecomposed:

    >> t := time():
       f := ifactor(6*p^3, UsePrimeTab);
       (time() - t)/1000.0

                     2 3 1000000000117000000004563000000059319

                                       0.21

    >> Factored::getType(f)

                                     "unknown"

#### Background

- `ifactor` uses the elliptic curve method.

  `ifactor` is an interface to the kernel function `stdlib::ifactor`. It calls `stdlib::ifactor` with the given arguments and convert its result, which is the list `[s, p1, e1, ..., pr, er]` as described above, into an object of the domain type `Factored`.

  You may directly call the kernel function `stdlib::ifactor` inside your routines, in order to avoid this conversion and to decrease the running time.

#### Changes

- The return value of `ifactor` is an object of domain type `Factored`.

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