integer factorization - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Group Theory : Numbers : Integer Functions : ifactor

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[1])^e[1] * ... * ``(f[n])^e[n] such that  n=uf1e1...fnen where u=signn,  f1,...,fn are the distinct prime factors of n, and  e1,...,en 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

ifactor61

61

(1)

ifactor60

2235

(2)

ifactor144

2432

(3)

expand

144

(4)

ifactor60,easy

2235

(5)

ifactor411

2211

(6)

n:=1842140223038358851257:

ifactorn,easy

13457_c18_1

(7)

ifactorn

13457676278653458498009

(8)

See Also

factor, GaussInt/GIfactor, ifactors, isprime, numtheory/factorEQ, type[facint]

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.


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam