File: /ext/sage/10.1/src/sage/arith/misc.py
Docstring :
Return the factorization of "n". The result depends on the type of
"n".
If "n" is an integer, returns the factorization as an object of
type "Factorization".
If "n" is not an integer, "n.factor(proof=proof, **kwds)" gets
called. See "n.factor??" for more documentation in this case.
Warning:
This means that applying "factor()" to an integer result of a
symbolic computation will not factor the integer, because it is
considered as an element of a larger symbolic ring.EXAMPLES:
sage: f(n) = n^2
sage: is_prime(f(3))
False
sage: factor(f(3))
9
INPUT:
* "n" -- a nonzero integer
* "proof" -- bool or "None" (default: "None")
* "int_" -- bool (default: "False") whether to return answers as
Python ints
* "algorithm" -- string
* "'pari'" -- (default) use the PARI c library
* "'kash'" -- use KASH computer algebra system (requires that
kash be installed)
* "'magma'" -- use Magma (requires magma be installed)
* "verbose" -- integer (default: 0); PARI's debug variable is set
to this; e.g., set to 4 or 8 to see lots of output during
factorization.
OUTPUT:
* factorization of n
The qsieve and ecm commands give access to highly optimized
implementations of algorithms for doing certain integer
factorization problems. These implementations are not used by the
generic "factor()" command, which currently just calls PARI (note
that PARI also implements sieve and ecm algorithms, but they are
not as optimized). Thus you might consider using them instead for
certain numbers.
The factorization returned is an element of the class
"Factorization"; use "Factorization??" to see more details, and
examples below for usage. A "Factorization" contains both the unit
factor (+1 or -1) and a sorted list of "(prime, exponent)" pairs.
The factorization displays in pretty-print format but it is easy to
obtain access to the "(prime, exponent)" pairs and the unit, to
recover the number from its factorization, and even to multiply two
factorizations. See examples below.
EXAMPLES:
sage: factor(500)
2^2 * 5^3
sage: factor(-20)
-1 * 2^2 * 5
sage: f=factor(-20)
sage: list(f)
[(2, 2), (5, 1)]
sage: f.unit()
-1
sage: f.value()
-20
sage: factor(-next_prime(10^2) * next_prime(10^7))
-1 * 101 * 10000019
sage: factor(293292629867846432923017396246429, algorithm='flint')
3 * 4852301647696687 * 20148007492971089
sage: factor(-500, algorithm='kash')
-1 * 2^2 * 5^3
sage: factor(-500, algorithm='magma')
-1 * 2^2 * 5^3
sage: factor(0)
Traceback (most recent call last):
...
ArithmeticError: factorization of 0 is not defined
sage: factor(1)
1
sage: factor(-1)
-1
sage: factor(2^(2^7) + 1)
59649589127497217 * 5704689200685129054721
Sage calls PARI's
https://pari.math.u-bordeaux.fr/dochtml/help/factor, which has
"proof=False" by default. Sage has a global proof flag, set to
"True" by default (see "sage.structure.proof.proof", or use
"proof.[tab]"). To override the default, call this function with
"proof=False".
sage: factor(3^89 - 1, proof=False)
2 * 179 * 1611479891519807 * 5042939439565996049162197
sage: factor(2^197 + 1)
3 * 197002597249 * 1348959352853811313 * 251951573867253012259144010843
Any object which has a factor method can be factored like this:
sage: K.<i> = QuadraticField(-1)
sage: factor(122 - 454*i)
(-i) * (-i - 2)^3 * (i + 1)^3 * (-2*i + 3) * (i + 4)
To access the data in a factorization:
sage: f = factor(420); f
2^2 * 3 * 5 * 7
sage: [x for x in f]
[(2, 2), (3, 1), (5, 1), (7, 1)]
sage: [p for p,e in f]
[2, 3, 5, 7]
sage: [e for p,e in f]
[2, 1, 1, 1]
sage: [p^e for p,e in f]
[4, 3, 5, 7]
We can factor Python, numpy and gmpy2 numbers:
sage: factor(math.pi)
3.141592653589793
sage: import numpy
sage: factor(numpy.int8(30))
2 * 3 * 5
sage: import gmpy2
sage: factor(gmpy2.mpz(30))
2 * 3 * 5