Integer factorization functions

AUTHORS:

  • Andre Apitzsch (2011-01-13): initial version

sage.rings.factorint.aurifeuillian(n, m, F=None, check=True)[source]

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: 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

>>> from sage.all import *
>>> from sage.rings.factorint import aurifeuillian

>>> # needs sage.libs.pari sage.rings.real_interval_field
>>> aurifeuillian(Integer(2), Integer(2))
[5, 13]
>>> aurifeuillian(Integer(2), Integer(2)**Integer(5))
[1985, 2113]
>>> aurifeuillian(Integer(5), Integer(3))
[1471, 2851]
>>> aurifeuillian(Integer(15), Integer(1))
[19231, 142111]

>>> # needs sage.libs.pari
>>> aurifeuillian(Integer(12), Integer(3))
Traceback (most recent call last):
...
ValueError: n has to be square-free
>>> aurifeuillian(Integer(1), Integer(2))
Traceback (most recent call last):
...
ValueError: n has to be greater than 1
>>> aurifeuillian(Integer(2), Integer(0))
Traceback (most recent call last):
...
ValueError: m has to be positive

from sage.rings.factorint import aurifeuillian
# needs sage.libs.pari sage.rings.real_interval_field
aurifeuillian(2, 2)
aurifeuillian(2, 2^5)
aurifeuillian(5, 3)
aurifeuillian(15, 1)
# needs sage.libs.pari
aurifeuillian(12, 3)
aurifeuillian(1, 2)
aurifeuillian(2, 0)

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)[source]

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]

>>> from sage.all import *
>>> # needs sage.libs.pari sage.rings.real_interval_field
>>> from sage.rings.factorint import factor_aurifeuillian as fa
>>> fa(Integer(2)**Integer(6) + Integer(1))
[5, 13]
>>> fa(Integer(2)**Integer(58) + Integer(1))
[536838145, 536903681]
>>> fa(Integer(3)**Integer(3) + Integer(1))
[4, 1, 7]
>>> fa(Integer(5)**Integer(5) - Integer(1))
[4, 11, 71]
>>> prod(_) == Integer(5)**Integer(5) - Integer(1)
True
>>> fa(Integer(2)**Integer(4) + Integer(1))
[17]
>>> fa((Integer(6)**Integer(2)*Integer(3))**Integer(3) + Integer(1))
[109, 91, 127]

# needs sage.libs.pari sage.rings.real_interval_field
from sage.rings.factorint import factor_aurifeuillian as fa
fa(2^6 + 1)
fa(2^58 + 1)
fa(3^3 + 1)
fa(5^5 - 1)
prod(_) == 5^5 - 1
fa(2^4 + 1)
fa((6^2*3)^3 + 1)

REFERENCES:

sage.rings.factorint.factor_cunningham(m, proof=None)[source]

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 – boolean (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

>>> from sage.all import *
>>> from sage.rings.factorint import factor_cunningham
>>> factor_cunningham(Integer(2)**Integer(257)-Integer(1)) # optional - cunningham_tables
535006138814359 * 1155685395246619182673033 * 374550598501810936581776630096313181393
>>> factor_cunningham((Integer(3)**Integer(101)+Integer(1))*(Integer(2)**Integer(60)).next_prime(), proof=False) # optional - cunningham_tables
2^2 * 379963 * 1152921504606847009 * 1017291527198723292208309354658785077827527

from sage.rings.factorint import factor_cunningham
factor_cunningham(2^257-1) # optional - cunningham_tables
factor_cunningham((3^101+1)*(2^60).next_prime(), proof=False) # optional - cunningham_tables
sage.rings.factorint.factor_trial_division(m, limit='LONG_MAX')[source]

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

>>> from sage.all import *
>>> from sage.rings.factorint import factor_trial_division
>>> n = Integer(920384092842390423848290348203948092384082349082)
>>> factor_trial_division(n, Integer(1000))
2 * 11 * 41835640583745019265831379463815822381094652231
>>> factor_trial_division(n, Integer(2000))
2 * 11 * 1531 * 27325696005058797691594630609938486205809701

from sage.rings.factorint import factor_trial_division
n = 920384092842390423848290348203948092384082349082
factor_trial_division(n, 1000)
factor_trial_division(n, 2000)