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 – integer

  • m – integer

  • F – integer (default: None)

  • check – boolean (default: True)

OUTPUT:

A list of factors.

EXAMPLES:

sage: from sage.rings.factorint import aurifeuillian
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: 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: 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 if self 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 to limit, where limit must fit in a C signed long.

INPUT:

  • limit – integer (default: LONG_MAX) that fits in a C signed 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
sage.rings.factorint.factor_using_pari(n, int_=False, debug_level=0, proof=None)

Factor this integer using PARI.

This function returns a list of pairs, not a Factorization object. The first element of each pair is the factor, of type Integer if int_ is False or int otherwise, the second element is the positive exponent, of type int.

INPUT:

  • int_ – (default: False), whether the factors are of type int instead of Integer

  • debug_level – (default: 0), debug level of the call to PARI

  • proof – (default: None), whether the factors are required to be proven prime; if None, the global default is used

OUTPUT:

A list of pairs.

EXAMPLES:

sage: factor(-2**72 + 3, algorithm='pari')  # indirect doctest
-1 * 83 * 131 * 294971519 * 1472414939

Check that PARI’s debug level is properly reset (trac ticket #18792):

sage: alarm(0.5); factor(2^1000 - 1, verbose=5)
Traceback (most recent call last):
...
AlarmInterrupt
sage: pari.get_debug_level()
0