integer factorization

Given an integer $n$, its integer factorization (or prime factorization) consists of the primes $p_i$ which multiplied together give $n$ as a result. To put it algebraically,

$$n=\prod _{i=1}^{\omega (n)}p_i{}^{a_i},$$

with each $p_i$ distinct, all $a_i>0$ but not necessarily distinct, and $\omega (n)$ being the value of the number of distinct prime factors function. Theoretically, an integer is a product of all the prime numbers,

$$n=\prod _{i=1}^{\mathrm{\infty }}p_i{}^{a_i},$$

with many $a_i=0$.

For example, the factorization of 32851 is $7\times 13\times 19\times 19$, more usually expressed as $7\times 13\times {19}^2$. Because of the commutative property of multiplication, it does not matter in what order the prime factors are stated in, but it is customary to give them in ascending order (http://planetmath.org/AscendingOrder), and to group them together by the use of exponents.

The factorization of a positive integer is unique (this is the fundamental theorem of arithmetic). For a negative number one could take the factorization of $|n|$ and randomly give negative signs to one (or any odd number) of the prime factors. Alternatively, the factorization can be given as $-1\cdot p_1{}^{a_1}\cdot \mathrm{\dots }$ (this is what Mathematica opts for).

The term “factorization” is often used to refer to the actual process of determining the prime factors. There are several algorithms to choose from, with trial division being the simplest to implement.

Title	integer factorization
Canonical name	IntegerFactorization
Date of creation	2013-03-22 16:39:09
Last modified on	2013-03-22 16:39:09
Owner	PrimeFan (13766)
Last modified by	PrimeFan (13766)
Numerical id	8
Author	PrimeFan (13766)
Entry type	Definition
Classification	msc 11A41
Synonym	prime factorization