ifactor - Maple Programming Help

ifactor

integer factorization

 Calling Sequence ifactor(n) ifactor(n, method, opts)

Parameters

 n - integer or a rational method - (optional) name of base method for factoring opts - (optional) additional arguments specific to base method

Description

 • ifactor returns the complete integer factorization of n.
 • The answer is in the form u * (f)^e * ... * (f[n])^e[n] such that  $n=u{f}_{1}^{{e}_{1}}\mathrm{...}{f}_{n}^{{e}_{n}}$ where $u=\mathrm{sign}\left(n\right)$,  ${f}_{1},\mathrm{...},{f}_{n}$ are the distinct prime factors of n, and  ${e}_{1},\mathrm{...},{e}_{n}$ are their multiplicities (negative in the case of the denominator of a rational).
 • The expand function may be applied to cause the factors to be multiplied together again.
 • If a second parameter is specified, the named method will be used when the front-end code fails to achieve the factorization. By default, a mixed method that primarily uses the multiple polynomial quadratic sieve method ('mpqsmixed') is used as the base method. Currently accepted names are:

 'mpqs' - Multiple Polynomial Quadratic Sieve method; 'morrbril' - Morrison and Brillhart's continued fraction method; 'squfof' - Shanks' undocumented square-free factorization; 'pollard' - Pollard's rho method; 'lenstra' - Lenstra's elliptic curve method; 'mpqsmixed' - 'mpqs', 'morrbril' and 'pollard'; 'mixed' - 'morrbril' and 'pollard' (default for Maple 11 and earlier) 'easy' - which does no further work; and 'easyfunc' - which does no further work, and provides the computed factors.

 • If the 'easy' option is chosen, the result of the ifactor call will be a product of the factors that were easy to compute, and one or more names of the form _c||m_n indicating an m-digit composite number that was not factored where the n is an integer which preserves (but does not imply) the uniqueness of this composite.
 • If the 'easyfunc' option is chosen, the result of the ifactor call will be a product of the factors that were easy to compute, and one or more functions of the form _c_n(m) where the n is an integer which preserves the uniqueness of this composite, and m is the composite number itself.
 • The pollard base method accepts an additional optional integer k: ifactor(n, pollard, k). It increases the efficiency of the method when one of the factors is of the form $km+1$.

Examples

 > $\mathrm{ifactor}\left(61\right)$
 ${}\left({61}\right)$ (1)
 > $\mathrm{ifactor}\left(60\right)$
 ${{}\left({2}\right)}^{{2}}{}{}\left({3}\right){}{}\left({5}\right)$ (2)
 > $\mathrm{ifactor}\left(-144\right)$
 ${-}{{}\left({2}\right)}^{{4}}{}{{}\left({3}\right)}^{{2}}$ (3)
 > $\mathrm{expand}\left(\right)$
 ${-}{144}$ (4)
 > $\mathrm{ifactor}\left(60,\mathrm{easy}\right)$
 ${{}\left({2}\right)}^{{2}}{}{}\left({3}\right){}{}\left({5}\right)$ (5)
 > $\mathrm{ifactor}\left(\frac{4}{11}\right)$
 $\frac{{{}\left({2}\right)}^{{2}}}{{}\left({11}\right)}$ (6)
 > $n≔1842140223038358851257:$
 > $\mathrm{ifactor}\left(n,\mathrm{easy}\right)$
 ${}\left({13}\right){}{}\left({457}\right){}{\mathrm{_c18_1}}$ (7)
 > $\mathrm{ifactor}\left(n\right)$
 ${}\left({13}\right){}{}\left({457}\right){}{}\left({676278653}\right){}{}\left({458498009}\right)$ (8)

References

 The implementation of the Multiple Polynomial Quadratic Sieve is based on code by Paul Zimmermann and Scott Contini, and it is described in the following articles.
 Alford, W. R. and Pomerance, C. "Implementing the Self Initializing Quadratic Sieve on a Distributed Network. In Number Theoretic and Algebraic Methods in Computer Science, Proc. Internat. Moscow Conf., June-July 1993 (Ed. A. J. van der Poorten, I. Shparlinski, and H. G. Zimmer). Singapore, World Scientific, pp. 163-174, 1995.
 Contini, S. "Factoring Integers with the Self-Initializing Quadratic Sieve", M.A. Thesis, University of Georgia, 1997.
 Pomerance, C.; Smith, J. W.; and Tuler, R. "A Pipeline Architecture for Factoring Large Integers with the Quadratic Sieve Method." SIAM J. Comput. 17, pp. 387-403, 1988.