|
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[1])^e[1] * ... * ``(f[m])^e[m] such that where , are the distinct prime factors of n, and 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_k indicating an m-digit composite number that was not factored where the k 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_k(m) where the k 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 .
|
|
|
Examples
|
|
>
|
|
| (8) |
>
|
|
>
|
|
| (10) |
|
|
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.
|
|
|
|