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

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

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

>>> 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
aurifeuillian(2, 2)
aurifeuillian(2, 2^5)
aurifeuillian(5, 3)
aurifeuillian(15, 1)
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: 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 *
>>> 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]

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)
sage.rings.factorint.fermat_factor(n, max_iterations=10000)[source]

Try to split n using Fermat’s factorization method.

Fermat’s method writes \(n\) as a difference of two squares \(n = a^2 - b^2 = (a - b)(a + b)\). Starting from \(a = \lceil\sqrt{n}\rceil\), it tests for successive values of \(a\) whether \(a^2 - n\) is a perfect square.

The number of iterations needed is \((p + q)/2 - \lceil\sqrt{pq}\rceil \approx (p - q)^2/(8\sqrt{n})\). The method is therefore effective precisely when n has two factors of close magnitude, and hopeless when the factors are far apart.

INPUT:

  • n – integer at least 3

  • max_iterations – integer (default: 10000); number of candidate values of \(a\) to test

OUTPUT:

A pair (p, q) of integers with p * q == n and p <= q, or None if no such pair was found within max_iterations iterations. The factors are not guaranteed to be prime, and the pair may be the trivial factorization (1, n).

EXAMPLES:

sage: from sage.rings.factorint import fermat_factor
sage: p = next_prime(2^512); q = next_prime(p)
sage: fermat_factor(p * q) == (p, q)
True

>>> from sage.all import *
>>> from sage.rings.factorint import fermat_factor
>>> p = next_prime(Integer(2)**Integer(512)); q = next_prime(p)
>>> fermat_factor(p * q) == (p, q)
True

from sage.rings.factorint import fermat_factor
p = next_prime(2^512); q = next_prime(p)
fermat_factor(p * q) == (p, q)

The method splits moduli far beyond the reach of factor() when the two prime factors share their leading bits:

sage: p = next_prime(2^1024 + 2^400); q = next_prime(2^1024 + 2^500)
sage: fermat_factor(p * q) == (p, q)
True

>>> from sage.all import *
>>> p = next_prime(Integer(2)**Integer(1024) + Integer(2)**Integer(400)); q = next_prime(Integer(2)**Integer(1024) + Integer(2)**Integer(500))
>>> fermat_factor(p * q) == (p, q)
True

p = next_prime(2^1024 + 2^400); q = next_prime(2^1024 + 2^500)
fermat_factor(p * q) == (p, q)

A perfect square yields two equal factors, and a prime yields the trivial factorization:

sage: fermat_factor(15^2)
(15, 15)
sage: fermat_factor(101)
(1, 101)

>>> from sage.all import *
>>> fermat_factor(Integer(15)**Integer(2))
(15, 15)
>>> fermat_factor(Integer(101))
(1, 101)

fermat_factor(15^2)
fermat_factor(101)

An integer congruent to \(2\) modulo \(4\) is not a difference of two squares, and far-apart factors exhaust the search budget; both cases return None:

sage: fermat_factor(22)
sage: fermat_factor(3 * next_prime(2^80), max_iterations=100)

>>> from sage.all import *
>>> fermat_factor(Integer(22))
>>> fermat_factor(Integer(3) * next_prime(Integer(2)**Integer(80)), max_iterations=Integer(100))

fermat_factor(22)
fermat_factor(3 * next_prime(2^80), max_iterations=100)

REFERENCES:

- :wikipedia:`Fermat's_factorization_method`