Integer factorization functions#
AUTHORS:
Andre Apitzsch (2011-01-13): initial version
- sage.rings.factorint.aurifeuillian(n, m, F=None, check=True)#
Return the Aurifeuillian factors \(F_n^\pm(m^2n)\).
This is based off Theorem 3 of [Bre1993].
INPUT:
n
– integerm
– integerF
– integer (default:None
)check
– boolean (default:True
)
OUTPUT:
A list of factors.
EXAMPLES:
sage: from sage.rings.factorint import aurifeuillian sage: # needs sage.libs.pari sage.rings.real_interval_field sage: aurifeuillian(2, 2) [5, 13] sage: aurifeuillian(2, 2^5) [1985, 2113] sage: aurifeuillian(5, 3) [1471, 2851] sage: aurifeuillian(15, 1) [19231, 142111] sage: # needs sage.libs.pari sage: aurifeuillian(12, 3) Traceback (most recent call last): ... ValueError: n has to be square-free sage: aurifeuillian(1, 2) Traceback (most recent call last): ... ValueError: n has to be greater than 1 sage: aurifeuillian(2, 0) Traceback (most recent call last): ... ValueError: m has to be positive
Note
There is no need to set \(F\). It’s only for increasing speed of
factor_aurifeuillian()
.
- sage.rings.factorint.factor_aurifeuillian(n, check=True)#
Return Aurifeuillian factors of \(n\) if \(n = x^{(2k-1)x} \pm 1\) (where the sign is ‘-’ if x = 1 mod 4, and ‘+’ otherwise) else \(n\)
INPUT:
n
– integer
OUTPUT:
List of factors of \(n\) found by Aurifeuillian factorization.
EXAMPLES:
sage: # needs sage.libs.pari sage.rings.real_interval_field sage: from sage.rings.factorint import factor_aurifeuillian as fa sage: fa(2^6 + 1) [5, 13] sage: fa(2^58 + 1) [536838145, 536903681] sage: fa(3^3 + 1) [4, 1, 7] sage: fa(5^5 - 1) [4, 11, 71] sage: prod(_) == 5^5 - 1 True sage: fa(2^4 + 1) [17] sage: fa((6^2*3)^3 + 1) [109, 91, 127]
REFERENCES:
- sage.rings.factorint.factor_cunningham(m, proof=None)#
Return factorization of
self
obtained using trial division for all primes in the so called Cunningham table. This is efficient ifself
has some factors of type \(b^n+1\) or \(b^n-1\), with \(b\) in \(\{2,3,5,6,7,10,11,12\}\).You need to install an optional package to use this method, this can be done with the following command line:
sage -i cunningham_tables
.INPUT:
proof
– bool (default:None
); whether or not to prove primality of each factor, this is only for factors not in the Cunningham table
EXAMPLES:
sage: from sage.rings.factorint import factor_cunningham sage: factor_cunningham(2^257-1) # optional - cunningham_tables 535006138814359 * 1155685395246619182673033 * 374550598501810936581776630096313181393 sage: factor_cunningham((3^101+1)*(2^60).next_prime(), proof=False) # optional - cunningham_tables 2^2 * 379963 * 1152921504606847009 * 1017291527198723292208309354658785077827527
- sage.rings.factorint.factor_trial_division(m, limit='LONG_MAX')#
Return partial factorization of
self
obtained using trial division for all primes up tolimit
, wherelimit
must fit in a Csigned long
.INPUT:
limit
– integer (default:LONG_MAX
) that fits in a Csigned long
EXAMPLES:
sage: from sage.rings.factorint import factor_trial_division sage: n = 920384092842390423848290348203948092384082349082 sage: factor_trial_division(n, 1000) 2 * 11 * 41835640583745019265831379463815822381094652231 sage: factor_trial_division(n, 2000) 2 * 11 * 1531 * 27325696005058797691594630609938486205809701