ifactor

Factor an integer into primes

MuPAD® notebooks will be removed in a future release. Use MATLAB® live scripts instead.

MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.

Syntax

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

Description

ifactor(n) computes the prime factorization n = sp1e1 … prer 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.

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 2 r + 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 and the terms piei by means of the index operator [ ], i.e., f[1] = p1^e1, f[2] = p2^e2, ... for positive n and f[1] = s, f[2] = p1^e1, f[3] = p2^e2, ... for negative n.

The call Factored::factors(f) yields a list of the factors [p1, p2, ...], while Factored::exponents(f) returns a list of the exponents [e1, e2, ...] with 1 ≤ ir.

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 [s, p1, e1, p2, e2, ...].

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.

Examples

Example 1

To get the prime factorization of 120, enter:

f := ifactor(120)

You can access the terms of this factorization using the index operator:

f[1], f[2], f[3]

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

coerce(f, DOM_LIST)

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

domtype(f)

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)

You can ask for the type of the factorization:

Factored::getType(f)

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

Multiplying factored objects preserves the factored form:

f2 := ifactor(12)

f*f2

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(%)

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)

map(%, coerce, DOM_LIST)

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

coerce(ifactor(5), DOM_LIST)

Example 3

The bound on the prime number table is:

ifactor(PrimeLimit)

We assign a large prime number to p:

p := nextprime(10^10);
q := nextprime(10^12)

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(p^3*q^4);
(time() - t)/1000.0
10000000019^3*1000000000039^4
2.5
Factored::getType(f)
"irreducible"
delete f

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

t := time():
f := ifactor(p^3*q^4, UsePrimeTab);
(time() - t)/1000.0
1000000005856000011728326008600735477170193366706178119695352530650045867891819
0.015625
Factored::getType(f)
"unknown"
delete f

Parameters

n

An arithmetical expression representing an integer

Options

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.

PrimeLimit

ifactor(PrimeLimit) returns an integer, namely a bound on the size of prime numbers in the internal prime number table. The table contains all primes below this bound. The default values are: 1000000 on UNIX® systems and 300000 on Mac OS platforms and Windows® platforms.

The size of this table can be changed via the MuPAD command line flag -L.

Return Values

Object of domain type Factored, or a symbolic ifactor call.

Algorithms

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.