Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Option FactorComplete->False in FactorInteger

• To: mathgroup at smc.vnet.net
• Subject: [mg30847] Re: [mg30778] Option FactorComplete->False in FactorInteger
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Thu, 20 Sep 2001 03:51:49 -0400 (EDT)
• References: <200109190416.AAA12539@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

AGUIRRE ESTIBALEZ Julian wrote:
> 
> "You can make some factoring problems go faster by setting the option
> FactorComplete->False, so that FactorInteger[n] tries to pull out only
> easy factors from n."
> 
>         Does anybody know under what conditions it returns the complete
> factorization? I am factoring integers with 40 digits, all whose prime
> factors are less than 5*10^5 .
> 
> Julian Aguirre                  | Voice:  +34 946012659
> Departamento de Matematicas     | Fax:    +34 944648500
> Universidad del Pais Vasco      | Postal: Aptdo. 644, 48080 Bilbao, Spain
>                                 | email:  mtpagesj at lg.ehu.es

At present Mathematica will pull out all factors whose squares fit into
a machine integer (these are most quickly handled by trial division). So
it is possible to miss some at the upper end of the range you indicate.
Only if nothing gets pulled out in this way will FactorInteger resort to
more strenuous methods when FactorComplete is set to False.

In[1]:= ee = Apply[Times,Table[Prime[10^j], {j,6}]]
Out[1]= 261887097144359436088778213

In[2]:= FactorInteger[ee, FactorComplete->False]
Out[2]= {{29, 1}, {541, 1}, {7919, 1}, {2107892680651777043, 1}}

This sort of thing is subject to change, and in fact our development
version behaves differently.

For the sort of number you have, if you require full factorization then
the example above shows that it is necessary to avoid the
FactorComplete->False specification. More to the point this will not be
terribly costly in performance. Indeed, (virtually) every factor of size
less than 10^6 will be found by relatively fast Pollard rho and p-1
methods, which are the next line of approach in FactorInteger following
trial division.

Daniel Lichtblau
Wolfram Research

• References:
  • Option FactorComplete->False in FactorInteger
    • From: AGUIRRE ESTIBALEZ Julian <mtpagesj@lg.ehu.es>