Re: time-limited integer factorization

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

On Thu, Jan 17, 2008 at 06:03:03PM -0800, Max Alekseyev wrote:
> Dear Bill,
> 
> factor_add_primes in your script does not always work as expected. For example:
> 
> ? default(factor_add_primes,1)
> %1 = 1
> ? factor(112455406951957393093)
> %2 =
> [7 1]
> [11 1]
> [37 1]
> [8513 1]
> [1245683 1]
> [3722183 1]
> ? factor(112455406951957393093,0)
> %3 =
> [7 1]
> [11 1]
> [37 1]
> [8513 1]
> [4636660085989 1]
> 
> It seems that in this example the primes 1245683 and 3722183 were not
> recorded with addprimes(), but I have no idea why. The
> factor_add_primes documentation does not explain what criterion is
> used to decide which primes it adds with addprimes().

factor_add_primes only record primes that are hard to find to avoid
filling up the memory.

> As the result, I often see incomplete factorizations produced by your
> timefact() routine even when the running time is far below the
> specified limit. Is there a way to overcome this problem?

You need to raise primelimit to at least 16777216 so that factor(,0)
find all the "easy" primes.

Cheers,
Bill.